Раскраски в теории графов
Правила раскраски графа, приписывание цветов его вершинам с условием, что никакие смежные вершины не получают одинакового цвета. Алгоритм приближенного решения задачи определения хроматического числа и построения минимальной раскраски произвольного графа.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 28.05.2019 |
| Размер файла | 1,6 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Построим граф , положив и объявив вершины смежны тогда и только тогда, когда для выполнения работ требуется хотя бы один общий механизм. При правильной раскраске графа работы, соответствующие вершинам одного цвета, можно выполнять одновременно, а наименьшее время выполнения всех работ достигается при минимальной раскраске.
3. Задача о проектировании коробки скоростей.
Коробка скоростей - механизм для изменения частоты вращения ведомого вала при постоянной частоте вращения ведущего. Это изменение происходит за счет того, что находящиеся внутри коробки шестерни (зубчатые колеса) вводятся в зацепление специальным образом. Одна из задач, стоящая перед конструктором коробки, заключается в минимизации ее размеров, а это часто сводится к минимизации числа валов, на которых размещаются шестерни.
Построим , вершины которого биективно соответствуют шестерням. Если по какой-то причине две шестерни не должны находиться на одном валу (например, они могут быть в зацеплении, или их общий вес велик для одного вала и т. д.), то соответствующие вершины графа соединим ребром. Вершины, имеющие один цвет при правильной раскраске этого графа, определяют шестерни, которые могут находиться на одном валу, а хроматическое число ч( равно минимальному количеству валов, нужных для проектируемой коробки.
Чтобы понять суть этого метода, надо обратить внимание на две вещи: во-первых, нам необходимо выбрать какую-то вершину, чтобы начать с нее раскраску, а во-вторых, все вершины, связанные с выбранной ребрами должны быть окрашены в цвета, отличные от цвета выбранной. Поэтому логично использовать один цвет для всех, не связанных с выбранной, вершин. А для того, чтобы сузить поиск вершин, которые можно окрасить в один цвет, следует выбрать вершину максимально связанную с другими, то есть имеющую наибольшую степень - ведь для всех связанных с ней вершин ее цвет заведомо использоваться не может.
Поэтому вершины вначале располагаются в порядке убывания их степеней. Первая вершина, имеющая наибольшую степень, окрашивается в цвет 1 (если несколько вершин имеют одинаковые степени можно выбрать любую из них); после этого список вершин просматривается сверху вниз (по убыванию степеней) и в цвет 1 окрашивается любая вершина, которая не смежна с другой, уже окрашенной в этот цвет. Затем возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет 2 и снова просматриваем список вершин сверху вниз, окрашивая в цвет 2 любую неокрашенную вершину, которая не соединена ребром с другой, уже окрашенной в цвет 2 вершиной. Аналогично действуем с цветами 3, 4 и т. д., пока не будут окрашены все вершины. Число использованных цветов будет приближенным значением хроматического числа графа.
Покажем работу этого алгоритма на примере.
4. Пусть дан граф, вершины которого надо раскрасить. Построим список вершин по убыванию степеней: степень 3 (deg=3) имеют вершины v1 и v4; степень 2 (deg=2) имеют вершины v2, v3 и v5.
Решение:
Выберем вершину с наибольшей степенью, например, v1 и окрасим ее (рис.б). Мы выбрали в качестве первого цвета синий (С). Вершины, смежные с вершиной v1, а это вершины v2, v4 и v5 не могут быть окрашены в синий цвет. Ищем вершины, которые можно окрасить в синий цвет. Это единственная вершина v3. Окрашиваем ее в синий цвет (рис.в). Синий цвет исчерпан, в него нельзя больше окрасить ни одну вершину. Выбираем из списка нераскрашенных вершин вторую вершину с максимальной степенью - это вершина v4 и окрашиваем ее во второй цвет (рис.г). Пусть это будет красный (К) цвет. Из оставшихся не раскрашенными вершин, вершина v5 не может быть раскрашена в красный цвет. Ищем вершины, которые можно окрасить в красный. Это единственная вершина v2. Раскрасим ее в красный. Красный цвет исчерпан. Выбираем единственную не раскрашенную вершину v5 и раскрашиваем ее в третий цвет - зеленый (З). На этом раскраска графа завершена. Количество используемых красок 3.
Число использованных цветов будет тогда приближенным значением хроматического числа графа.
5. Пример: задан граф. Раскрасить его по степеням вершин.
Составим таблицу:
|
Вершина vi |
Степень |
B(1) |
B(2) |
B(3) |
B(4) |
|
|
4 |
5 |
4 |
|
|
|
|
|
6 |
5 |
|
6 |
|
|
|
|
3 |
4 |
|
|
3 |
|
|
|
2 |
4 |
|
2 |
|
|
|
|
5 |
4 |
|
|
5 |
|
|
|
7 |
4 |
|
|
|
7 |
|
|
8 |
3 |
8 |
|
|
|
|
|
9 |
3 |
|
|
9 |
|
|
|
1 |
2 |
1 |
|
|
|
|
|
Цвет |
|
1 |
2 |
3 |
4 |
Теперь рассмотрим задачу с хроматическим многочленом:
6. Пример: Найти хроматический многочлен для графа:
=
Ответ:
Заключение
граф раскраска алгоритм хроматический
В данной работе рассмотрены: раскраски в теории графов.
Итак, для того чтобы научиться решать задачи, надо разобраться в том, что собой они представляют, как они устроены, из каких составных частей они состоят, каковы инструменты, с помощью которых производится решение задач.
Решая практические задачи с помощью теории графов стало ясно видно, что в каждом шаге, в каждом этапе их решения необходимо применить творчество.
С самого начала, на первом этапе, оно заключается в том, что нужно суметь проанализировать и закодировать условие задачи. Второй этап - схематическая запись, которая состоит в геометрическом представлении графов, и на этом этапе элемент творчества очень важен потому, что далеко не просто найти соответствия между элементами условия и соответствующими элементами графа.
Решая транспортную задачу или задачу на составление генеалогического дерева я сделала вывод, что безусловно метод графов интересен, красив и нагляден.
Курсовая работа может быть полезна студентам физико-математического факультета, желающим углублённо ознакомиться с раскрасками в теории графов.
Литература
1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов; Либроком - Москва, 2012. - 392 c.
2. Харари Ф. Теория графов / Пер.с англ. и предисл. В.П. Козырева. Под ред. Г.П. Гаврилова. Изд. 2-е. - М.: Едиториал УРСС, 2003. - 296 с.
3. Харари Ф., Палмер Э. Перечисление графов - М.: Мир, 1977. - 324 с.
4. Оре О. Теория графов.-- 2-е изд.-- М.: Наука, Главная редакция физико-математической литературы, 1980, 336 с
5. Мельников О.И. Теория графов в занимательных задачах. Изд.3, испр. и доп. 2009. 232 с.
6. Мельников О.И. Занимательные задачи по теории графов. - Минск: ТетраСистемс, 2001. - 144 с.
7. Мельников О.И. Незнайка в стране графов: Пособие для учащихся. Изд. 3-е, стереотипное. М.: КомКнига, 2007. - 160 с.
8. Зыков А.А. Основы теории графов. - М.:Наука, 1987, 384 с.
9. Теория графов в задачах и упражнениях. Более 200 задач с подробными решениями; Либроком - Москва, 2013. - 416 c.
10. Исследования по прикладной теории графов; Наука. Новосибирск - Москва, 2008. - 168 c.
11. Зыков, А.А. Теория конечных графов; Новосибирск: Наука - Москва, 2011. - 544 c.
12. Родионов В.В. Методы четырехцветной раскраски вершин плоских графов; КомКнига - Москва, 2012. - 289 c.
13. Татт У. Теория графов; НФ "Пушкинская библиотека", АСТ Москва, АСТ - Москва, 2013. - 229 c.
14. Уилсон Р. Введение в теорию графов; ЭлКниги - Москва, 2010. - 998 c.
Размещено на Allbest.ru
...Подобные документы
Алгоритм, использующий метод Магу-Вейссмана. Общие сведения, описание, вызов и загрузка, функциональное назначение и программный код программы. Описание логической структуры и инструкция пользователю, решение контрольных примеров раскраски графа.
курсовая работа [350,5 K], добавлен 20.12.2009Примеры решения задач по заданию графов. Определение основных характеристик графа: диаметра, радиуса, эксцентриситета каждой вершины. Вычисление вершинного и реберного хроматического числа. Упорядоченность матричным способом и построение функции.
контрольная работа [224,6 K], добавлен 05.07.2014История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.
курсовая работа [636,2 K], добавлен 20.12.2015Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.
контрольная работа [466,3 K], добавлен 11.03.2011Задача о кенигсбергских мостах, четырех красках, выходе из лабиринта. Матрица инцидентности для неориентированного и (ориентированного) графа. Степень вершины графа. Ориентированное дерево. Линейные диаграммы или графики Ганта. Метод критического пути.
презентация [258,0 K], добавлен 23.06.2013Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014Понятие и матричное представление графов. Ориентированные и неориентированные графы. Опеределение матрицы смежности. Маршруты, цепи, циклы и их свойства. Метрические характеристики графа. Применение теории графов в различных областях науки и техники.
курсовая работа [423,7 K], добавлен 21.02.2009Понятие "граф". Отношения между разнородными элементами. Матричное представление графов. Операции над графами. Маршруты, цепи, циклы. Метрические характеристики графа. Приложение теории графов в различных областях науки и техники. Листинг программы.
курсовая работа [725,8 K], добавлен 15.12.2008Применение интервальных графов. Алгоритмы распознавания интервальных графов: поиск в ширину, поиск в ширину с дополнительной сортировкой, лексикографический поиск в ширину, алгоритм "трех махов". Программа задания единичного интервального графа.
курсовая работа [1,5 M], добавлен 10.02.2017Нахождение минимального пути от фиксированной до произвольной вершины графа с помощью алгоритма Дейкстры, рассмотрение основных принципов его работы. Описание блок-схемы алгоритма решения задачи. Проверка правильности работы разработанной программы.
курсовая работа [495,4 K], добавлен 19.09.2011Алгоритм построения минимального остовного дерева. Последовательность выполнения алгоритма Прима, его содержание и назначение. Процедура рисования графа. Порядок составления и тестирования программы, ее интерфейс, реализация и правила эксплуатации.
курсовая работа [225,0 K], добавлен 30.04.2011Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.
презентация [430,0 K], добавлен 19.11.2013Восстановление графов по заданным матрицам смежности вершин. Построение для каждого графа матрицы смежности ребер, инцидентности, достижимости, контрдостижимости. Поиск композиции графов. Определение локальных степеней вершин графа. Поиск базы графов.
лабораторная работа [85,5 K], добавлен 09.01.2009Спектральная теория графов. Теоремы теории матриц и их применение к исследованию спектров графов. Определение и спектр предфрактального фрактального графов с затравкой регулярной степени. Связи между спектральными и структурными свойствами графов.
дипломная работа [272,5 K], добавлен 05.06.2014Общее понятие теоремы Эйлера, этапы ее доказательства. Необходимые и достаточные условия существования эйлерова цикла. Сущность задачи о построении каркаса куба. Алгоритм Флери построения эйлерова цикла. Обход полуэйлерова графа с нечетной вершины.
презентация [27,1 K], добавлен 12.04.2014Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке.
курсовая работа [1006,8 K], добавлен 23.12.2007Алгоритм перехода к графическому представлению для неориентированного графа. Количество вершин неориентированного графа. Чтение из матрицы смежностей. Связи между вершинами в матрице. Задание координат вершин в зависимости от количества секторов.
лабораторная работа [34,0 K], добавлен 29.04.2011Понятие "граф" и его матричное представление. Свойства матриц смежности и инцидентности. Свойства маршрутов, цепей и циклов. Задача нахождения центральных вершин графа, его метрические характеристики. Приложение теории графов в областях науки и техники.
курсовая работа [271,1 K], добавлен 09.05.2015Элементы теории графов. Центры и периферийные вершины графов, их радиусы и диаметры. Максимальный поток транспортировки груза и поток минимальной стоимости. Пропускная способность пути. Анализ сетей Петри, их описание аналитическим и матричным способами.
задача [1,3 M], добавлен 28.08.2010Понятие и внутренняя структура графа, его применение и матричное представление (матрица инциденций, разрезов, цикломатическая, Кирхгофа). Специальные свойства и признаки графов, решение оптимизационных задач. Венгерский алгоритм, матричная интерпретация.
курсовая работа [664,6 K], добавлен 24.12.2013
