Теория графов. Методические указания по подготовке к контрольным работам по дисциплине «Дискретная математика»

Министерство образования Российской Федерации
УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Теория графов
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
по подготовке к контрольным работам по дисциплине
«Дискретная математика»
Уфа  2005

Министерствообразования Российской Федерации
УФИМСКИЙГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедрапроектирования средств информатики
ТЕОРИЯГРАФОВ
МЕТОДИЧЕСКИЕУКАЗАНИЯ
по подготовке к контрольным работам по дисциплине
«Дискретная математика»
Уфа  2005
Составители: Н.И. Житникова,Г.И. Федорова, А.К. Галимов
УДК 519.6 (07)
ББК 22.193 (я7)
Теория графов. Методическиеуказания по подготовке к контрольным работам по дисциплине «Дискретнаяматематика». /Уфимск. гос. авиац. техн. ун-т.; Сост.: Н.И. Житникова,Г.И. Федорова, А.К. Галимов. — Уфа, 2005 -37 с.
Предназначены для студентов 1курса направления 654600: Информатика и вычислительная техника,       : Защита информациидля подготовки к контрольным работам по курсу «Дискретная математика».
Табл. 2. Ил. 14.Библиогр.: 9 назв.
Рецензенты:        Газизов Р.К.
                              ВасильевВ.И.
© Уфимский государственный
авиационный технический университет, 2005

                                                    Содержание
Краткийперечень основных понятий теории графов ………………..    4
Понятия смежности,инцидентности, степени………………………..     7
Маршрутыи пути ……………………………………………………….   7
Матрицы смежности и инцидентности…..…………………………….     7
Связность. Компоненты связности ……………………………………..   8
Матрицы достижимости и связности………….……………………….   9
Расстояния в графе…………………………..…………….…………….   9
Образи прообраз вершины и множества вершин …………..………..   10
Нагруженныеграфы ………………..…………………………………..  11
Деревьяи циклы …………………………………….………….………   12
Решение контрольных задач по теме «Теория графов»……………………………………………...…………………...  13
Задание 1. Компоненты сильной связностиориентированного графа.…………………………………………………………………….   13
Задание2. Расстояния в ориентированном графе ..………………......   16
Задание3. Минимальный путь в нагруженном ориентированном графе ...……...…………………………………………………………...              20
Задание4. Эйлеровы циклы и цепи ……..………………………….…   23
Задание5. Минимальное остовное дерево...………...…………...……  25
Задание6. Задача о коммивояжёре...………...…………...……………   27
Заданиядля самостоятельного решения ………….………......………   34
Списоклитературы…………………………………………………..….  37

Краткий перечень основных понятий теорииграфов.
Теория графов как теоретическая дисциплина можетрассматриваться как раздел дискретной математики, исследующий свойства конечныхмножеств (бесконечные графы не будут вводиться в рассмотрение) с заданнымиотношениями между их элементами. Как прикладная дисциплина теория графовпозволяет описывать и исследовать многие физические, технические,экономические, биологические, социальные и другие системы. Например, графом,изображенным на рис. 1, в котором точки − вершины графа − города,линии, соединяющие вершины − ребра − дороги, соединяющие города,описывается так называемая транспортная задача (задача нахождения кратчайшегопути из одного города- пункта в другой).

Рис. 1.
Формальное определение графа таково. Пусть заданоконечное множество V, состоящее из nэлементов,называемых вершинами графа, и подмножество Xдекартова произведения V×V, то есть ориентированным графом Dназываетсясовокупность (V,X). Неориентированнымграфом Gназывается совокупность множества Vимножества ребер − неупорядоченных пар элементов, каждый из которыхпринадлежит множеству V.
Одинаковыепары — параллельные или кратные ребра;
Кратностью реберназывают количество одинаковых пар.

Рис.2.
Например,кратность ребра {v1, v2} вграфе, изображенном на рис. 2, равна двум, кратность ребра {v3, v4} −трем.
Псевдограф− граф, в котором есть петли и/или кратные ребра.
Мультиграф− псевдограф без петель.
Граф−мультиграф, в котором ни одна пара не встречается более одного раза.
Графназывается ориентированным, если пары(v,w) являются упорядоченными.
Ребраориентированного графа называются дугами.
Итак, используемыедалее обозначения:
V– множество вершин;
X– множество ребер или дуг;
v(илиvi)– вершина или номер вершины;
G, G0 — неориентированный граф;
D, D0–ориентированный;
{v,w} − ребра неориентированного графа;
{v,v} – обозначение петли;
(v,w) − дуги в ориентированном графе;
v,w — вершины, x,y,z– дуги и ребра;
n(G), n(D) количество вершин графа;
m(G) — количество ребер, m(D) — количество дуг.
Примеры
1) Ориентированный граф D=(V, X), V={v1, v2, v3, v4},
X={x1=(v1,v2), x2=(v1,v2), x3=(v2,v2), x4=(v2,v3)}.

Рис. 3.
2) Неориентированныйграф G=(V, X), V={v1, v2, v3, v4, v5},
X={x1={v1,v2}, x2={v2,v3}, x3={v2,v4}, x4={v3,v4}}.

Рис. 4.
Понятия смежности, инцидентности,степени
Если x={v,w} — ребро,то vи w−концы ребра x.
Если x=(v,w) — дуга ориентированногографа, то v− начало, w– конец дуги.
Вершина vи ребро xнеориентированного графа (дуга xориентированного графа) называются инцидентными, если vявляется концом ребра x(началом или концом дуги x).
Вершины v, wназываютсясмежными, если {v,w}ÎX.
Степеньювершины vграфа Gназывается число d(v) ребер графа G, инцидентных вершине v.
Вершинаграфа, имеющая степень 0 называется изолированной,а степень 1 – висячей.
Полустепеньюисхода(захода) вершины vориентированного графа Dназывается число d+(v) (d-(v)) дуг ориентированного графа D, исходящихиз v(заходящих в v).
Следуетзаметить, что в случае ориентированного псевдографа вклад каждой петлиинцидентной вершине vравен 1 как в d+(v), так и в d-(v).
Маршруты и пути
Последовательность v1x1v2x2v3...xkvk+1, (где k³1, viÎV, i=1,...,k+1, xiÎX, j=1,...,k), в которой чередуются вершины и ребра (дуги) и длякаждого j=1,...,kребро (дуга) xjимеет вид {vj,vj+1} (дляориентированного графа (vj,vj+1)),называется маршрутом, соединяющимвершины v1и vk+1(путем из v1в vk+1).
Пример
Вграфе, изображенном на рис.4, v1x1v2x2v3x4v4x3v2 — маршрут, v2x2v3x4v4–подмаршрут;
маршрутможно восстановить и по такой записи x1x2x4x3;
есликратности ребер (дуг) равны 1, можно записать и так v1v2v3v4v2.
Цепь− незамкнутый маршрут (путь), в котором всеребра (дуги) попарно различны.
Цикл− замкнутая цепь (в неориентированном графе).
Контур− замкнутый путь (в ориентированном графе).
Простой путь (цепь)− путь (цепь, цикл, контур), в котором ни одна дуга/ребро не встречаетсядважды.
Простой цикл (контур)− цикл (контур), в котором все вершины попарно различны.
Гамильтоновацепь (путь, цикл, контур) − простая цепь (путь, цикл, контур),проходящая через все вершины.
Эйлерова цепь(путь,цикл, контур) − цепь (путь, цикл, контур), содержащая все ребра(дуги) графа по одному разу.
Длинамаршрута (пути) − число ребер в маршруте (дуг в пути).
Утверждение 1.Для тогочтобы связный псевдограф Gобладал Эйлеровым циклом, необходимо и достаточно,чтобы степени всех его вершин были четными.
Утверждение 2. Для тогочтобы связный псевдограф Gобладал Эйлеровой цепью, необходимо и достаточно,чтобы он имел ровно 2 вершины нечетной степени.
Матрицы смежности и инцидентности
Пусть D=(V,X) ориентированный граф, V={v1,...,vn},X={x1,...,xm}.
Матрицасмежностиориентированного графа D−квадратная матрица
A(D)=[aij] порядка n, где
                                             
Матрицаинцидентности− матрица B(D)=[bij]порядка n´m, где
                                  
Матрицейсмежностинеориентированного графа G=(V,X)называется квадратная симметричная матрица A(G)=[aij] порядка n, где
                                            
Матрицаинцидентностиграфа Gназываетсяматрица B(G)=[bij] порядка n´m, где
                               
Связность. Компоненты связности
Подграфомграфа G(ориентированного графа D) называется граф, все вершины и ребра которогосодержатся среди вершин и ребер графа G(D).
Подграф называется собственным,если он отличен от самого графа.
Говорят, что вершинаwориентированногографа D(графа G) достижима из вершины v, если либо w=v, либо существует путь (маршрут) из vв w.
Граф (ориентированный граф) называется связным (сильно связным), если для любых двух его вершин v, wсуществуетмаршрут (путь), соединяющий vи w.
Компонентойсвязностиграфа G(сильной связности ориентированного графаD)называется его связный (сильно связный) подграф, не являющийся собственнымподграфом никакого другого связного (сильно связного) подграфа графа G(ориентированногографа D).Матрицы достижимости и связности
Пусть A(D) – матрица смежности ориентированного псевдографа D=(V,X) (илипсевдографа G=(V,X)), где V={v1,…, vn}.Обозначим через Ak=[a(k)ij] k-ю степень матрицы смежности A(D).
Элемент a(k)ijматрицы Akориентированного псевдографа D=(V,X) (псевдографаG=(V,X)) равенчислу всех путей (маршрутов) длины kиз viв vj.
Матрицадостижимостиориентированного графа D− квадратная матрица T(D)=[tij]порядка n, элементы которой равны
                                 
Матрицасильной связностиориентированногографа D− квадратнаяматрица S(D)=[sij] порядка n, элементы которой равны
              
Матрицасвязностиграфа G− квадратная матрица S(G)=[sij]порядка n, элементы которой равны
                   
Пусть G=(V,X) – граф, V={v1,…, vn},A(G)– его матрица смежности. Тогда
S(G)=sign[E+A+A2+A3+… An-1](E- единичнаяматрицапорядкаn).
Утверждение3. Пусть D=(V,X) – ориентированный граф, V={v1,…, vn},A(D) – его матрица смежности. Тогда
1)  T(D)=sign[E+A+A2+A3+…An-1],
2)   S(D)=T(D)&TT(D) (TT-транспонированнаяматрица, & — поэлементное умножение).
Расстояния в графе
Пусть  называется минимальнаядлина пути между ними, при этом  пути.
Расстояние в графе удовлетворяют аксиомам метрики
1)  
2)    (не в ориентированномграфе)
3)  
4)    в связном графе (не вориентированном графе).
Пусть  связный граф (илипсевдограф).
Диаметромграфа Gназывается величина
Пусть
Максимальнымудалением (эксцентриситетом)в графе Gот вершины называется величина
Радиусом графа Gназывается величина
Центром графаGназывается любая вершина  такая, что
Образ ипрообраз вершины и множества вершин
Пусть  ориентированный граф
Обозначим

V1;
V1.
Нагруженные графы
Нагруженный граф− ориентированный граф D=(V,X), намножестве дуг которого определена не которая функция
Цифранад дугой (см. рис. 5)− вес дуги (цена дуги).

Рис. 5.
Обозначения:для любого пути П нагруженного ориентированного графа Dчерез l(П) сумму длин дуг, входящих в путь П. (Каждая дугасчитается столько раз, сколько она входит в путь П).
Величинаlназывается длинойпути.
Есливыбрать веса равными 1, то придем к ненагруженному графу.
Путьв нагруженном ориентированном графе из вершины vв вершину w, где v¹w,называется минимальным, если он имеетнаименьшую длину.
Аналогично определяется минимальный маршрут в нагруженном графе.
Введемматрицу длин дуг C(D)=[cij] порядка n, причем
                                       
Свойства минимальныхпутей в нагруженном ориентированном графе
1)Если для "дуги  "минимальный путь (маршрут) является простой цепью;
2)если  минимальный путь(маршрут) то для "i,j:  путь (маршрут)  тоже являетсяминимальным;
3)если  − минимальный путь(маршрут) среди путей (маршрутов) из vв w, содержащих не более k+1 дуг (ребер), то  − минимальныйпуть (маршрут) из vв uсреди путей (маршрутов), содержащих не более kдуг(ребер).
Деревья и циклы
Граф Gназывается деревомесли он является связным и не имеет циклов.
Граф Gназывается лесомесли все его компоненты связности — деревья.
Свойствадеревьев:
Следующие утверждения эквивалентны:
1)     Граф Gесть дерево.
2)     Граф Gявляется связным и не имеет простых циклов.
3)     Граф Gявляется связным и число его ребер ровно на 1 меньшечисла вершин.
4)     "две различные вершины графа Gможносоединить единственной (и при этом простой) цепью.
5)     Граф Gне содержит циклов, но, добавляя к нему любое новоеребро, получаем ровно один и притом простой цикл
Утверждение4. Если у дерева Gимеется,по крайней мере, 1 ребро, то у него найдется висячая вершина.
Утверждение5.Пусть Gсвязный граф, а  − висячаявершина в G, граф  получается из Gврезультате удаления вершины  и инцидентного ейребра. Тогда  тоже является связным.
Утверждение6.Пусть G — дерево с n(G) вершинами и m(G) ребрами. Тогда m(G)=n(G)-1.
Утверждение7.Пусть G– дерево. Тогда любая цепь в Gбудет простой.
Остовнымдеревом связного графа Gназываетсялюбой его подграф, содержащий все вершины графа Gи являющийся деревом.
Пусть G– связный граф. Тогда остовное дерево графа Gдолжносодержать n(G)-1 ребер. Значит, для получения остовного дерева изграфа Gнужно удалить  ребер.
Число  − цикломатическое число графа G.
Решениеконтрольных задач по теме «Теория графов».
Задание1. Компоненты сильной связности ориентированного графа.
С помощью матрицы смежности найтикомпоненты сильной связности ориентированного графа D.
Cоставляемматрицу смежности A(D) размерности  (n−количество вершин) для данного ориентированного графа: она состоит из нулей иединиц, номера строк – индексы вершин, из которых исходят дуги, номерастолбцов – индексы вершин, в которые дуги входят (если есть дуга, исходящая извершины viи входящая в vj, то элемент матрицы смежности, стоящий на пересеченииi-тойстроки и j-того столбца равен 1, иначе – 0.).
Для того, чтобы выделить компоненты сильной связности,необходимо сначала найти матрицу достижимости T(D) ориентированного графа по первой формуле утверждения3, затем находим матрицу сильной связности S(D) ориентированного графа (она должна бытьсимметрической) по второй формуле из того же утверждения.
Алгоритм выделения компонент сильнойсвязности
1. Присваиваем p=1 (p−количество компонент связности),
2. Включаем в множество вершин Vpкомпоненты сильной связности Dpвершины, соответствующие единицам первой строки матрицы Sp.В качестве матрицы A(Dp) возьмем подматрицу матрицы A(D),состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов,соответствующих вершинам из Vp.
3. Вычеркиваем из Spстроки и столбцы, соответствующие вершинам из Vp.Если не остается ни одной строки (и столбца), то p — количество компонент сильной связности. В противномслучае обозначим оставшуюся после вычеркивания срок и столбцов матрицу как Sp+1, присваиваем p=p+1 ипереходим к п. 2.
Пример
Выделим компоненты связности ориентированного графа,изображенного на рис. 6. В данной задаче количество вершин n=5.

Рис. 6.
Значит, для данного ориентированного графаматрица смежности будет иметь размерность 5×5 и будет выглядеть следующимобразом
                                         
Найдем матрицу достижимости для данногоориентированного графа по формуле 1) из утверждения 3:
           
                                    
Следовательно,

        
Такимобразом, матрица сильной связности, полученная по формуле 2) утверждения 3,будет следующей:
     
Присваиваем p=1  и составляем множествовершин первой компоненты сильной связности D1: это тевершины, которым соответствуют единицы в первой строке матрицы S(D). Такимобразом, первая компонента сильной связности состоит из одной вершины
Вычеркиваем из матрицы S1(D) строку истолбец, соответствующие вершине v1, чтобыполучить матрицу S2(D):
                                    
Присваиваем p=2. Множество вершин второй компоненты связностисоставят те вершины, которым соответствуют единицы в первой строке матрицы S2(D), то есть  исходного графа D−в ее качестве возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A,находящихся на пересечении строк и столбцов, соответствующих вершинам из V2:
                                              
Вычеркиваем из матрицы S2(D) строки истолбцы, соответствующие вершинам из V2, чтобыполучить матрицу S3(D), котораясостоит из одного элемента:
                                                     
иприсваиваем p=3. Таким образом, третья компонента сильной связностиисходного графа, как и первая, состоит из одной вершины
Таким образом, выделены 3 компоненты сильной связностиориентированного графа D:
       D1:

D2:

       D3:

Задание 2.Расстояния в ориентированном графе
С помощьюалгоритма фронта волны найти расстояния в ориентированном графе D: диаметр, радиус и центры.
Пусть  ориентированный граф сn³2 вершинами и v,w(v¹w) –заданные вершины из V.
Алгоритмпоиска минимального пути из  в  в ориентированном графе
(алгоритм фронта волны).
1)        Помечаем вершину  индексом 0, затемпомечаем вершины Îобразу вершины  индексом 1. Обозначаемих FW1(v). Полагаемk=1.
2)              Если  или k=n-1, иодновременно то вершина  не достижима из