Раскраски в теории графов
Правила раскраски графа, приписывание цветов его вершинам с условием, что никакие смежные вершины не получают одинакового цвета. Алгоритм приближенного решения задачи определения хроматического числа и построения минимальной раскраски произвольного графа.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 28.05.2019 |
| Размер файла | 1,6 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Приднестровский государственный университет им. Т.Г. Шевченко
Физико-математический факультет
Кафедра прикладной математики и информатики
КУРСОВАЯ РАБОТА
по дисциплине "Теория графов"
Раскраски в теории графов
Выполнила: студентка 110 гр.
Кушнир И.А.
Научный руководитель: ст. преподаватель
Старчук Т.И.
Тирасполь 2017
Содержание
- Введение
- 1. Теоретическая часть
- 1.1 Правильная раскраска
- 1.2 Оценки хроматического числа
- 1.3 Раскраска ребер
- 1.4 Хроматический полином
- 1.5 Теорема о пяти красках
- 1.6 Теорема четырех красок
- 1.7 Совершенные графы
- 1.8 Раскраски гиперграфов
- 1.9 Однозначно раскрашиваемые графы
- 1.10 Связь матроидных разложений графов с раскрасками
- 1.11 Где применяются графы?
- 2. Практическая часть
- Заключение
- Литература
Введение
Теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Графы буквально вездесущи. Особенностью этой теории является геометрический подход к изучению объектов.
В виде графов можно, например, интерпретировать схемы дорог и электрические цепи, географические карты и молекулы химических соединений, связи между людьми и группами людей.
На практике часто бывает полезно изобразить некоторую ситуацию в виде рисунков, составленных из точек (вершин), представляющих основные ситуации, и линий (ребер), соединяющих определенные пары этих вершин и представляющих связи между ними. Такие рисунки известны под общим названием графов.
В приложениях теории графом нередко возникают задачи, для решения которых необходимо разбить множество всех вершин графа в объединение непустых непересекающихся подмножеств таким образом, чтобы вершины из одного и того же множества были попарно не смежными, а число таких подмножеств - минимально возможным. Задачи раскраски вершин или ребер графа занимают важное место в теории графов. К построению раскрасок сводится целый ряд практических задач.
При решении таких задач можно представить себе, что мы раскрашиваем вершины графа в различные цвета, причем сделать это надо так, чтобы любые две смежные вершины были раскрашены в разные цвета, а число использованных цветов было минимально возможным.
Главной целью работы является научиться правильно применять теорию графов в повседневной жизни.
В данной курсовой работе я рассмотрела тему раскраски графов.
Для достижения цели необходимо решить следующие задачи:
· Найти и изучить литературу по данной теме
· Накопить и систематизировать полученную информацию по теме.
· Изучить основные понятия.
В работе использованы следующие методы исследования:
Работа насчитывает 28 страницы, состоит из введения, двух глав, заключения, библиографического списка используемой литературы, а также содержит 6 разобранных примеров.
1. Теоретическая часть
1.1 Правильная раскраска
Раскраской графа называется такое приписывание цветов его вершинам, что никакие две смежные вершины не получают одинакового цвета. Множество всех вершин одного цвета является независимым и называется одноцветным классом.
Пусть G - некоторый граф, k - натуральное число. Произвольная функция вида называется вершиной k-раскраской, или просто k-раскраской, графа G. Раскраска называется правильной, если для любых смежных вершин иГраф, для которого существует правильная k-раскраска, называется k-раскрашиваемым (или раскрашиваемым k цветами).В определении раскраски вместо множества {1, 2,.., k} можно взять произвольное k-элементное множество.
Правильную k-раскраску графа можно трактовать как окрашивание каждой его вершины в один из k цветов, при этом смежные вершины должны получать различные цвета. Поскольку функция f не обязательно сюрьективна, то при k-pacкpacкe фактически может быть использовано менее k цветов. Таким образом, правильную k-раскраску графа Gможно рассматривать как разбиение:
Множества вершин VG но более чем k непустых классов, каждый из которых является независимым множеством. Классы этого разбиения называются цветными классами.
Минимальное число k, при котором граф G является k-раскрашиваемым, называется хроматическим числом этого графа и обозначается (G) . Если ч(G) = k, то граф G называется k-хроматическим. Правильная k-раскраска графа G при k = (G) называется минимальной.
В качестве иллюстрации рассмотрим граф G, изображенный на рис. 1, где указана одна из правильных 4-раскрасок. Меньшим числом цветов этот граф раскрасить правильно нельзя. Действительно, граф содержит цикл (, для правильной раскраски которого нужно не менее трех цветов, а для вершины требуется новый цвет. Итак,(G)=4.
Граф является 1-хроматическим тогда и только тогда, когда он пустой, а 2-хроматическим - когда он двудольный и не пустой. Обычно 2-хроматический граф называют бихроматическим. Поэтому теорему Кёнига о двудольных графах можно сформулировать в следующем виде:k-непустой граф является бихроматическим тогда и только тогда, когда он не содержит циклов нечетной длины.
Задачи определения хроматического числа и построения минимальной раскраски произвольного графа являются очень сложными, эффективные алгоритмы их решения неизвестны. Рассмотрим простой алгоритм построения правильной раскраски, в ряде случаев приводящий к раскраскам, близким к минимальным.
Алгоритм последовательной раскраски
1. Произвольной вершине графа G припишем цвет 1.
2. Если вершины раскрашены l цветами 1, 2, …, l, l то новой произвольно взятой вершине припишем минимальный цвет, не использованный при раскраске вершин из ее окружения.
Раскраска, к которой приводит описанный алгоритм, называется последовательной. Очевидно, что это - правильная раскраска. Для некоторых классов графов (например, полных k - дольных) последовательная раскраска является минимальной. В общем случае это не так.
Следующая теорема сводит задачу построения правильной раскраски графов к аналогичной задаче для двухсвязных графов.
Теорема 1.1. Если каждый блок графа k-раскрашиваем, то и сам граф также k-раскрашиваем.
Воспользуемся индукцией по числу блоков рассматриваемого графа. Для графа, являющегося блоком, утверждение тривиально. Предположим, что теорема верна для графов, состоящий из блоков. Пусть теперь G - граф, имеющий ровно m+1 блоков, B - один из его концевых блоков, H- объединение всех остальных блоков. По индуктивному предположению оба графа B и H являются k- раскрашиваемыми. Зафиксируем для каждого из них правильною k- раскраску.
Графы B и H имеют ровно одну общую вершинуv. Если ее цвета в обеих фиксированных k- раскрасках совпадают, то получена правильная k - раскраска графа G. В противном случае нужно очевидным образом переставить цвета в одной из фиксированных раскрасок.
1.2 Оценки хроматического числа
Хроматическое число графа определяется как наименьшее k, для которого граф имеет k - раскраску. Граф называется k - раскрашиваемым, если, и k - хроматическим, если.
Обозначим через множество всех порожденных подграфов графа G, а через , как обычно, - минимальную из степеней вершин графаG.
Определение: Граф двуцветен тогда и только тогда, когда он не содержит нечетных простых циклов.
Похоже, что проблема характеризации k - цветных графов для k3 все еще не решена, поскольку такой критерий даже для k=3 помог бы решить гипотезу о четырех красок. Не найдены также эффективные методы определения хроматического числа произвольного графа. Однако известно несколько оценок для , в которых используются различные другие варианты. Одна очевидная нижняя оценка - это число вершин в наибольшем полном подграфе графа . Мы рассмотрим сейчас верхние оценки; первая такая оценка была получена Секерешем и Вилфом:
Теорема 2.1. Для любого графа G верно неравенство:
Утверждение теоремы для пустых графов. Пусть G- произвольный ч -хроматический граф, ч, а H - его минимальный порожденный подграф, удовлетворяющий условию ч(H)=ч. В этом случае ч(H-v)для любой вершины v графа II.
Предположим, что. Граф H-v правильно раскрасим ч-1 цветами. Окрасив затем вершину v в один из этих цветов, не использованный при окраске смежных с ней вершин, получим правильную (ч-1) - раскраску графа H. Следовательно,
и
Через обозначим наибольшую из степеней вершин графа G.
Следствие: Для любого графа G верно неравенство: ч(G)1+.
Теорема Брукса (1941г.). Если G - связный граф не являющимся полным, и то
Оценка, устанавливаемая теоремой Брукса, достижима. Так, для кубического графа G, изображенного на рис.2, существует правильная 3- раскраска, а правильная 2-раскраска невозможна, ибо это не двудольный граф. Следовательно, ч(G)=3=.
Однако теорема может дать и завышенную оценку хроматического числа. Например, из этой теоремы следует, что в то время как .
Две вершины графа называются соцветными относительно некоторой правильной раскраски, если при этой раскраске они имеют один цвет.
Следствие: При любой минимальной раскраске связного графа существуют две соцветные относительно этой раскраски вершины, расстояние между которыми равно 2.
Теорема (А.П. Ершов, Г.И. Кожухин, 1962)Для любого связного (n, m) - графа G верны неравенства:
.
(Напомним, что пара квадратных скобок означает целую часть числа, а пара фигурных скобок - дробную часть.)
Теорема 2.3. Существуют графы без треугольников с произвольным большим хроматическим числом.
Теорема 2.4. Для любых двух положительных целых чисел l и ч существует ч-хроматический граф, обхват которого превосходит l.
Оценим хроматическое число в терминах числа независимости.
Теорема 2.5. Для любого графа G верно:
(1)
где
Следствие: Если G - связный граф, не являющийся полным, и , то.
Теорема 2.6. Для любых натуральных чисел n, и ч, удовлетворяющих неравенствам (1), существует граф порядка n с числом вершинной независимости и хроматическим числом ч.
Гипотеза: Если и, то
Теорема 2.7. Хроматическое число почти каждого графа G порядка n удовлетворяет соотношению .
1.3 Раскраска ребер
Реберной k-раскраской графа G называется функция , ставящая в соотвествие каждому его ребру e число из множества {1, 2, …, k}. Если - реберная раскраска и, то говорят что ребро е окрашено в цвет с. Множество всех ребер, окрашенных в фиксированный цвет, называют реберным цветным классом. Реберная раскраска называется правильной, если смежные ребра имеют разные цвета. Граф, допускающий правильную реберную k - раскраску, называется реберно k - раскрашиваемым. Минимальное число k, при котором граф G является реберно k - раскрашиваемым, называется хроматическим индексом (хроматическим классом, реберным хроматическим числом) графа G и обозначается через .Если =k, то граф G называется реберно k- хроматическим.
Поскольку ребра любого графа смежны тогда, когда смежны соотвествующие вершины реберного графа , то можно определить как хроматическое число графа , т.е. .
При правильной реберной раскраске каждое множество ребер одного цвета являются паросочетанием. По этому число можно рассматривать как наименьшее число паросочетаний, на которые разбивается множество ребер графа .
Поскольку при любой правильной раскраске графа ребра, инцидентные одной вершине, имеют различные цвета, то Легко привести примеры, когда (см. рис.3).
Следующая теорема, принадлежащая В.Г. Визингу(1964г.), дает поразительные точные оценки хроматического числа индекса графа.
Теорема 3.1.Для любого графа G верны неравенства
Теорема 3.2.Справедливы равенства:
.
Теорема 3.3.Для любого двудольного графа G верно равенство:
.
Теорема 3.4. Для почти каждого графа G верно равенство:
.
Теорема 3.5. Гипотеза четырех красок справедлива тогда и только тогда, когда ч'(G)=3 для любого кубического планарного графа G, не содержащего мостов.
1.4 Хроматический полином
Хроматический многочлен графа введен Биркгофом и Льюисом, когда они предпринимали попытку решить гипотезу четырех красок. Поскольку t - раскраской графа G является произвольное отображение вида , то число попарно различных t - раскрасок этого графа равно числу всех таких отображений, т. е. , где . Количество попарно различных правильных t - раскрасок графа называется хроматической функцией графа и обозначается через Очевидно, что наименьшее из чисел , для которых , есть .
Для некоторых графов хроматическая функция определяется совсем легко. Например, , так как цвета всех вершин пустого графа можно выбирать независимо друг от друга. При правильной раскраске полного графа первая вершина может иметь любой из t заданных цветов, а для окраски каждой из последующих вершин разрешается использовать на один цвет меньше, чем для предыдущей. Поэтому
Итак, имеем:
Утверждение 1: Если - дизъюнктное объединение графов, то: f(G, t)=
Утверждение 2: Если и графы и имеют только одну общую вершину, то .
Утверждение 3: Пусть - две несмежные вершины графа . Если =, а получается из графа в результате слияния вершин , то .
Следствие: Хроматическая функция любого графа равна сумме хроматических функций некоторого числа полных графов, порядки которых не больше чем .
Поскольку - полином от , то верно:
Следствие: Хроматическая функция любого графа является полином от .
Поэтому хроматическую функцию обычно называют хроматическим полиномом графа .
Найдем с помощью утверждения 3 хроматический многочлен для графа изображенного на рисунке.
При этом вместо будем писать или рисовать соответствующие графы. На первом шаге получим ситуацию, представленную на рис. сверху. Далее смотрим следующий рисунок:
Итак,
Теорема 4.1. Хроматический полином любого (n, m)- графа , содержащего ровно k связных компонент, имеет вид:
где - целые неотрицательные числа.
Несомненный интерес представляет следующий вопрос, ответ на который пока не получен: каким условиям должен удовлетворять полином, чтобы он был хроматическим многочленом некоторого графа? Любопытно было бы найти условия, при которых хроматические многочлены графов совпадают. Примерами таких графов являются деревья, которые можно определить в терминах хроматических многочленов.
Теорема 4.2. Граф порядка n является деревом тогда и только тогда, когда
1.5 Теорема о пяти красках
Хотя не известно, все ли планарные графы 4 - раскрашиваемы, все они, несомненно, 5 - раскрашиваемы. Мы приведем доказательство этого неизвестного утверждения, принадлежащее Хивуду:
Теорема 5.1. Каждый планарный граф 5- раскрашиваем.
Доказательство: Будем доказывать индукцией по числу вершин. Для любого планарного графа с вершинами результат тривиален, поскольку такой граф с - раскрашиваем.
Допустим, что все планарные графы с вершинами () 5 - раскрашиваемы. Пусть - плоский граф с вершинами. В графе найдется вершина v степени 5 или менее. По предположению индукции плоский граф 5 - раскрашиваем.
Рассмотрим приписывание цветов вершинам графа ,при котором получается 5 - раскраска; цвета будем обозначать через Ясно, что если некоторый цвет, скажем , не используется в раскраске вершин, смежных с , то, приписав цвет вершине , получим 5 - раскраску графа .
Осталось рассмотреть случай, когда и для вершин графа , смежным с , используются все пять цветов. Переставим номера цветов, если это необходимо, так, чтобы вершины, смежные с и окрашенные в цвета были циклически упорядочены относительно . Пометим теперь вершину, смежную с и окрашенную цветом , буквой, .
Обозначим через подграф графа , порожденный всеми вершинами, окрашенными в один из цветов . Если вершины принадлежат различным компонентам графа , то 5 - раскраску графа можно получить, поменяв друг с другом () цвета вершин той компоненты графа , которая содержит . В этой 5 - раскраске уже нет вершин, смежных с и окрашенных в цвет ; поэтому, окрасив в цвет , образуем 5 - раскраску графа .
Если же вершины принадлежат одной и той же компоненте графа , то в между существует простая цепь, все вершины которой окрашены в цвета . Эта цепь вместе с цепь образует простой цикл, который обязательно окружает или вершину , или вершину . В любом из этих случаев нельзя соединить простой цепью, все вершины которой окрашены в цвета . Следовательно, рассматривая подграф графа , порожденный всеми вершинами, окрашенными в цвета , заключаем, что вершины принадлежат различным его компонентам. Таким образом, если поменять между собой цвета вершин в компоненте подграфа , содержащей получим 5 - раскраску графа , и в ней ни одна из вершин, смежных с , не будет окрашена в . Поэтому, окрасив вершину в цвет , образуем 5 - раскраску всего графа .
1.6 Теорема четырех красок
Наиболее известная задача в теории графов и, возможно, во всей математике - знаменитая проблема четырех красок. Эту замечательную задачу каждый математик в течении пяти минут может объяснить любому прохожему на улице. В конце объяснения оба будут хорошо понимать проблему, но не будут способны ее решить.
В следующей цитате из исторической статьи Мея формулируется теорема о четырех красок и поясняется ее роль:
"Предполагается, что любую карту на плоскости или поверхности шара можно раскрасить только четырьмя красками таким образом, чтобы никакие две смежные страны не были одного и того же цвета. Каждая страна должна состоять из одной связной области, а смежными называются страны, которые имеют общую границу в виде линии (а не просто одной общей точки). На протяжении более чем половины столетия многие математики предпринимали попытки решить эту проблему, но смогли доказать справедливость гипотезы только для отдельных случаев… Кажется, что ей на некоторое время предназначено сохранить отличительную черту быть одновременно и наиболее простой, и наиболее заманчивой нерешенной проблемой математике."
Теорема четырех красок являлось проблемой теории графов, потому что каждая карта порождает граф, в котором страны (включая внешнюю область) - это вершины и две вершины соединяются ребром, если соответствующие им страны смежны. Таким образом, удалось показать, что вершины любого планарного графа можно раскрасить четырьмя или меньшим числом красок так, чтобы смежные вершины имели разные цвета.
В 1976 году Кенет Аппель и Волфган Хакен из Иллинойского университета доказали, что так можно раскрасить любую карту. Это была первая крупная математическая теорема, для доказательство которой был применен компьютер. Несмотря на последующие упрощения, доказательство практически невозможно проверить, не используя компьютер. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств (741 страница); в последствии были предложены более компактные алгоритмы и скорректирован ряд ошибок. Новое доказательство, основанное на алгебраических и топологических методах, дал индийский математик Ашей Дарвадкер в 2000 году.
Определение: Раскраской плоской карты G называется такое приписывание цветов областям в G, что никакие две смежные вершины области не получаются одинакового цвета.
Теорема четырех красок: Каждый планарный граф 4 - раскрашиваем.
Предположим, что теорема четырех красок справедлива, и возьмем произвольную плоскую карту G. Пусть G* - граф, являющийся основной карты, геометрически двойственной к карте G. Так как две области карты G смежны тогда и только тогда, когда соответствующие им вершины графа G* смежны, то карта G 4 - раскрашиваема, поскольку граф G* 4 - раскрашиваем.
Легко привести примеры планарных 4 - хроматических графов. Таковы графы , изображенные на рис. В каждом из этих графов не менее четырех треугольников, что является в силу теоремы необходимым условием 4 - хроматичности.
Теорема 6.1. Каждый планарный граф, имеющий меньше четырех треугольников, 3 - раскрашиваем.
Следствие: Каждый планарный граф, не содержащий треугольников, 3 - раскрашиваем.
Теорема 6.2. Теорема четырех красок справедлива тогда и только тогда, когда каждая кубическая плоская карта, не имеющая мостов, 4 - раскрашиваема.
Другую интересную эквивалентную форму теоремы четырех красок предложил Уитни.
Теорема 6.3. Теорема четырех красок справедлива тогда и только тогда, когда любой гальмитонов планарный граф 4 - раскрашиваем.
Наряду с эквивалентами теоремы четырех красок, в которых говорится о раскраске областей, существует также эквивалент, в котором рассматривается раскраска ребер.
Теорема 6.4. Теорема четырех красок справедлива тогда и только тогда, когда ч'(G)=3 для любого кубического планарного графа G, не содержащего мостов.
Теорема 6.5. Для того чтобы связная планарная карта G была 4 - раскрашиваема, необходимо и достаточно, чтобы граф можно было представить в виде суммы таких трех подграфов что для любой вершины v числа ребер из каждого подграфа , инцидентных v, были либо все четные, либо все нечетные.
Теорема 6.6. Каждый связный k - хроматический граф стягиваем к
Теорема 6.7. Теорема Хадвигера для k=5 эквивалентна теореме четырех красок.
В связи с теоремой четырех красок Г. Биркгоф в начале века поставил вопрос: какими свойствами должны обладать минимальные плоские графы, вершины которых нельзя правильно раскрасить четырьмя красками? Такие графы называются неприводимыми. Далее изучались графы, их называли приводимыми конфигурациями, которые не являются подграфами неприводимых графов.
Пусть - некоторая поверхность, любая карта на которой допускает раскраску ч цветами, и существует карта на , не допускающая раскраску ч цветами. Тогда ч называется хроматическим числом поверхности S.
Теорема 6.8. Если - сфера сp>0 ручками, то:
.
Пусть теперь - произвольный связный граф, каждому ребру которого поставлена в соответствие переменная . Получим систему уравнений , записав соотношение вида
для каждого цикла графа , и систему - для каждого цикла из некоторого фиксированного базиса циклов.
Лемма: Каждому решению системы при фиксированной окраске некоторой вершины однозначно соответствует правильная раскраска графа четырьмя цветами.
Так как граф может содержать большое число циклов, то перейдем от системы уравнений к системе .
Теорема 6.9. Каждому решению системы при фиксированной окраске некоторой вершины однозначно соответствует правильная раскраска графа четырьмя цветами.
Теорема 6.10. Плоский двусвязный граф является бихроматическим тогда и только тогда, когда граница каждой его грани содержит четное число ребер.
Утверждение: Карта является 2 - раскрашиваемой тогда и только тогда, когда граф эйлеров.
Теорема 6.11. Плоский граф 3 - раскрашиваем тогда и только тогда, когда он является подграфом плоской триангуляции с четными степенями вершин.
Теорема 6.12. Любой плоский граф, содержащий менее четырех 3 - циклов, 3 - раскрашиваем.
1.7 Совершенные графы
Как отмечалось выше, хроматическое число и плотность любого графа удовлетворяют очевидному неравенству . При этом разность может быть как угодно велика. В этом параграфе изучаются графы, обладающие тем свойством, что хроматическое число и плотность не только самого графа, но и каждого его порожденного подграфа, равны.
Граф называется совершенным, если для любого его порожденного подграфа .
Из этого определения непосредственно вытекает, что всякий порожденный подграф любого совершенного графа является совершенным.
Очевидно, что все полные и пустые графы совершенны. Примером совершенного графа может служить также каждый двудольный граф, поскольку для любого его подграфа либо (если непустой), либо (при пустом ).
Совершенные графы введены К. Бержем в 1960г. Интерес к этим графам связан прежде всего с двумя обстоятельствами. Во-первых, многие трудно разрешимые в общем случае задачи теории графов успешно решаются для совершенных графов. Во-вторых, ряд широко известных классов графов содержится в классе совершенных. Таковы, например, все двудольные, пороговые, расщепляемые и триангулированные графы.
Теорема 7.1. Граф, дополнительный к совершенному графу, также является совершенным.
Лемма: Следующие два утверждения равносильны:
1. Граф является совершенным;
2. В любом непустом порожденном подграфе графа есть такое независимое множество вершин A, что .
Пусть произвольные графы. Будем считать их множество вершин не пересекающимся и следующим образом определим новый граф . Отметим произвольную вершину графа и положим Вершины графа будем считать смежными, если выполняется одно из следующих трех условий:
1.
2.
3.
Скажем, что граф получается из графа в результате замены вершины v графом H.
Лемма: Граф, полученный из совершенного графа в результате замены вершин совершенными графами, также являются совершенными.
Лемма: В любом совершенном графе Gесть клика, пересекающая каждое наибольшее независимое множество вершин графа G.
Теорема 7.2. Пусть A - матрица клик графа . Тогда для того, чтобы граф был совершенным, необходимо и достаточно выполнение равенства.
Легко видеть, что условием, необходимым для того, чтобы граф был совершенным, является отсутствие в нем порожденных простых циклов нечетной длины . В самом деле, если такой цикл, то Из теоремы вытекает, что таких циклов не должен содержать и граф, дополнительный к совершенному. В 1962 году К. Берж высказал предположение, что эти два условия не только необходимы, но и достаточны для того, чтобы граф был совершенным.
Сильная гипотеза Бержа: Граф является совершенным тогда и только тогда, когда ни он, ни его дополнение не содержит порожденных подграфов вида
1.8 Раскраски гиперграфов
Так же, как для графов, вводится понятие вершиной раскраски гиперграфов. Раскраска вершин гиперграфов называется правильной, если любое ребро содержит две вершины, окрашенные в различные цвета. Ясно, что правильную раскраску могут допускать лишь гиперграфы, каждое ребро которых имеет степень не меньше чем 2. Кроме того, будем считать, что изолированных вершин гиперграф не содержит.
Гиперграф называется k - раскрашиваемым (k - цветным), если для него существует правильная раскраска в kцветов.
Хроматическое число - это наименьшее число цветов, достаточное для правильной раскраски гиперграфа . Если , то гиперграф называется k - хроматическим.
Очевидно, что разбиению множества на независимые множества соответствует правильная раскраска вершин гиперграфа цветами. Верно, конечно, и обратное утверждение.
Теорема 8.1. Для любого гиперграфа порядка n справедливы неравенства:
где - число независимости гиперграфа .
Важное место в теории графов занимают верхние оценки хроматического числа в терминах степеней вершин. При естественном определении степеней вершин сохраняет силу теорема Брукса. При другом определении, которое мы дадим ниже, получается более тонкая оценка хроматического числа, полученная И. Томеску.
Так же, как и для графов, через
Абсолютным гиперграфов будем называть гиперграф, для любых двух вершин которого существует ребро Оказывается, справедлива следующая теорема:
Теорема 8.2. Если - связный гиперграф, отличный от абсолютного, и то .
Теорема 8.3.Пусть - разбиение множества на независимые множества. Тогда:
где .
Следствие: Для любого гиперграфа верно неравенство
На первый взгляд кажется, что наличие ребер высокой степени должно способствовать снижению хроматического числа гиперграфа. Однако это не так, как показывает следующая теорема:
Теорема 8.4. Для любых целых чисел и существует такой гиперграф , что и для любого ребра
Теорема 8.5. Для любых целых чисел k, h, l существует h - однородный k - хроматический гиперграф, который не содержит циклов длины меньше l.
Известно, какую роль в теории графов играют бихроматические графы, т.е. графы, хроматическое число которых не превосходит 2. Простой, но очень важный критерий бихроматичности графа дал Д. Кёниг: граф не должен содержать циклов нечетной длины.
Гиперграф тоже будем называть бихроматическим, если . Для гиперграфа пока не найдено критерий бихроматичности в терминах его структуры.
Утверждение: Если гиперграф не содержит циклов нечетной длины, то он является бихроматическим.
Более широкий класс бихроматических графов нашли Фурнье и Лас Верньяс.
Теорема 8.6. Если в каждом цикле нечетной длины гиперграфа есть три ребра, имеющие общую инцидентную вершину, то гиперграф является бихроматическим.
Утверждение: Если гиперграф является бихроматическим, то он не содержит ни одного цикла нечетной длины, состоящего лишь из ребер степени 2.
1.9 Однозначно раскрашиваемые графы
Пусть - помеченный граф. Каждая его ч() - раскраска порождает разбиение множества его вершин на ч() одноцветных классов. Если ч() = и каждая - раскраска графа порождает одно и то же разбиение множества , то называется однозначно - раскрашиваемым, или просто однозначно раскрашиваемым.
Граф, представленный на рисунке однозначно 3 - раскрашиваем, так как каждая его 3 - раскраска дает разбиение . Пятиугольник не однозначно 3 - раскрашиваем: возможны пять различных разбиений множество его вершин.
Начнем с элементарных замечаний, касающихся однозначно раскрашиваемых графов. Прежде всего, в любой - раскраске однозначно - раскрашиваемого графа каждая вершина смежна по крайней мере с одной вершиной каждого цвета, отличного от цвета, приписанного . Иначе можно было бы получить другую - раскраску графа , перекрасив вершину . Отсюда следует, что . Необходимое условие однозначной раскрашиваемости графа найдено Картрайтом и Харари.
Теорема 9.1. В n - раскраске однозначно n - раскрашиваемого графа подграф, порожденный объединением любых двух одноцветных классов, связен.
Теорема 9.2. Каждый однозначно n - раскрашиваемый граф - связен.
Следствие: В каждой - раскраске однозначно n - раскрашиваемого графа подграф, порожденный объединением любых двух одноцветных классов, - связен.
Легко привести примеры 3 - хроматических графов, не содержащих треугольников.
Теорема 9.3. Для каждого существует однозначно - раскрашиваемый граф, не содержащий подграфов, изоморфных .
Граф , приведенный на рисунке, иллюстрирует теорему для случая =3.
Теорема 9.4. Пусть есть 3 - хроматический плоский граф. Если содержит такой треугольник , что для любой вершине графа существует последовательность треугольников, в которой соседние два имеют общее ребро и , то - однозначно 3 - раскрашиваемый граф.
Из этой теоремы немедленно вытекает
Следствие: Если двусвязный граф 3 - хроматический плоский граф имеет более одной области, не являющейся треугольником, то - однозначно 3 - раскрашиваемый граф.
Предположение, обратное следствию не верно: однозначно 3 - раскрашиваемый планарный граф может иметь более одной области, не являющейся треугольником. Однако каждый однозначно 3 - раскрашиваемый планарный граф должен содержать треугольники.
Теорема 9.5. Однозначно 3 - раскрашиваемый планарный граф, имеющий не менее 4 вершин, содержит по крайней мере два треугольника.
В случае однозначно 4 - раскрашиваемых планарных графов ситуация особенно просто.
Теорема 9.6. Каждый однозначно 4 - раскрашиваемый планарный граф является максимальным планарным графом.
Вопрос существования 5 - раскрашиваемых планарных графов остается все еще открытым, результат Хедетниеми, приведенный в работе Чартрэнда и Геллера, разрешает проблему однозначно 5 - раскрашиваемости.
Теорема 9.7. Ни один из планарных графов не является однозначно 5 - раскрашиваемым.
1.10 Связь матроидных разложений графов с раскрасками
Отметим простые связи, существующие между матроидными разложениями графов и раскрасками. Напомним, что матроидным разложением графа называется представление его в виде объединения: , М - графов, т.е. графов, все связные компоненты которых суть полные графы; минимальное число компонент в матроидных разложениях графа - матроидное число .
Зафиксируем правильную раскраску ребер и рассмотрим разбиение множества ребер на цветные классы:
. (1)
Очевидно, что граф , для которого , является М - графом, и (2)
- матроидное разложение. Итак, разбиение на цветные классы (1) определяет матроидное разложение (2) графа . Тем самым доказано.
Утверждение: Для любого графа верно неравенство
Утверждение: Если граф не содержит треугольников, то . Для любого двудольного графа верно неравенство .
Утверждение: Для любого графа справедливо неравенство .
В качестве иллюстрации рассмотрим граф , изображенный на рисунке, для него , , .
Утверждение: Для произвольного графа равентсва, и равносильны.
Если , то . Но при никакие две максимальные клики графа не не пересекаются, и потому - пустой граф, . Итак, при и
Остается доказать истинность импликации .
Доказательство основано на следующей очевидной комбинаторной лемме.
Лемма: Пусть - конечное множество, каждому из элементов которого приписан один из двух фиксированных цветов или оба эти цвета. Если для любой пары элементов множество существует общий приписанный им цвет, то тогда и все элементы множества имеют общий приписанный им цвет.
Пусть теперь - матроидное разложение графа Достаточно доказать, что любой полный подграф графа целиком содержится в каком-либо из ; если это так, то разложение определяет правильную 2 - раскраску графа клик и истинность импликации доказана.
Каждому из ребер графа следующим образом припишем один из цветов{1,2} или оба эти цвета. Именно, всем ребрам графа приписывается цвет . Пусть теперь - клика графа , .
Если ребра смежны, то в порожденном подграфе существует третье ребро , смежное с ним обоими. Какие-то два из этой тройки ребер имеющий цвет, поскольку цветов только два. Но концы этих трех ребер вместе входят в одну из связных компонент графа , являющихся полными графами, следовательно, и третье ребро имеет тот же цвет. Итак, для любой пары смежных ребер графа существует общий приписанный им цвет.
Если же ребра и не смежны, то в графе есть еще четыре ребра , смежных из этих ребер существует общий цвет, откуда вытекает, что существует цвет, общий для ребер
Доказано, что любые два ребра графа имеют общий цвет. В силу леммы существует общий цвет, например 1, приписанный всем ребрам графа . Последнее означает, что содержится в одной из компонент графа .
Из утверждения вытекает: Если , то и .
1.11 Где применяются графы?
Графы заинтересовали меня своей возможностью помогать в решении различных головоломок, математических и логических задач. Я решила разобраться какую роль в обычной жизни играют графы.
С помощью графов упрощается решение математических задач, головоломок, задач на смекалку.
Лабиринт - это граф. А исследовать его - это найти путь в этом графе.
Другое применение раскраски в графах может быть использовано при:
· распределение памяти в ЭВМ;
· проектирование сетей телевизионного вещания;
· распределение частот и областей сотовых систем связи.
Задача об определении минимального числа красок, нужных для правильной раскраски графа.
Графами являются сетевые графики строительства.
Типичными графами на географических картах являются изображения железных дорог, схемы движения городского транспорта, схемы авиалиний.
Графом является и система улиц города. Его вершины - площади и перекрестки, а ребра - улицы.
Графы есть и на картах звездного неба.
Практическая часть графов очень велика. Многие люди даже не подозревают, что практически каждый день пользуются этим понятием и его свойствами. Довольно широка область практического применения графов в окружающем нас мире.
2. Практическая часть
Рассмотрим некоторые практические задачи, сводящиеся к правильной раскраске графов.
1. Задача составления расписаний.
Предположим, что нужно прочесть несколько лекций за кратчайшее время. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно (например, их читает один и тот же лектор). Построим граф , вершины которого биективно соответствуют лекция, и две вершины смежны тогда и только тогда, когда соответствующие лекции нельзя читать одновременно. Очевидно, что любая правильная раскраска этого графа определяет допустимое расписание: лекции, соответствующие вершинам графа, составляющим цветной класс, читаются одновременно. И, обратно, любое допустимое расписание определяет правильную раскраску графа Оптимальные расписания соответствуют минимальным раскраскам, а число часов, необходимое для прочтения всех лекций, равно ч().
2. Задача распределения оборудования.
Заданы множества и работ и механизмов соответственно. Для выполнения каждой из работ требуется некоторое время, одинаковое для всех работ, и некоторые механизмы. При этом никакой из механизмов не может быть одновременно занят в нескольких работах. Нужно распределить механизмы так, чтобы общее время выполнения всех работ было минимальным.
...Подобные документы
Алгоритм, использующий метод Магу-Вейссмана. Общие сведения, описание, вызов и загрузка, функциональное назначение и программный код программы. Описание логической структуры и инструкция пользователю, решение контрольных примеров раскраски графа.
курсовая работа [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
