Реализация приближенных алгоритмов вершинной расраски графа (с помощью Delphi)

Введение

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

Заключение

В процессе выполнения курсовой работы была рассмотрена такая важная тема как раскраска графов. Задачи подобного рода встречаются довольно часто в повседневной жизни - ярким примером того может служить раскраска географических карт, на которых не должно быть граничащих областей с одинаковыми цветами. Использование алгоритмов, дающих оптимальную раскраску минимальным количеством цветов, и их реализация на ЭВМ позволяет значительно сократить время, в сравнении с ручным счетом, на получение правильной раскраски.
Созданная программа позволяет выполнять следующие действия:
• вводить граф с клавиатуры матрицей смежности;
• автоматически формировать массивы координат вершин;
• строить на экране граф и найденную раскраску;
• производить обработку нескольких графов в течение одного сеанса работы с программой, благодаря наличию в ней пользовательского меню.
Работа по созданию программы позволила приобрести практические навыки программирования прикладных задач теории графов.
Минимальные требования к аппаратуре позволяют использовать данную программу на любом компьютере с операционной системой MS-Windows 9x или ей аналогичной.