Поиск максимального независимого множества графа с помощью алгоритмов Брона-Кэрбоша, Ткача, алгоритма поиска η-областей

Автор работы: Пользователь скрыл имя, 17 Ноября 2011 в 03:43, курсовая работа

Описание

Этот граф устроен следующим образом. Вершины его - знакомые юбиляра. Две вершины смежны, если соответствующие знакомые друг другу не симпатизируют. Нетрудно понять, что число независимости этого графа и представляет тот самый максимальный контингент приглашенных, который может себе позволить юбиляр.
Таким образом, задача поиска наибольшего независимого множества заключается в нахождении наибольшего количества несмежных между собой вершин графа. Данная программа предлагает 3 алгоритма решения этой задачи.

Содержание

Введение 4
1.Математические методы 6
2.Постановка задачи 11
3.Разработка алгоритмов 12
3.1. Алгоритм Брона-Кэрбоша 12
3.2. Алгоритм Ткача 13
3.3. Алгоритм поиска η-областей 14
4.Описание программы 17
Выводы 19
Список использованных источников 20
Приложение А: Экранные формы 21
Приложение Б: код 22

Скачать (239.69 Кб) Сколько стоит заказать работу?
Работа состоит из  1 файл

Note.docx

— 255.41 Кб (Скачать документ)

        {

                for (int i = 0; i<QPnt-1; i+=2)

                {

                     sp1=0; se1=0; sp2=0; se2=0;

                     for (int j=0; j<QPnt; j++)

                     {

                        if (j<=i)

                        {

                          sp1+=AdjMatr[i][j];

                          sp2+=AdjMatr[i+1][j];

                        }

                        if (j>i)

                        {

                          se1+=AdjMatr[i][j];

                          se2+=AdjMatr[i+1][j];

                        }

                     } 

                     if ((sp1>sp2) || ((sp1==sp2)&&(se1>se2)))

                     {

                        f1 = false;

                        for (int k=0; k<QPnt; k++)

                        {

                           if ((k!=i)&&(k!=i+1))

                              swap(AdjMatr[i][k],AdjMatr[i+1][k]);

                           if ((k!=i)&&(k!=i+1))

                              swap(AdjMatr[k][i],AdjMatr[k][i+1]);

                        }

                        swap(MNM3[i],MNM3[i+1]);

                     }

                     else f1 = true;

                } 

                for (int i = 1; i<QPnt; i+=2)

                {

                     sp1=0; se1=0; sp2=0; se2=0;

                     for (int j=0; j<QPnt; j++)

                     {

                        if (j<=i)

                        {

                          sp1+=AdjMatr[i][j];

                          sp2+=AdjMatr[i+1][j];

                        }

                        if (j>i)

                        {

                          se1+=AdjMatr[i][j];

                          se2+=AdjMatr[i+1][j];

                        }

                     }

                     if ((sp1>sp2) || ((sp1==sp2)&&(se1>se2)))

                     {

                        f2 = false;

                        for (int k=0; k<QPnt; k++)

                        {

                           if ((k!=i)&&(k!=i+1))

                              swap(AdjMatr[i][k],AdjMatr[i+1][k]);

                           if ((k!=i)&&(k!=i+1))

                              swap(AdjMatr[k][i],AdjMatr[k][i+1]);

                        }

                        swap(MNM3[i],MNM3[i+1]);

                     }

                     else f2 = true;

                }

                if (f1 && f2) flag = true;

        }

} 
 

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

        : TForm(Owner)

{

    IMG->Brush->Color = clWhite;

    IMG->FillRect(Form1->Image1->ClientRect);

    IMG->Brush->Color = clBlack;

    IMG->FrameRect(Form1->Image1->ClientRect);

    IMG->Pen->Width = 2;

}

//--------------------------------------------------------------------------- 

void __fastcall TForm1::Image1MouseUp(TObject *Sender, TMouseButton Button,

      TShiftState Shift, int X, int Y)

{

     if (fBuild)

     {

           bool cls = true;

           bool puts = false;

           IMG->Brush->Color = clBlack;

           for (int i=0; i<QPnt; i++)

           {

               float d = sqrt((X-Points[i].x)*(X-Points[i].x) + (Y-Points[i].y)*(Y-Points[i].y));

               if (d<=2*R)

                  cls = false;

               if (d<=R)

               {

                  puts = true;

                  icurr = i;

                  break;

               }

           } 

           if (cls && !Select1) PutPoint(X,Y);

           if (cls && Select1) puts=true; 

           if (puts)

           {

              if (!Select1)

              {

                        edge1 = Points[icurr];

                        edge1.inc = icurr;

                        IMG->Brush->Color = clRed;

                        IMG->Pen->Color = clBlack;

                        IMG->Ellipse(edge1.x-R,edge1.y-R,edge1.x+R,edge1.y+R);

                        Select1 = true;

              } 

              else if (Select1)

              {

                 for (int i = 0; i<QPnt; i++)

                    if ((X >= Points[i].x-R)&&(X <= Points[i].x+R)&&(Y >= Points[i].y-R)&&(Y <= Points[i].y+R)&&(Points[i].x!=edge1.x)&&(Points[i].y!=edge1.y))

                    {

                        edge2 = Points[i];

                        edge2.inc = i;

                        IMG->Brush->Color = clBlack;

                        IMG->Pen->Color = clBlack;

                        IMG->Ellipse(edge1.x-R,edge1.y-R,edge1.x+R,edge1.y+R);

                        IMG->Ellipse(edge2.x-R,edge2.y-R,edge2.x+R,edge2.y+R);

                        Select2 = true;

                    }

                 if (!Select2 && !fMove)

                 {

                      PutPoint(X,Y);

                      edge2 = Points[QPnt-1];

                      edge2.inc = QPnt-1;

                      PutEdge(edge1,edge2);

                      Select1 = false;

                      IMG->Ellipse(edge1.x-R,edge1.y-R,edge1.x+R,edge1.y+R);

                 }

                 if (Select2 && !fMove)

                 {

                   PutEdge(edge1,edge2);

                   Select1 = false;

                   Select2 = false;

                 }

              }

           } 

           if (!puts && !cls)

           {

                MessageBox(NULL,"Ñëèøêîì áëèçêî ê  äðóãîé âåðøèíå!",NULL,NULL);

                cls = true;

           } 

           if (fMove)

              for (int i=0; i<QEdg; i++)

              {

                 IMG->Pen->Color = clBlack;

                 IMG->Brush->Color = clBlack;

                 IMG->MoveTo(Points[icurr].x,Points[icurr].y);

                 if ((Edges[i].p1.x==xm)&&(Edges[i].p1.y==ym))

                 {

                      IMG->LineTo(Edges[i].p2.x,Edges[i].p2.y);

                      Edges[i].p1 = Points[icurr];

                      IMG->Ellipse(Edges[i].p2.x-R,Edges[i].p2.y-R,Edges[i].p2.x+R,Edges[i].p2.y+R);

                 }

                 if ((Edges[i].p2.x==xm)&&(Edges[i].p2.y==ym))

                 {

                      IMG->LineTo(Edges[i].p1.x,Edges[i].p1.y);

                      Edges[i].p2 = Points[icurr];

                      IMG->Ellipse(Edges[i].p1.x-R,Edges[i].p1.y-R,Edges[i].p1.x+R,Edges[i].p1.y+R);

                 }

              }

           fMove = false;

     }

}

//---------------------------------------------------------------------------

void __fastcall TForm1::BRestClick(TObject *Sender)

{

        CleanWind();

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Image1MouseMove(TObject *Sender, TShiftState Shift,

      int X, int Y)

{

        Edit1->Text = X;

        Edit2->Text = Y; 

        if (fMove)

        {

                Points[icurr].x = X;

                Points[icurr].y = Y;

        }

}

//---------------------------------------------------------------------------

void __fastcall TForm1::BRedClick(TObject *Sender)

{

        IMG->Brush->Color = clBlack;

        for (int i=0; i<QPnt; i++)

                IMG->Ellipse(Points[i].x-R,Points[i].y-R,Points[i].x+R,Points[i].y+R);

        fBuild = true;

        BRest->Enabled = true;

        BTkach->Enabled = false;

        BBron->Enabled = false;

        BEta->Enabled = false;

        BDone->Enabled = true;

        BRed->Enabled = false;

        Select1 = false;

        Select2 = false;

Информация о работе Поиск максимального независимого множества графа с помощью алгоритмов Брона-Кэрбоша, Ткача, алгоритма поиска η-областей