3.2. Раскраска карт и графов.
О п р е д е л е н и е.
а)
Раскраской
называется задание цвета вершинам
так, что если
,
то
имеют различные цвета.
б)
Хроматическим числом
графа
называется минимальное число цветов,
требующееся для раскраски
//
Т е
о р е м а.
для всех планарных графов
//
Эта теорема была впервые «доказана» в 1976 г. проверкой на компьютере всех возможных случаев.
О п
р е д е л е н и е. Пусть
карта. Определим карту
называемую двойственной к
,
следующим образом: выберем внутреннюю
точку в каждой области
;
если две области имеют общее ребро, то
проведём дугу, связывающую выбранные
внутренние точки в этих областях. Этот
процесс определяет
.
//
П
р и м е р 3.5. На рис 7.14 изображена карта
вместе с двойственной картой
.
//
Рис. 7.14
Раскраска соответствует раскраске областей так, что области, имеющие общее ребро, имеют разные цвета. Следовательно, мы можем переформулировать теорему о раскрашивании в четыре цвета следующим образом.
Т е о р е м а. Если области карты необходимо раскрасить таким образом, чтобы смежные области имели различные цвета, то для этого требуется не более четырёх цветов. //
У п р а ж н е н и е 7.3.
1.
Пусть
дерево с
Доказать, что
2. Проверить справедливость формулы Эйлера для графов из упражнения 7.1, 1.
3.
Пусть
– планарный граф и
обозначает степень области
в карте
.
Доказать, что
4.
Пусть
– связный планарный граф и
.
Доказать, что
5.
Привести примеры, показывающие, что
приведённое в задаче 4 этого упражнения
неравенство неверно при
6.
Определить граф
,
для которого
.
7.
Пусть
– дерево. Что является значением
?
§ 4. Структуры данных для представления графа
Матрица
смежности предполагает очевидный метод
представления графа в машине – на языке
высокого уровня мы можем использовать
массив, чтобы хранить элементы матрицы.
Симметричность и нулевая диагональ
сокращают необходимый объём памяти;
для графа с n вершинами
требуется
ячеек. Обычно многие элементы матрицы
равны нулю и поэтому большая часть
используемой памяти является лишней,
однако, несмотря на это, иногда матрица
смежности является наиболее удобным
представлением графа. Однако для многих
задач предпочтительным является
представление в виде списка смежности.
В этом случае мы свяжем список связей
с каждой вершиной
;
является списком вершин, смежных с
.
Р
ис.
7.15
П р и м е р 4.1. На рис 7.15 даны граф и списки, которые могут быть использованы для его представления. //
Один из путей применения этих списков – это использование массивов
и
Где
хранит номера вершин,
хранит связь, а
– точки начала списка
в
.
П р и м е р 4.2. Для графа из примера 4.1 мы можем иметь ситуацию, изображённую на табл. 7.1.
Е
сли
не имеет смежных вершин, то установим
,
в противном случае
является смежной с
и
является ребром графа. Аналогично, если
,
тогда
является смежной с
.
Фрагмент программы, которая даёт список
смежных вершин к каждой вершине, выглядит
следующим образом:
Аналогичная программа может быть
использована для создания матрицы
смежности
графа из представления с помощью списка
связей
следующим образом:
,
do
Чтобы создать структуры и из , можно использовать следующую программу:
Возможно другое представление графов с помощью списка связей. Выбор представления во много зависит от используемых алгоритмов.
Представление вершин, смежных с , в виде списка связей определяет «порядок» рёбер, выходящих из . Рассмотрим это последнее утверждение и списки связей, данные в начале этого параграфа, по отношению к графу. Ребра упорядочены, как показано на рис. 7.16. Граф с упорядочиванием рёбер такого сорта упорядоченным графом. Дадим формальное определение.
О п
р е д е л е н и е. Множество
вершин вместе с множеством
упорядоченных списков упорядоченных
пар вершин называют упорядоченным
графом.
Необходимо наложить некоторые условия на списки , чтобы рассматриваемые структуры были графами. Эти условия следующие:
а)
для любого
;
б)
.
//
Граф, изображённый на рис 7.16, может быть записан в терминах упорядоченного графа следующим образом:
Упорядоченный граф определяет единственный неупорядоченный граф. Обратное утверждение неверно, поскольку в общем случае возможно много способов упорядочения графа. Некоторые из этих упорядочений рассматриваются в соответствии со следующим определением.
О п р е д е л е н и е. Два упорядоченных графа и называются эквивалентыми, если существует биекция между множествами вершин и биекция сохраняет списковую структуру. Другими словами, если
есть список рёбер , то
есть список рёбер . //
П р и м е р 4.3. Графы, изображённые на рис 7.17, эквивалентны, однако они не являются эквивалентными как упорядоченные графы. //
В
се
понятия § 2 (маршруты, замкнутые маршруты,
связность, дерево) переносятся очевидным
образом на упорядоченные графы.
Рис. 7.17
У п р а ж н е н и е 7.4.
1. Записать алгоритмы данного параграфа на каком либо языке программирования и проверить их работу на некоторых наборах данных.