Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Алгоритм] Кубический подграф.

Автор: rusmgn 22.5.2010, 13:08

Условие. Задан граф G=<V,E>
Вопрос. Существует ли в E непустое подмножество E' такое, что в графе G'=<V,E'> любая вершина имеет степень, равную 3 или 0?  [C++]

Есть алгоритм, нужно проверить корректен ли он, и если нет, то исправить.  По возможности добавить комментарии.

#include <iostream.h>
#include <fstream.h>

struct Stack
{
int v,u;
int numb;
bool key;
Stack *next;
};

int n,m;
bool KEY=false;
typedef Stack* TStack;

TStack push(TStack , int ,int);
TStack pop(TStack);
void Build(TStack);
void OutPut(TStack);
void decrease(TStack ,int);
void increase(TStack ,int);
int deg(TStack,int);
TStack START;
bool K_check(TStack);
bool K_gen(int );
//---------------------------------------------------------------------------
int main()
{
fstream fin("3.TXT");
fin>>n;
fin>>m;

START=new Stack[n+1];
for(int w=0;w<n;w++)
START[w].next =NULL;

Build(START);    // построение списка графов
OutPut(START);   // вывод списка
cout<<endl<<endl;

for(int i=1;i<n+1;i++)
cout<<i<<" - "<<deg(START,i)<<endl;

if(K_gen(1)) cout<<"KUB";
else cout<<"neKUB";
delete[] START;

cin.get();
return 0;
}
//---------------------------------------------------------------------------

TStack push(TStack START, int v,int numb)
{
TStack q;
q=new Stack;
q->v=v;
q->numb=numb;
q->key=true;
q->next=START;
return q;
}

TStack pop(TStack START)
{
START=START->next;
return START;
}

//Построение списка инцидентности
void Build(TStack START)
{
fstream fin("3.TXT");
fin>>n;
fin>>m;
while(!fin.eof())
   {
   int u,v,numb;
     fin>>u;
     fin>>v;
     fin>>numb;
     START[u-1].next=push(START[u-1].next,v,numb);
     START[v-1].next=push(START[v-1].next,u,numb);
   }
   fin.close();
}

//Вывод списка инцидентности
void OutPut(TStack START)
{
for(int k=0;k<n;k++)
  {
   cout<<k+1<<" -> ";
   TStack Temp;
   Temp=START[k].next;
  while(Temp!=NULL)
    {if(Temp->key)
      {
        cout<<Temp->v<<" -> ";
       }
     Temp=Temp->next;
     if(Temp==0) cout<<"NIL";
     }
  cout<<endl;}
}

int deg(TStack START, int x)      // степень вершины
{
int V=0;

TStack Temp;
Temp=START[x-1].next;

   while(Temp!=NULL)
     {
     if(Temp->key==true)
     V++;
     Temp=Temp->next;
     }

return V;
}

bool K_check(TStack START)
{
bool k=true;
int x,y=0;
  for(int i=1;i<n+1;i++)
  {
   x=deg(START,i);
   if(x!=3)
     if(x==0) y++; //проверка на степень 0
   else
   {
    k=false;
    break;
   }
  }
if(y==n) k=false; // все изолир
return k;
}

void decrease(TStack START, int NUMB) // понижение степени
{
  TStack Temp=NULL;
  for(int i=0;i<n;i++)
  {
   Temp=START[i].next;
    while(Temp!=NULL)
    {
     if(Temp->numb==NUMB)
      {
       Temp->key=false;
       break;
      }
     Temp=Temp->next;
    }
  }
}

void increase(TStack START, int NUMB)
{
  TStack Temp=NULL;
  for(int i=0;i<n;i++)
  {
   Temp=START[i].next;
    while(Temp!=NULL)
    {
     if(Temp->numb==NUMB)
      {
       Temp->key=true;
       break;
      }
     Temp=Temp->next;
    }
  }
}

bool K_gen(int i)
{
int j;
j=i;
while(j<m+1)
{
  if(K_check(START))
  {
   KEY=true;
   return KEY;
  }
  else
  {
   decrease(START,j);
   K_gen(j+1);
   increase(START,j);
   j++;
  }

}
}