Теория графов / графы.doc

Московский Государственный Институт

Электронной Техники (ТУ)

Курсовая работа по

«Дискретной математике»

«Теория графов»

Выполнил :

Тетерин А.Н.

ИМЭ-37

Преподаватель:

Клюшин А.В.

МОСКВА

2003 г

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

Основные понятия

Прежде всего рассмотрим способы задания графа .

Способы задания графа

Рассмотрим различные способы задания для одного и того же графа.

В дальнейшем будем опираться именно на второе определение графа.

3. Матрица смежности

4. Матрица инцидентности

Понятие изоморфизма для графов имеет наглядное толкование. Представим рёбра графов эластичными нитями, связывающими узлы - вершины. Тогда, изоморфизм можно представить как перемещение узлов и растяжение нитей.

Пример 1 (изоморфизм). Покажем, что следующие два графа изоморфны.

Действительно, отображение a → e, b → f, c → g, d → h, являющееся изоморфизмом легко представить как модификацию первого графа, передвигающую вершину d в центр рисунка.

Определение 1 (Степень вершины).

Степенью вершины назовём удвоенное количество петель, инцидентных этой вершине плюс количество остальных инцидентных ей рёбер.

Подграфы

Определение 2 (Подграф). Подграфом графа называется граф, являющийся подмоделью исходного графа. Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).

Определение 3 (Подграф, порождённый множеством вершин).

Подграфом, порождённым множеством вершин U называется подграф, множество вершин которого - U, содержащий те и только те рёбра, оба конца которых входят в U.

Определение 4 (Остовной подграф). Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

Два последних определения дают два вида максимальности подграфов: максимальность множества вершин и максимальность множества рёбер. Это подтверждают следующие три задачи:

.

Определение 5 (Пустой, полный графы). Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежны.

Маршруты, цепи и циклы.

Маршруты, цепи и циклы

Определение 6 (Маршрут). Маршрутом в графе G = <V,E; I> называется последовательность вершин и рёбер вида v₀,e₁,v₁,e₂, ..., v_n-1,e_n,v_n, где v_i  V, i  [0,n], e_i  E, (v_i-1,e_i), (v_i,e_i)  I, i  [1,n]. Вершины v₀, v_n называются связанными данным маршрутом (или просто связанными). Вершину v₀ называют началом, а v_n - концом маршрута. Если v₀ = v_n, то маршрут называют замкнутым. Число n называется длиной маршрута.

Определение 7 (Цепь, простая цепь, цикл). Маршрут, в котором все рёбра попарно различны, называется цепью. Замкнутый маршрут, являющийся цепью, называется циклом. Маршрут, в котором все вершины попарно различны, называется простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.

Пример 2 (цепь). Маршрут a,{a,b},b,{b,c},c,{c,a},a,{a,d},d в первом графе из примера 1 является цепью, но не является простой цепью.

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

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

Пример 3 (граф отношения делимости). Построим граф, изображающее отношение делимости на множестве {1,2,3,4,5,6,7,8,9,10}. Принцип такой: если от одного числа до другого есть цепь, ведущая вверх, тогда второе число делится на первое.

Связность графа

Определение 8 (Связность). Граф называется связным, если любая пара его вершин связана.

Определение 9 (Связные компоненты). Связными компонентами графа называются подграфы данного графа, вершины которых являются классами эквивалентности отношения свзанности в данном графе.

Определение 10 (Цикломатическое число). Цикломатическим числом графа называется число связных компонент графа плюс число рёбер минус число вершин.

Эйлеровы и гамильтоновы циклы

Определение 11 (Эйлеров цикл). Эйлеровым называется цикл, проходящий по каждому ребру графа ровно один раз. Граф, имеющий эйлеров цикл, тоже будем называть эйлеровым.

Пример 4 (эйлеров цикл). Построим эйлеров цикл для второго графа из задачи 1.1. Это h, {h,l}, l, {l,i}, i, {i,m}, m, {m,j}, j, {j,n}, n, {n,k}, k, {k,h}, h, {h,i}, i, {i,j}, j, {j,k}, k, {k,l}, l, {l,m}, m, {m,n}, n, {n,h}, h.

Теорема 1 (Критерий эйлеровости графа). Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин - чётные числа.

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

Кроме понятия эйлерова цикла в задачах часто возникает необходимость нахождения цепи, проходящей по каждому ребру ровно один раз (снимается требование замкнутости. Такие цепи будем называть эйлеровыми цепями.

Определение 12 (Гамильтонов цикл). Гамильтоновым называется цикл, проходящий по каждой вершине графа ровно один раз.

Деревья

Определение 13 (Дерево). Связный граф без циклов называется деревом.

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

Пример 5 (генеологическое дерево). На рисунке показано библейское генеологическое дерево.

Определение 14 (Лес, листья). Граф без циклов называется лесом. Вершины

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

3 Раскраска, плоские графы

Раскраска графов

Определение 15 (Раскраска). Раскраской графа G = (V,E) называется отображение : V → N . ^*

Определение 16 (Правильная раскраска). Раскраска называется правильной, если образы любых двух смежных вершин различны: (u)  (v), если (u,v)  I. Хроматическим числом графа называется минимальное количество красок, необходимое для правильной раскраски графа.

Пример 6 (раскраска). На следующем рисунке показана правильная раскраска.

Грани графа

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

Определение 17 (Плоский граф). Существует правило изображение графов на поверхности: рёбра графа должны пересекаться только своими концами, то есть в точках, представляющих вершины графа.

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

Определение 18 (Грань графа). Гранью графа, изображенного на некоторой поверхности, называется часть поверхности, ограниченная рёбрами графа.

Данное понятие грани, по-существу, совпадает с понятием грани многогранника. В качестве поверхности в этом случае выступает поверхность многогранника. Если многогранник выпуклый, его можно изобразить на плоскости, сохранив все грани. Это можно наглядно представить следующим образом: одну из граней многогранника растягиваем, а сам многогранник ``расплющиваем'' так, чтобы он весь поместился внутри этой грани. В результате получим плоский граф. Грань, которую мы растягивали ``исчезнет'', но ей будет соответствовать грань, состоящая из части плоскости, ограничивающей граф.

Таким образом, можно говорить о вершинах, рёбрах и гранях многогранника, а оперировать соответствующими понятиями для плоского графа.

Когда мы говорим ``плоский граф'', мы имеем в виду геометрический объект. Однако, конечно же не все его геометрические свойства нам важны (например, неважен абсолютный размер). Поэтому точнее считать, что плоский граф - это трёхосновная модель <V,E,S; I, B>, где V - множество вершин, E - множество рёбер, S - множество граней, I - отношение инцидентности, а B - отношение ограниченности, связывающее рёбра с ограничиваемыми ими гранями.

Теорема 2 (Обобщенная теорема Эйлера о многогранниках). Количество граней плоского графа равно его цикломатическому числу + 1.

В первоначальной формулировке теорема Эйлера о многогранниках звучала так: ``Для любого выпуклового многогранника количество вершин минус количество рёбер плюс количество граней равно 2.''

Для плоских графов существует очень знаменитая проблема четырёх красок. Она состоит в том, чтобы доказать (или опровергнуть) утверждение, что хроматическое число любого плоского графа не превосходит 4. Данная проблема была положительно решена всего несколько лет назад с использованием компьютерного анализа различных вариантов.

Двойственные графы

Определение 19 (Двойственный граф). Граф, вершинами которого являются грани графа G, изображенного на поверхности, рёбрами - рёбра графа G, гранями - вершины графа G, отношение инцидентности - отношением ограниченности графа G, а отношение ограниченности - отношением инцидентности графа G, называется двойственным графом к графу G.

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

Пример 7 (двойственный граф). На рисунке изображёны двойственные графы куба и октаэдра.

Эйлеровы пути,гамильтоновы пути.

Эйлеровы пути

Эйлеровым путем в графе называется произвольный путь, проходящий через каждое ребро графа в точности один раз, т.е. путь v₁, ..., v_m+1, такой что каждое ребро e E появляется в последовательности v₁, ..., v_m+1 в точности один раз как e = {v_i, v_i+1} для некоторого i.

Если v₁ = v_m+1, то такой путь называется эйлеровым циклом. Задача существования эйлерова пути в заданном графе была решена Эйлером в 1736 году, и представленное им необходимое и достаточное условие существования такого пути считается первой в истории теоремой теории графов.

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

Доказательство. Доказательство достаточности условия теоремы будет следствием анализа алгоритма нахождения эйлерова пути, который будет описан ниже. Необходимость условия очевидна, так как если вершина v, отличная от вершины v₁ и v_m+1, появляется в эйлеровом пути k раз, то это означает, что степень этой вершины в графе составляет 2k. Отсюда следует, что вершины нечетной степени, если они существуют, являются концами эйлерова пути. Здесь следует отметить, что не существует графов с одной только вершиной нечетной степени. Действительно, обозначая степень вершины v через d(v), имеем

ибо в указанной сумме каждое ребро {u, v} считается дважды: один раз в d(u) и один раз в d(v). Отсюда следует, что число вершин всегда четно.

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

Предположим, что u и v - единственные вершины нечетной степени связного графа G =  V, E>, и образуем граф G* добавлением дополнительной вершины t и ребер {u, t} и {v, t} (или просто {u, v}, если {u, v}E ). Тогда G* - связный граф без вершин нечетной степени, а эйлеровы пути в G будут в очевидном взаимно однозначном соответствии с эйлеровыми циклами в G*. В силу этого дальше мы будем заниматься только эйлеровыми циклами.

Пример гамильтонова пути в графе и графа, в котором такого пути не существует, показан на рис. (а), (б) соответственно.

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

Проблема существования гамильтонова пути принадлежит к классу так называемых NP-полных задач. Это широкий касс задач, включающий фундаментальные задачи из теории графов, логики, теории чисел, дискретной оптимизации и других дисциплин, ни для одной из которых не известен полиномиальный алгоритм (т.е. с числом шагов, ограниченным полиномом от размерности задачи).

Нахождение кратчайших путей в графе

Начальные понятия

Будем рассматривать ориентированные графы G = V, E>, дугам которых приписаны веса. Это означает, что каждой дуге u, v> E поставлено в соответствие некоторое вещественное число a (u, v), называемое весом данной дуги.