Алгоритм раскраски графа (точный)

  • Просмотров 5798
  • Скачиваний 98
  • Размер файла 133
    Кб

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Кафедра САПР Пояснительная записка к курсовому проекту по дисциплине “Дискретная математика” На тему: “Алгоритм раскраски графа (точный)" Выполнил: студентка гр. 06ВА-1 Молоткова Е. Принял: к.т.н., доцент Валько А.Ф. Пенза 2007г. СОДЕРЖАНИЕ Аннотация 1. Теоретическая часть 2. Алгоритм, использующий метод Магу - Вейссмана 2.2

Разработанный алгоритм 3. Описание программы 3.1 Общие сведения 3.2 Вызов и загрузка 3.3 Функциональное назначение 3.4 Описание логической структуры программы 3.5 Инструкция пользователю 3.6 Решение контрольных примеров Заключение СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ ПРИЛОЖЕНИЕ Аннотация В настоящей пояснительной записке приведено описание алгоритма раскраски графа (точный). Изложены вопросы проектирования структуры программы и

данных. Разработаны схемы алгоритмов решения задачи. Разработана и отлажена программа, реализующая представленные алгоритмы на языке Visual C. Представлены результаты решения контрольных примеров, выполненные с помощью разработанной программы на ПК Intel core 2 Duo. Пояснительная записка содержит 34 страницы, 5 рисунков, 4 использованных источника, приложения. 1. Теоретическая часть Графом,в общем случае, называются два множества,

находящиеся между собой в некотором отношении: G=(V,Е), где V – множество вершин, Е – множество связей между ними . Вершины графа изображаются точками, а связи между ними – линиями произвольной конфигурации. Связь неупорядоченной пары вершин называется ребром, упорядоченной- дугой. Граф, у которого все вершины соединены дугами называется ориентированным. Граф, у которого все вершины соединены ребрами называется

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