4. Требования к содержанию и оформлению отчета

Отчет должен включать:

- задание на выполнение работы;

- описание этапов выполнения работы в соответствии с заданием;

- выводы по работе;

- перечень использованной литературы.

Работа должна быть оформлена в соответствии с требованиями ГОСТов /6/.

Форма титульного листа дана в приложении 5.

5. Литература

1. Горбатов В.А. Основы дискретной математики - М.: Высшая школа, 1986

2. Акимов О.Е. Дискретная математика - М.: Лаборатория Базовых Знаний, 2001

3. Абрайтис Л.Б. Автоматизация проектирования топологии цифровых интегральных

микросхем – М.: Радио и связь, 1985

4. Харари Ф. Теория графов– М.: Мир, 1973

5. Кристофидес Н. Теория графов, алгоритмический подход – М.: Мир, 1978

6. Соболева Н.В. Методические указания по оформлению курсовых работ, курсовых

и дипломных проектов - Ижевск: ИжГТУ, 2003

7. Новиков Ф.А. Дискретная математика для программистов – Санкт-Петербург:

Питер, 2001

ПРИЛОЖЕНИЕ 1

НАПРАВЛЕННЫЕ ГРАФЫ

Направленный (ориентированный) граф D состоит из конечного непустого множества вершин V=V_D и конечного множества направленных рёбер E=E_D, которые производят отображение δ: E→V×V. Если δ (e) = (υ, ω), то υ называется начальной вершиной, а ω - конечной вершиной ребра e /2/.

Для направленного графа D можно путём отмены направленности рёбер получить соответствующий ненаправленный граф Г, который называется нижним для графа D.Формально, нижний для графа D граф имеет те же вершины и рёбра, но последний утрачивает свою направленность.

Направленный граф называется простым, если он не содержит петель (т. е рёбер e, для которых δ (e) = (υ, υ)) и не содержит множественных рёбер (т.е с одинаковыми начальной и конечной вершинами).

На рис. П1.1 показаны простой направленный и нижний для него графы. Два ребра направленного графа, связывающие вершины υ₄ и υ₅ , не являются множественными, так как их направления различны, т.е у них разные начальные и конечные вершины. В то же время, соответствующий нижний граф не является простым, так как он имеет множественные рёбра.

рис. П1.1

Многие определения для ненаправленных графов могут быть перенесены на направленные графы с учётом необходимых модификаций. В частности, определения смежности, инцидентности и валентности остаются неизменными. Так, например, две вершины υ и ω направленного графа будут смежными, тогда и только тогда, когда существует направленное ребро либо из υ в ω, либо из ω в υ. Однако, мы должны модифицировать определение матриц смежности для направленного графа с целью учёта направленности рёбер.

Элемент (i, j) матрицы смежности направленного графа представляет собой число рёбер с начальной вершиной υ_i и конечной вершиной υ_j, поэтому матрица может и не быть симметричной.

Для направленного графа валентность (степень) вершины равна сумме элементов в соответствующей строке плюс столбец матрицы смежности. Элементы в строке, отвечающей вершине «υ», представляют собой рёбра, начинающиеся в вершине «υ», элементы в столбце, отвечающей вершине «υ», представляют собой рёбра, заканчивающиеся в вершине «υ». Сумма всех элементов матрицы смежности равна сумме всех рёбер направленного графа.

Для направленного графа последовательностью направленных рёбер из υ₀ в υ_n называется последовательность рёбер e₁,e₂, … ,e_n таких, что δ(e_i) = (υ_i-1,υ _i) для i=1,2,…,n.

Направленный граф называется связным (или слабо связным), если его нижний ненаправленный граф является связным. Направленный граф называется сильно связным, если для каждой упорядоченной пары вершин (υ ,ω) существует направленный путь

из υ в ω.

Пример. На рис. П1.2 показаны направленные графы, у которых одинаковые нижние ненаправленные графы. Граф (а) не является сильно связным, так как, например, нет пути из υ в ω, или, формально, мы не можем перейти из υ в ω вдоль рёбер в направлении стрелок. Граф (b) является сильно связным, так как мы можем перейти из любой вершины в любую другую вершину в результате движения вдоль стрелок рёбер.

ω

ω

(а) (b)

Рис. П1.2

ПРИЛОЖЕНИЕ 2

ВЛОЖЕНИЕ ГРАФОВ

Определим, является ли граф планарным, можно ли осуществить однослойную печать и если нет, то установим, сколько потребуется слоев и какие ребра следует удалить, чтобы граф стал планарным.

Исходный граф G приведен на рис. П2.1.

Рис. П2.1

Попытаемся сделать граф планарным (рис.П2.2).

• Граф является планарным, если изображается на плоскости так, что его ребра пересекаются только в вершинах /1/.

Рис. П2.2

Полученный граф не является планарным, так как после преобразований ребро {6, 3} пересекает ребро{5, 7}.

Для доказательства того, что граф непланарный, используем критерий Понтрягина.

Теорема Понтрягина (критерий Понтрягина): граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных F₅ или К ₃₃.

F₅ - полный граф на пяти вершинах, К ₃₃ - двудольный граф на шести вершинах.

Два графа называются гомеоморфными, если они изоморфны с точностью до вершин степени 2, или они преобразуются до графов, изоморфных друг другу заменой некоторых ребер цепями соответствующей длины.

Найдем эти подграфы (рис.П2.3 и рис.П2.4).

2

3

7

4

6

5

Рис. П2.3

Полученный подграф, гомеоморфный F₅ (при стягивании ребра {5,7} или {5,4} получим граф F₅).

2

• 6

6

5

1

3

4

7

Рис. П2.4

Полученный подграф, гомеоморфный К₃₃ (при стягивании ребра {7,5} или {5,4} получим граф К₃₃).

Вычислим толщину графа.

• Толщиной графа называется наименьшее число планарных графов, объединение которых дает исходный граф.

_, где n – мощность; S_i – степень i-ой вершины; - целая часть.

Для данного графа имеем:

Таким образом, получили, что необходимо два слоя, чтобы разместить граф на плоскости без пересечения его ребер.

• Чтобы определить, какие ребра необходимо удалить для преобразования графа в планарный, выделим все запрещенные фигуры и построим двумерную таблицу, каждая строка которой взаимно однозначно соответствует запрещенной фигуре Q_i; столбец соответствует ребру (табл. П2.1). Тогда покрытие строк столбцами этой таблицы определит, какие ребра необходимо удалить для приведения графа к планарному виду.

Минимальное покрытие будет соответствовать минимальному решению, так как удаление любого ребра выводит запрещенную фигуру из класса подграфов, гомеомор-фных F₅ или K_33.

Таблица П2.1

Qi	{1,2}	{2,6}	{2,3}	{1,6}	{6,7}	{1,7}	{2,4}
Q1	0	1	1	0	1	0	1
Q2	1	0	1	1	0	1	1

Qi	{2,7}	{3,6}	{3,7}	{3,4}	{4,6}	{4,5}	{5,7}
Q1	1	1	1	1	1	1	1
Q2	0	1	1	0	1	1	1

Таким образом, минимальное покрытие содержит одно из ребер:

{2,3}, {2,4}, {3,6}, {3,7}, {4,6}, {4,5}, {5,7}

Например, после удаления ребра {3,6} получаем планарный граф.

Соединение, которое соответствует удаленному ребру, реализуется на второй плоскости.

Толщина графа G равна 2.

ПРИЛОЖЕНИЕ 3

ПЛОСКАЯ УКЛАДКА ГРАФА В УЗЛЫ РЕШЕТКИ

Множество вершин графа может состоять из подмножеств вершин, отображающих элементы топологии. Изобразим граф G, в котором используется 3 типа вершин: терминальные вершины G_b, элементные вершины G_c и вершины G_e, отображающие электрические цепи /3/.

Исходный граф представлен на рис.П3.1.

Рис П3.1

Обозначения:

- Отображает терминальные вершины G_b

- Отображает элементные вершины G_c

- Отображает электрические цепи G_e

- Псевдовершины, т.е. отображает пересечение ребёр соединений и ребёр решётки.

Планарный граф требуется уложить в прямоугольную решётку.

Параметры решётки:

m – число горизонтальный линий

n – число вертикальных линий m и n определяются как минимальные величины, удовлетворяющие условиям:

m  n  | G_c | + | G_b | Площадь кристалла

2(m + n) – 4  | G_b | Число внешних контактных площадок (1)

m ≤ n ≤ m + 1 Квадратичность кристалла

Алгоритм

1. Определим по исходному графу мощность | G_b |, | G_c |, | G_e |:

| G_b | = 3

| G_c | = 11

| G_e | = 8

2. Подставим полученные значения в систему (1) и упростим её:

m  n  14

2(m + n) – 4  3

m ≤ n ≤ m + 1

m  n  14

m + n  3,5 (2)

n ≤ m + 1

n ≥ m

3. Найдем минимальные значения m и n (табл. П3.1), удовлетворяющие системе (2):

Таблица П3.1

m	2	2	3	3	4	4
n	2	3	3	4	4	5
m  n	4	6	9	12	16	20

Для удобства расположения графа в узлах решётки возьмем m=4 и n=5. В этом случае пересечений не должно быть.

2. Выполним укладку исходного планарного графа в узлы прямоугольной решётки (рис.П3.2).

Рис. П3.2

Приложение 4

РАСКРАСКА ГРАФОВ

Определение. Пусть G=(V,E) – обыкновенный граф и k – натуральное число. Функция f: V{1,…,k} называется раскраской графа. Раскраска называется правильной, если для любых смежных вершин x,yV справедливо неравенство f(x)  f(y). Число k – число красок раскраски f / 5/.

Мы, как правило, будем представлять себе, что мы раскрашиваем вершины некоторым набором красок (в количестве k штук). Правильность раскраски означает, что смежные вершины раскрашиваются в разные цвета.

Определение. Наименьшее число красок, необходимое для правильной раскраски графа G, называется хроматическим числом графа G. Правильную раскраску таким числом красок будем называть оптимальной.

Хроматическое число обозначается через h (G). Рассмотрим примеры графов, изображенных на рис. П4.1.

Рис. П4.1

Оба графа содержат трехэлементный полный подграф К₃, поэтому для правильной раскраски необходимо, по крайней мере, три краски. Для графа G₁ этого достаточно (см. рис. П4.1). Граф G₂ имеет цикл длины 5. Нетрудно понять, что для правильной раскраски вершин цикла необходимо три краски. Но центральная вершина графа G₂ смежная со всеми вершинами цикла, поэтому для правильной раскраски графа понадобится четвертая краска (см. рис. П4.1). Итак, h (G₁)=3 и h (G₂)=4.

Очевидно, что если компоненты связности графа G правильно раскрасить k красками, то и сам граф окажется правильно раскрашенным этими красками. Отсюда следует, что если G₁,G₂,…,G_c – все компоненты связности графа G, то

h (G)=max{ h (G₁), h (G₂),…, h (G_c)}.

Оказывается, что аналогичное утверждение справедливо и для компонент двусвязности.

Теорема 1. Пусть любой блок графа G можно правильно раскрасить k красками. Тогда и сам граф G можно правильно раскрасить k красками /4/.

Приведем примеры задач, которые сводятся к нахождению хроматического числа и соответствующей оптимальной раскраски.

Задача составления расписаний. Предположим, что в учебном центре надо провести несколько занятий за кратчайшее время. Длительность всех занятий одинакова, скажем, один час. Некоторые занятия не могут проводиться одновременно, например, это занятия в одной и той же учебной группе (по разным предметам), или занятия проводит один и тот же преподаватель. Для решения задачи построим граф G, вершинам которого биективно соответствуют занятия. Две вершины соединены ребром, если соответствующие занятия нельзя проводить одновременно. Ясно, что правильная раскраска графа G определяет расписание, удовлетворяющее требованиям несовместимости по времени: занятия, соответствующие вершинам, окрашенным одинаково, можно проводить одновременно. Справедливо и обратное, любое такое расписание определяет правильную раскраску графа G. Следовательно, кратчайшее время, необходимое для проведения всех занятий, равно h (G), а из оптимальной раскраски графа G получается необходимое расписание.

Задача распределения ресурсов. Необходимо выполнить некоторое множество V={v₁,v₂,…,v_n} работ. Имеется множество S={s₁,s₂,…,s_r} ресурсов, необходимых для выполнения этих работ. Каждая работа использует часть указанных ресурсов, одновременно могут выполняться работы, использующие разные ресурсы. Все работы выполняются за одно и то же время t. Необходимо распределить ресурсы так, чтобы общее время выполнения всех работ было минимальным.

Рассмотрим граф G с множеством вершин V. Две различные вершины v и v’ графа G смежные тогда и только тогда, когда для выполнения работ v и v’ требуется хотя бы один общий ресурс. Наименьшее время выполнения всех работ равно h (G) ·t. Оптимальная раскраска графа G определяет распределение ресурсов.

Как мы видели выше, при решении ряда практических задач необходимо уметь вычислять хроматическое число графа. Естественно попытаться найти формулу, которая выражала бы хроматическое число через «привычные» величины: число вершин, ребер, компонент связности, степени вершин. Однако несложные примеры показывают, что такой формулы нет. Рассмотрим графы, изображенные на рис. П4.2.

Рис. П4.2

У этих графов одно и то же число вершин, ребер, компонент связности. Распределение степеней вершин тоже совпадает: четыре вершины имеют степень 4, остальные – степень 2. Однако хроматическое число первого графа равно четырем, а второго – двум.

Если нет формулы, позволяющей точно вычислить хроматическое число, то можно попытаться найти приемлемые оценки для этого числа.

Рассмотрим вначале нижние оценки для h (G).

Начнем с оценки, связанной с плотностью графа.

Определение. Плотностью p (G) графа G называется наибольшее число вершин полного подграфа графа G.

Следующее утверждение очевидно.

Предложение 1. Для любого графа G выполняется неравенство

p (G) ≤ h (G).

Для графов, изображенных на рис.2, это неравенство превращается в равенство. Однако, как показывает следующее, утверждение разность между h (G) и p (G) может быть сколь угодно большой.

Теорема 2. Для всякого k ≥ 2 существует граф G такой, что p(G)=2 и h (G)=k.

Определение. Множество попарно несмежных вершин графа называется независимым множеством. Вершинным числом независимости (G) графа G называется наибольшее число вершин независимого множества.

Так для графов G₁ и G₂, изображенных на рис. 1, получаем, что (G₁) =3, (G₂) =2.

Предложение 2. Для любого графа G выполняется неравенство

n / (G)h (G),

где n = .

Предложение 3. Для любого графа G выполняется неравенство

n²/(n² – 2m) h (G),

где m =.

Отметим, что для полного графа 2m=n(n-1), поэтому для произвольного графа

n²–2m>0 /5/.

Из верхних оценок укажем одну, приведенную в теореме 3, которую часто называют теоремой Брукса. (Теорема доказана Бруксом в 1941г.) Через (G) обозначим наибольшую степень вершин графа G.

Теорема 3. Пусть G=(V,E) – связный неполный граф и (G)3. Тогда h(G) (G).

Верхняя оценка хроматического числа, даваемая теоремой Брукса, является удовлетворительной для тех графов, степени вершин которых примерно одинаковы. В общем же случае разность между (G) и h(G) может быть сколь угодно большей. Рассмотрим граф, изображенный на рис. П.4.3. Очевидно, что h (G)=2 и в то же время,

(G)=l.

Рис.П4.3

Итак, общий итог «изысканий», проведенных выше, можно назвать неутешительным. Как мы видели, не существует формулы, позволяющей вычислить хроматическое число по «знакомым» величинам: число вершин, ребер, компонент связности, степени вершин, и нет достаточно хороших оценок для хроматического числа. Эта ситуация является отражением того факта, что задача вычисления хроматического числа является трудно решаемой, так же, как и задача нахождения гамильтонова цикла. Обсуждение алгоритмов вычисления хроматического числа выходит за рамки данного пособия, и мы ограничимся лишь тем, что приведем простой алгоритм нахождения правильной раскраски, близкой к оптимальной.

Алгоритм состоит в следующем. Упорядочиваем вершины графа G: V={v₁,v₂,…,v_n}. Вершину v₁ красим первой краской. Предположим, что вершины v₁,…,v_i уже раскрашены и на это использовано l красок. Если на раскрашенные вершины, смежные с v_i+1, использованы все краски, то v_i+1 раскрашиваем l+1 краской. Если среди l красок найдется краска, которая не использована для вершин, смежных с v_i+1, то вершину v_i+1 красим этой

Краской /7/.

Приведенный алгоритм часто называют алгоритмом последовательной раскраски. Нетрудно привести примеры, когда такая раскраска не является оптимальной.

Исторически понятие хроматического числа возникло с проблемой четырех красок. Проблема возникла в математике в середине 19 века. Первоначально вопрос формулировался так: сколько нужно красок для раскраски любой географической карты, при которой соседние страны раскрашены в разные цвета? Под географической картой понимается разбиение плоскости на конечное число связных областей, стран, границы которых состоят из замкнутых непрерывных линий без самопересечений, а соседними являются страны, имеющие общую границу ненулевой длины. Довольно очевидно, что четырех красок недостаточно. и вопрос формулировался обычно в более конкретном виде: достаточно ли четырех красок для раскраски любой географической карты? Это и есть проблема четырех красок. Положительный ответ на вопрос называется гипотезой четырех красок.

Проблема раскраски географических карт сводится к проблеме (правильной) раскраски плоских графов. Проиллюстрируем это сведение картой, изображенной на рис.П4.4.

Рис.П4.4

На рисунке изображена карта, имеющая пять стран (внешняя область - тоже страны). Внутри каждой страны зафиксируем точку, точки соединим ребром, если страны имеют общую границу. (На рис. П4.4 ребра проведены пунктирными линиями). Ребра при этом можно провести так, чтобы они не пересекались, т.е. чтобы полученный граф был плоским. Ясно, что раскраска карты определяет правильную раскраску графа и обратно. Проблему четырех красок можно теперь сформулировать так: достаточно ли четырех красок для правильной раскраски плоского графа?

Эта проблема вызвала большой интерес в математике. Есть свидетельства, что ей занимались известные математики Мебиус и де Морган. В 1880 году А. Компе опубликовал положительное решение проблемы четырех красок. Однако в 1890 году Р. Хивуд обнаружил ошибку в этом доказательстве. Одновременно он показал, что пяти красок достаточно для раскраски любого плоского графа. После этого появлялось довольно много «доказательств» гипотезы четырех красок и «контрпримеров» к ней, в которых обнаруживались ошибки. В 1969 году Х. Хели свел проблему четырех красок к исследованию множества С так называемых конфигураций. Множество С является конечным. Но довольно большим (порядка нескольких тысяч). Несколькими годами позже, в 1976 году математикам К. Аппелю и В. Хейкену удалось показать, что все конфигурации из множества С можно правильно раскрасить в четыре цвета. В возникающем при этом переборе существенно использовался компьютер. Такое решение проблемы четырех красок долгое время не признавалось многими математиками, поскольку его сложно повторить. Однако сейчас практически общепризнано, что К. Аппелем и В. Хейкеном доказана гипотеза четырех красок.

Приведем доказательство утверждения о том, что любой плоский граф можно раскрасить пятью красками (теорема 5). Предварительно установим следующий результат.

Теорема 4. В любом плоском графе найдется вершина, имеющая степень не выше пяти /4,7/.

Теорема 5. Каждый плоский граф можно правильно раскрасить пятью красками /4,7/.

Доказательство проведем индукцией по числу вершин графа. Для графа, состоящего из одной вершины утверждение теоремы очевидно. Предположим, что любой плоский граф, содержащий k вершин, можно правильно раскрасить пятью красками. Пусть плоский граф G содержит k+1 вершину.

По теореме 4 граф G содержит вершину, степень которой не превосходит пяти. Обозначим эту вершину через v₀. Граф G’=G–v₀ является плоским и содержит k вершин. Используя предположение индукции, правильно раскрасим граф G’ пятью красками. Если для раскраски вершин, смежных с v₀, использовано четыре краски или меньше, то найдется краска для вершины v₀ и в результате получится правильная раскраска графа G.

Предположим, что для раскраски вершин, смежных с v₀, использованы все пять красок. Отсюда следует, что s (v₀)=5. Занумеруем вершины, смежные v₀, по часовой стрелке (рис. П4.5).

Рис. П4.5.

Пусть вершина v_i раскрашена i–краской. Обозначим через Н₁₃ подграф графа G, порожденный вершинами, раскрашенными первой и третьей красками. Рассмотрим два случая.

Первый случай: вершины v₁ и v₃ лежат в разных компонентах связности графа Н₁₃. Обозначим через K компоненту связности графа Н₁₃, содержащую вершину v₃. Вершины, принадлежащие K, перекрасим следующим образом: вершины, раскрашенные первой краской, покрасим третьей, а вершины, раскрашенные третьей краской, покрасим первой. Мы получим правильную раскраску графа G’.

Действительно, если мы возьмем смежные вершины x и y графа G’ и обе эти вершины не лежат в K, то они будут раскрашены разными красками, поскольку не перекрашивались (рис. П4.5). Если одна из вершин, скажем х, принадлежит K, а вторая вершина y не принадлежит K, то х раскрашена (и до и после перекрашивания) первой или третьей красками, а вершина y не может быть раскрашена этими красками, поскольку K – компонента связности графа Н₁₃ и yK. Если же обе вершины х и y принадлежат K, то они до перекрашивания были раскрашены разными красками, а после перекрашивания их краски поменяются, но останутся различными. После перекраски вершина v₃ будет раскрашена в первый цвет. Раскрасим вершину v₀ в третий цвет и мы получим правильную раскраску всего графа G.

Второй случай: вершины v₁ и v₃ лежат в одной компоненте связности графа Н₁₃. Тогда они соединены простой цепью, проходящей через вершины графа Н₁₃. Отметим, что если к этой цепи добавить ребро, соединяющее вершины v₀ и v₁, и ребро, соединяющее вершины v₀ и v₃, то получится цикл графа G, который ограничивает часть плоскости, содержащей вершину v₂ (рис. П4.5). Рассмотрим теперь подграф Н₂₄ графа G’, содержащий вершины, раскрашенные второй и четвертой красками. Вершины v₂ и v₄ не могут быть соединены цепью в этом графе.

Действительно, в противном случае ребра этой цепи пересекали бы ребра (v₁,v₃)–цепи графа Н₁₃, расширенной ребрами (v₀,v₁) и (v₀,v₃), что невозможно, поскольку G – плоский граф, или новая цепь проходила бы по вершинам старой цепи, что тоже невозможно, так как эти вершины раскрашены разными красками (рис. П4.6).

Рис. П4.6

Обозначим буквой L компоненту связности графа Н₂₄, содержащую вершину v₄. Вершины этой компоненты перекрасим: вторую краску заменим на четвертую, а четвертую – на вторую. В результате, как и в первом случае, получим правильную окраску графа G’. Вершина v₄ будет раскрашена второй краской, как и вершина v₂ (так как v₂L). Четвертая краска освободится для вершины v₀.

Реберной раскраской называется функция g: E{1,2,…,k}, где E-множество ребер, k-натуральное число (число красок). Раскраска называется правильной, если для любых двух смежных ребер e₁ и e₂ выполняется неравенство g(e₁)g(e₂). Наименьшее число красок, необходимое для правильной реберной раскраски графа называется его хроматическим индексом.

ПРИЛОЖЕНИЕ 5

Министерство образования Российской Федерации

Государственное образовательное учреждение высшего профессионального образования

"Ижевский государственный технический университет"

Кафедра "Автоматизированные системы обработки информации и управления"

ОТЧЕТ

по выполнению расчетно-графической работы

на тему «Исследование графов»

по дисциплине «Дискретная математика и теория графов»

Студент группы ________________________________ ( ______________________)

(подпись) (Ф.И.О.)