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

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

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

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

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

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

Выполнил :

Тетерин А.Н.

ИМЭ-37

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

Клюшин А.В.

МОСКВА

2003 г

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

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

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

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

1.      Явное задание графа как алгебраической системы.

2.      Геометрический

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

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

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

1.      <{a,b,c,d},{u,v,w,x}; {(u,a),(u,b),(v,b),(v,c),(w,c),(w,a),(x,c), (x,d)}>. Так как мы рассматриваем только простые графы, граф нам проще определять как модель, носителем которой является множество вершин, а отношение – бинарное отношение смежности вершин. Тогда данный граф запишется как <{a,b,c,d}; {(a,b), (b,a),(b,c),(c,b),(a,c),(c,a),(c,d),(d,c)}>. В таком представлении ребру соответствуют две пары вершин (v1,v2) и (v2,v1), инцидентных данному ребру. Чтобы задать такое представление, достаточно для каждого ребра указать двухэлементное множество вершин – его мы и будем отождествлять с ребром. Для данного графа рёбра задаются множеством {{a,b},{b,c},{a,c},{c,d}} и граф мы будем записывать как пару (V,E), где V – множество вершин, а E – множество рёбер.

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

2.      Геометрический

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> называется последовательность вершин и рёбер вида v0,e1,v1,e2, ..., vn-1,en,vn, где vi  V, i  [0,n], ei  E, (vi-1,ei), (vi,ei)  I, i  [1,n]. Вершины v0, vn называются связанными данным маршрутом (или просто связанными). Вершину v0 называют началом, а vn – концом маршрута. Если v0 = vn, то маршрут называют замкнутым. Число 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 – отношение ограниченности, связывающее рёбра с ограничиваемыми ими гранями.