ВВЕДЕНИЕ 

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

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

     Для реализации задачи  была выбрана  программная среда Microsoft Visual  C++ 6.0. Решение поставленной задачи в данной работе представлено с помощью пузырькового метода сортировки (на основе сравнений). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1. Теоретическая часть

 

1. Постановка  задачи

 

Задача. Знакомства.

Имеется n человек, где 1≤n≤1000. Каждому из них приписано некоторое число, которое определяет количество человек, с которыми ему предписано познакомиться. При этом знакомство взаимно, т.е. если человек с номером  i знакомится с человеком с номером j, то и человек с номером j знакомится с человеком с номером i. Составить алгоритм-программу, задача которой состоит в следующем. Необходимо организовать знакомства, чтобы после их реализации участники могли быть разбиты на 2 команды таким образом, что в первой команде находятся участники, знакомые друг с другом (каждый знает каждого), а во второй – только незнакомые (никто никого не знает). При этом численность первой команды должны быть максимальна. В случае невозможности реализации знакомств в выходной файл записать ответ «NO».

     1.2. Основные понятия и определения

 

   Начало теории графов датируют 1736 г., когда Л. Эйлер решил популярную в то время «задачу о кенигсбергских мостах». Термин «граф» впервые был введен спустя 200 лет (в 1936 г.) Д. Кенигом.

• Граф или неориентированный граф G — это упорядоченная пара G = (V,E), для которой выполнены следующие условия:

• V - это непустое множество вершин или узлов,
• E - это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

   При геометрическом представлении графа  элементы множества Х изображаются точками плоскости и называются вершинами графа. Линии, соединяющие любые пары точек x и y, из которых у является отображением х, называются дугами графа. Дуги графа имеют направление, обозначаемое стрелкой, которая направлена острием от элемента х к его отображению у. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.

    Вершина Ребро

   Рис.1 Граф

   Вершины и рёбра графа называются также  элементами графа, число вершин в графе | V |  — порядком, число рёбер | E |  — размером графа.

   Вершины u и v называются концевыми вершинами (или просто концами) рёбра e = {u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

   Два ребра называются смежными, если они имеют общую концевую вершину.

• Подграфом графа  G называется граф H, определяемый следующим образом:

• Граф Н должен содержать некое подмножество вершин данного графа G и все рёбра, инцидентные данному подмножеству, т. е. должны выполняться условия: V_H≤V_G, E_H≤E_G.

• Отображением каждой вершины подграфа является пересечение отображения той же вершины в графе G со всем подмножеством вершин подграфа Н.

Подграф Н является отавным графом графа  G: V_H=V_G. Если из графа удалить часть ребер (дуг), то получим частичный граф.

• Полным графом называется граф, в котором для каждой пары вершин v1,v2, существует ребро, инцидентное v1 и инцидентное v2 (каждая вершина соединена ребром с любой другой вершиной), т.е. если две его любые вершины смежные. Обозначается: K_n=|E_Kn|=n(n-1)/2.

     Рис.2 Примеры полных графов 

     1.3 Применение графов в различных сферах 

•  «Транспортные» задачи, в которых вершинами графа  являются пункты, а ребрами - дороги (автомобильные, железные и др.) и/или другие транспортные (например, авиационные) маршруты. Другой пример - сети снабжения (энергоснабжения, газоснабжения, снабжения товарами и т.д.), в которых вершинами являются пункты производства и потребления, а ребрами - возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т.д.).

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

•  Управление проектами. С точки зрения теории графов, проект - совокупность операций и зависимостей между ними. Примером является проект строительства некоторого объекта. Решаются задачи определения последовательности выполнения операций и распределения ресурсов между ними, оптимальных с точки зрения тех или иных критериев (времени выполнения проекта, затрат, риска и др.).

•  Модели коллективов и групп, используемые в социологии, основываются на представлении людей или их групп в виде вершин, а отношений между ними (например, отношений знакомства, доверия, симпатии и т.д.) - в виде ребер или дуг. В рамках подобного описания решаются задачи исследования структуры социальных групп, их сравнения, определения агрегированных показателей, отражающих степень напряженности, согласованности взаимодействия и др.

•  Модели организационных структур, в которых  вершинами являются элементы организационной  системы, а ребрами или дугами - связи (информационные, управляющие, технологические и др.) между ними.

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

4.  Описание  алгоритма

 

• Сортировка – это процесс перестановки объектов множества в определенном порядке. Когда говорят о сортировке, подразумевают упорядочение множества элементов по возрастанию или убыванию.

     Целью алгоритма сортировки является переорганизация  записей в файле так, чтобы  они располагались в нем в  каком-то строго определенном порядке (обычно в алфавитном или числовом).

     В нашей работе мы используем сортировку пузырьковым методом. Такая сортировка является наиболее известной и популярной. Ее популярность объясняется запоминающимся названием и простотой алгоритма. Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов.  Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень, т.е. на каждом шаге наибольший элемент неотсортированной части подобно пузырьку газа в воде «всплывает вверх».

     В этом методе массив делится на две  части: отсортированную и неотсортированную. На каждом шаге метода мы пробегаем от меньших индексов к большим по неотсортированной части, каждый раз сравнивая два соседних элемента: если они не упорядочены между собой (меньший следует за большим), то меняем их местами. Тем самым за один проход путем последовательных обменов наибольший элемент неотсортированной части сдвинется к концу.

 
        Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. Расположим массив сверху вниз, от нулевого элемента - к последнему. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

Рис.3  

     После нулевого прохода по массиву «вверху» оказывается самый «легкий» элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом, второй по величине элемент поднимается на правильную позицию.

 

Рис.4 Пример сортировки 

     Делаем  проходы по все уменьшающейся  нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.

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

2. Практическая  часть

 

     2.1. Описание данных 

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

Формат  файла выходных данных. В первой строке выходного файла находится численность первой команды или «NO». В случае, если реализация знакомств возможна, то в каждой из следующих строк должны находиться 2 числа, разделенные пробелом – номера людей, которым необходимо познакомиться. Приведем примеры расчетов для конкретных исходных данных.

     По  условию задачи алгоритм-программа, используя файл входных данных, должна создавать файл выходных данных output.txt. Примеры этих файлов должны иметь такой вид:

Пример  входного файла:

4

3

2

2

1

Пример  выходного файла:

        3

1. 2
1. 3
1. 4
2. 3

 

2. Реализация  решения с помощью алгоритма

 

     Для реализации нашего алгоритма воспользуемся  пошаговым выполнением:

• Шаг 1. Из имеющегося файла считываем число в некоторую переменную n и создаём массив из n элементов. Далее в этот массив заносим количество знакомств для каждого человека из файла.
• Шаг 2. После создания массива проверяем, чтобы сумма элементов массива была чётной (так, чтобы одно знакомство – одна связь – соединяло двух людей).
• Шаг 3. Сортируем массив с помощью метода пузырьковой сортировки. Определяем количество людей в первой группе. Чтобы в первой группе каждый был знаком друг с другом, необходимо, чтобы последний человек в этой группе имел количество потенциальных знакомств, равное номеру этого человека в отсортированном массиве минус один (N-1). Объясняется это тем, что этот человек должен быть знаком со всеми до него, кроме него самого. До него находятся n человек, следовательно, количество потенциальных знакомств этого человека должно составлять n. Но существует вероятность того, что количество знакомств будет больше n.
• Шаг 4. Отсортированный массив мы начинаем проверять с правого конца, для того, чтобы после обнаружения этого элемента определить численность первой группы. Если количество потенциальных знакомств человека составляет n, то описывается полный граф из членов группы из членов первой группы с помощью имеющихся связей. Этим самым мы выполняем одно из условий задачи, т.е. максимальность первой группы.
• Шаг 5. Во второй группе считаем общее количество знакомств, после чего в первой группе считаем излишек, который остаётся после того, как мы использовали все связи первой группы для построения полного графа, т.е. для того, чтобы познакомить всех людей первой группы друг с другом. Допустим, что в первой группе n человек, тогда образования полного графа для первой группы необходимо, чтобы у каждого человека было (n-1) потенциальных знакомств, соответственно, чтобы получить излишек, мы должны из количества потенциальных знакомств каждого человека вычесть (n-1), тем самым познакомив его с каждым членом первой группы, кроме него самого. Полный излишек первой группы равен сумме излишков каждого члена данной группы.
• Шаг 6. Далее проверяем, равно ли общее количество знакомств во второй группе излишку первой группы. Делается это для того, чтобы каждый член второй группы не знал другого члена второй группы. Т.к. у людей из второй группы могут быть потенциальные знакомства, а друг с другом они не могут быть знакомы, то мы пытаемся их познакомить с людьми из первой группы, используя оставшиеся у них связи.
• Шаг 7. Далее необходимо проверить, чтобы не возникла ситуация повторных знакомств между членами первой и второй групп. Делаем это следующим образом: рассмотрим первый член второй группы и используем все его необходимые связи полностью, знакомя с необходимым количеством людей из первой группы. Это необходимое количество определяется числом потенциальных знакомств первого элемента второй группы.
• Шаг 8. Затем проверяем первую группу. Если в ней после того, как мы вычли требуемые знакомства, содержатся отрицательные значения, то знакомства не возможны, и в выходной файл выводится «NO». Если же там оказались все нули, то данную систему знакомств можно реализовать. Делаем это следующим образом: из исходного массива выбираем по первому одному элементу и распределяем все связи этого элемента между последующими (по одной связи на элемент). Делаем это до тех пор, пока в исходном массиве каждый элемент не станет равен 0. Устанавливая связи между элементами, связанные пары мы заносим в специальный массив. В итоге в выходной файл мы выводим численность первой группы, которую получили на одном из первых этапов алгоритма, и массив связей, который мы получили на последнем этапе работы алгоритма.