Теория графов

     На  рис.5 представлен пример в случае n=4. Тогда человек 1 должен иметь 3 знакомства (от вершины 1 исходит 3 ребра), человек 2 и 3 имеют по 2 знакомства и человек 4 имеет только одно.

     Рис. 5 Пример графа  для n=4.

     Итак, мы видим, что условие задачи выполняется. Пример выходного файла, имеющийся  ранее, является верным.  

2.3 Тестовый  пример. 

Для проверки правильности нашей алгоритм-программы  занесем в файл входных данных input.txt другие числа. Результаты представлены на рис. 6 и 7.

Рис. 6  Окно входного файла 

Рис.7  Окно выходного файла 
 
 

3. Руководство пользователя

 

1.  Необходимые аппаратные и программные средства

 

     Программный продукт для решения задачи создан в среде разработки Visual Studio 9.0, тестирование производилось на аппаратной платформе (заявленные характеристики): ОС Windows 7, процессор Pentium Dual Core, частота 2200 МГц, частота шины процессора 800 МГц.

     Таким образом, при предоставлении указанных выше необходимых аппаратных и программных средств, созданный программный продукт будет иметь наилучшую реализацию. Однако возможно использование и других совместимых сред программирования и аппаратных платформ.

Требования  технологического характера:

     Данная  система является автоматизированной, следовательно, предполагается наличие  пользователя, который будет управлять  поведением системы. 

2.  Пошаговое выполнение программы

 

     Для реализации задачи пользователю необходимо:

1. Открыть текстовый файл «input.txt» и внести туда требуемые параметры. В первой строке содержится количество человек, которое находится в пределах 1≤n≤1000, во всех последующих n строках – количество человек, с которыми необходимо познакомиться человеку с номером i.
2. Запустить исполняемый файл Meeting.exe.
3. Открыть текстовый файл «output.txt», в котором и будут представлены результаты вычислений программы.

 
 

       ЗАКЛЮЧЕНИЕ 

       В результате выполнения курсовой работы была разработана программа, позволяющая находить максимальный полный подграф данного графа.

     Кроме практических результатов при выполнении курсовой работы был изучен теоретический  материал по теме «Теория графов», изучен метод пузырьковой сортировки, рассмотрены основные понятия и принципы, признаки, характерные для задач, решаемых этим методом, а также разработан алгоритм решения поставленной задачи.

       Таким образом, на основании представленного  тождества решений тестового  примера можно сделать вывод  о достоверности реализованного алгоритма и созданного на его основе программного продукта. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

  БИБЛИОГРАФИЧЕСКИЙ СПИСОК 

1. Иванов  Б. Н. Дискретная математика. Алгоритмы  и программы. - М.: Лаборатория Базовых  Знаний. 2003.- 288 с.
2. Нефедов В.Н., Осипова В.А. Курс дискретной математики: Учеб. пособие. – М.: Изд-во МАИ, 1992. – 264 с.
3. Кузнецов О. П.. Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: Энергия, 1980. - 344 с.
4. Хаггарти Р. Дискретная математика для программистов - М.: Техносфера, 2003. - 320 с.
5. Порублев И.Н.Ставровский А.Б. Алгоритмы и программы. Решение олимпиадных задач. — М.: «Вильямс», 2007.-  480 c.
6. http://ru.wikipedia.org/wiki//
7. http://spbcap.org/prom/085/2/index.html
8. www.erudition.ru/referat/ref/id.34265_1.html

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

       ПРИЛОЖЕНИЕ

Листинг программы:

#include "stdafx.h" 

struct Man{

      int num;

      int acq;

}; 

struct Meeting{

      Man man1;

      Man man2;

}; 

void Sort(int n_people, Man *People){

      Man temp;

      for(int i=0; i<n_people; i++){

            for(int j=0; j<n_people-1; j++){

                  if(People[j].acq<People[j+1].acq){

                        temp=People[j];

                        People[j]=People[j+1];

                        People[j+1]=temp;

                  }

            }

      }

} 

int _tmain(int argc, _TCHAR* argv[])

{

      int n_people=0, summeet=0, bar=0, sur=0, sumgr2=0;

      bool oblom=false;

      FILE *in=fopen("Input.txt", "r"), *out=fopen("Output.txt", "w");

      fscanf(in, "%d", &n_people);

      Man *People=new Man[n_people];

      for(int i=0; i<n_people; i++){

            People[i].num=i+1;

            fscanf(in, "%d", &People[i].acq);

      }

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

            summeet+=People[i].acq;

      if(summeet%2==0)

            summeet/=2;

      else oblom=true;

      if(!oblom){

            Meeting *Meetings=new Meeting[summeet];

            Sort(n_people, People);

            for(int i=n_people-1; i>0; i--){

                  if(People[i].acq>=i){

                        bar=i+1;

                        break;

                  }

            }

            Man *Group1=new Man[bar];

            Man *Group2=new Man[n_people-bar];

            for(int i=0, j=0; i<n_people; i++){

                  if(i<bar) Group1[i]=People[i];

                  else{

                        Group2[j]=People[i];

                        j++;

                  }

            }

            for(int i=0; i<bar; i++){

                  Group1[i].acq-=Group1[bar-1].acq;

                  sur+=Group1[i].acq;

            }

            for(int i=0; i<n_people-bar; i++)

                  sumgr2+=Group2[i].acq;

            if(sur==sumgr2){

                  for(int i=0; i<n_people-bar; i++){

                        for(int j=0; j<Group2[i].acq; j++)

                              Group1[j].acq--;

                        Group2[i].acq=0;

                  }

            }

            else oblom=true;

            if(!oblom){

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

                        if(Group1[i].acq<0){

                              oblom=true;

                              break;

                        }

            }

            if(!oblom){

                  for(int i=0, k=0; i<n_people; i++){

                        for(int j=i+1; j<People[i].acq+i+1; j++){

                              People[j].acq--;

                              Meetings[k].man1=People[i];

                              Meetings[k].man2=People[j];

                              k++;

                        }

                        People[i].acq=0;

                  }

                  fprintf(out, "%d\n", bar);

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

                        fprintf(out, "%d %d\n", Meetings[i].man1.num, Meetings[i].man2.num);

            }

            delete []Group1;

            delete []Group2;

            delete []Meetings;

      }

      if(oblom)

            fprintf(out, "NO");

      fclose(in);

      fclose(out);

      delete []People;

      return 0;

       }