Введение в теорию графов 1. Лекция: Графы и способы их представления
Приводятся начальные сведения о графах и основные понятия и определения такие как орграф, смешанный граф, дубликат графа дуга, петля, полустепени исхода и захода. Даются возможные способы представления графов. Цель лекции: Дать представление о графах и возможных способах их представления.
Содержание
Введение Графы и способы их представления Основные определения Способы описания графов Теоретико-множественное представление графов Задание графов соответствием Матричное представление графов
Введение
В последние годы особую важность приобрели те разделы математики, которые имеют отношение к развитию цифровых устройств, цифровой связи и цифровых вычислительных машин. Базой для преподавания этих дисциплин наряду с классическими методами анализа непрерывных физических моделей стали алгебраические, логические и комбинаторные методы исследования различных моделей дискретной математики.
Значительно возросла популярность теории графов – ветви дискретной математики. Графы встречаются во многих областях под разными названиями: "структуры" в гражданском строительстве, "сети" – в электронике, "социограммы" – в социологии и экономике, "молекулярные структуры" – в химии, "дорожные карты", электрические или газовые распределительные сети и т. д.
Родившись при решении головоломок и игр, таких, например, как задача о кенигсбергских мостах и игра Гамильтона, теория графов стала мощным средством исследования и решения многих задач, возникающих при изучении больших и сложных систем. Для специалистов по вычислительной технике, информационным системам и системам цифровой связи теория графов – это удобный язык выражения понятий из этой области; многие результаты теории графов имеют непосредственную связь с задачами, с которыми им приходится сталкиваться. Графическая интерпретация различных моделей графов дана на рис. 1.1 Так в виде ориентированных графов можно представить любую логическую или функционально - логическую схему (рис. 1.1,а). На таких графовых моделях можно, например, оценить быстродействие схемы. Блок-схема алгоритма может быть представлена вероятностным графом (рис. 1.1,б), который позволяет оценить временные характеристики алгоритма, затраты процессорного времени, трудоемкость и другие. Графом типа "дерево" можно отобразить практически любую структуру организации или предприятия (рис. 1.1,в).
Широкое применение теория графов получила при исследовании так называемой проблемы оптимизации, возникающей при конструировании больших систем как технических, так и программных, например, таких, как компиляторы.
В рамках этих исследований были разработаны многие, неизвестные ранее теоретико-графовые понятия. Теория графов имеет большую привлекательность для специалистов в области проектирования для построения эффективных алгоритмов и анализа их сложности. Использование аппарата теории графов оказало существенное влияние на разработку алгоритмов конструкторского проектирования схем. Непосредственное и детальное представление практических систем, таких, как распределительные сети, системы связи, приводит к графам большого размера, успешный анализ которых зависит в равной степени, как от эффективных алгоритмов, так и от возможностей компьютерной техники. Поэтому в настоящее время основное внимание сосредоточено на разработке и описании компьютерных алгоритмов анализа графов. В связи с этим основной упор в данном учебном пособии делается на машинные способы представления графов и алгоритмы решения задач на графах, легко реализуемых на ЭВМ.
a
б
Рис. 1.1. Графическая интерпретация применения графовых структур: а – орграф; б – вероятностный граф; в – граф-дерево
Графы и способы их представления
Основные определения
Графом называется двойка вида
G = (X, A),
где X = {xi}, i = 1, 2, ..., n – множество вершин графа, A = {ai}, i = 1, 2,... , m – множество ребер графа.
Рис. 1.2.
Если ребра не имеют ориентации, то граф называется неориентированным (рис. 1.2,б). Граф, в котором присутствуют и ребра, и дуги называется смешанным (рис. 1.2,в). В случае, когда G = (X, A) является орграфом, и мы хотим пренебречь направленностью дуг из множества A, то неориентированный граф, соответствующий G, будет обозначаться и называться неориентированным дубликатом или неориентированным двойником (рис. 1.2,г).
Дуга ai может быть представлена упорядоченной парой вершин (хn, хk), состоящей из начальной хn и конечной хk вершин. Например, для графа G1 (рис. 1.2,а) дуга a1 задается парой вершин (x2, x1), а дуга а3 парой (x2, x3). Если хn, хk – концевые вершины дуги ai, то говорят, что вершины хn и хk инцидентны дуге ai или дуга ai инцидентна вершинам хn и хk.
Дуга, у которой начальная и конечная вершины совпадают, называется петлей. В графе G3 (рис. 1.2,в) дуга a7 является петлей.
Каждая вершина орграфа хi может характеризоваться полустепенью исхода d0(хi) и полустепенью захода dt(хi).
Полустепенью исхода вершины хi — d0(хi) называется количество дуг, исходящих из этой вершины. Например, для орграфа G1 (рис. 1.2,а) характеристики полустепеней исхода следующие: d0(х1)=1, d0(х2)=2, d0(х3)=2, d0(х4 )=1.
Полустепенью захода вершины хi — dt(хi) называется количество дуг, входящих в эту вершину. Например, для орграфа G1: dt(х1)=2, dt(х2)=1, dt(х3)=2, dt(х4 )=1.
Очевидно, что сумма полустепеней исхода всех вершин графа, а также сумма полустепеней захода всех вершин графа равна общему числу дуг графа, т. е.
ni=1d0(xi)= ni=1dt(xi)=m
где n – число вершин графа, m – число дуг.
Каждая вершина неориентированного графа хi может характеризоваться степенью вершины d(хi).
Степенью вершины хi – d(хi) называется количество ребер, инцидентных этой вершине. Например, для орграфа G1 (рис. 1.2,б) характеристики степеней следующие: d(х1)=2, d(х2)=3, d(х3)=3, d(х4 )=2.
Способы описания графов
Граф описывается перечислением множества вершин и дуг. Примеры описания приведены для орграфов на рис. 1.3 и рис. 1.4.
G4 = (Х, А),
где Х = {хi}, i = 1, 2, 3, 4 – множество вершин; А = {ai }, i = 1, 2, ..., 6 – множество дуг, причем А = {(х1, х2), (х4, х2), (х2, х4 ), (х2, х3), (х3, х3), (х4 , х1)}.
Рис. 1.3.
G5 = (X, A),
где X = {B, C, D, E, F} – множество вершин графа, A = {ai}, i = 1, 2, ..., 5 – множество дуг графа, причем a1 = (F, B), a2 = (B, E), a3 = (F, D), a4 = (E, C), a5 = (C, D).
Рис. 1.4.
Задание графов соответствием
Описание графов состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины.
Соответствием Г называется отображение множества Х в Х, а граф в этом случае обозначается парой G = (X, Г).
Отображением вершины хi — Г(хi) является множество вершин, в которые существуют дуги из вершины хi, т. е. Г(хi) = { хj: дуга (хi, хj) A}.
Так для орграфа на рис. 1.3 описание заданием множества вершин и соответствия выглядит следующим образом: G4=(X, Г),
где X = {хi}, I = 1, 2, ..., 4 – множество вершин, Г(х1) = { х2 }, Г(х2) = { х3, х4 }, Г(х3) = { х3 }, Г(х4) = { х1, х2 } – отображения.
Для неориентированного или смешанного графов предполагается, что соответствие Г задает такой эквивалентный ориентированный граф, который получается из исходного графа заменой каждого неориентированного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Например, для графа на рис. 1.2,б Г(х2) = { х1, х3, х5 }, Г(х4) ={ х3, х5} и т. д.
Матричное представление графов
Для обработки на ЭВМ графы удобно представлять в виде матриц смежности и инциденций.
Матрица смежности – это квадратная матрица размерностью n x n, (где n – число вершин графа), однозначно представляющая его структуру.
A = {aij}, i, j = 1, 2, ..., n, а каждый элемент матрицы определяется следующим образом:
aij = 1, если дуга (хi, хj),
aij = 0, если нет дуги (хi, хj).
Матрица инциденций представляет собой прямоугольную матрицу размером n x m, где n – количество вершин графа, а m – количество дуг графа. Обозначается матрица инциденций B = {bij}, i = 1, 2, ..., n, j = 1, 2, ..., m.
Каждый элемент матрицы определяется следующим образом:
bij = 1, если хi является начальной вершиной дуги aj,
bij = –1, если хi является конечной вершиной дуги aj,
bij = 0, если хi не является концевой вершиной дуги aj или если aj является петлей.
На рис. 1.5, а,б приведен граф и его матрица смежности, по которой можно найти характеристики вершин. Так сумма элементов i-ой строки матрицы дает полустепень исхода вершины хi, а сумма элементов i-го столбца дает полустепень захода вершины хi. По матрице смежности можно найти прямые и обратные отображения. Рассмотрим i-ю строку матрицы. Если элемент aij=1, то элемент графа хj входит в отображение Г(хi). Например, во 2-й строке матрицы А (рис. 1.5,б) единицы стоят в 2-м и 5-м столбцах, следовательно, Г(х2) = { х2, х5}.
Рис. 1.5. Орграф и его матричное представление: а – орграф; б – матрица смежности; в – матрица инциденций
Для графа на рис. 1.5,а матрица инциденций приведена на рис. 1.5,в. Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец либо содержит один элемент равный 1 и один – равный – 1, либо все элементы столбца равны 0.
Для неориентированного графа, матрица инциденций определяется так же, за исключением того, что все элементы, равные –1, заменяются на 1.
Рассмотрим семь операций над графами, три из которых являются бинарными, включающими два графа, а остальные четыре – унарные, т. е. определены на одном графе.
Объединение графов G1 и G2 , обозначаемое как G1 G2 , представляет такой граф G3 = (Х1 Х2, A1 A2), что множество его вершин является объединением Х1 и Х2 , а множество ребер – объединением A1 и A2 . Граф G3 , полученный операцией объединения графов G1 и G2 , показан на рис. 2.1,д, а его матрица смежности – на рис. 2.1,е. Матрица смежности результирующего графа получается операцией поэлементного логического сложения матриц смежности исходных графов G1 и G2 .
Рис. 2.1.
Пересечение графов G1 и G2 , обозначаемое как G1 G2 , представляет собой граф G4 = (Х1 Х2, A1 A2). Таким образом, множество вершин графа G4 состоит из вершин, присутствующих одновременно в G1 и G2 . Операция пересечения графов G1 G2 показана на рис. 2.2,в, а результирующая матрица смежности получается операцией поэлементного логического умножения матриц смежности исходных графов G1 и G2 . показана на рис. 2.2.г.
Рис. 2.2.
Рис.2.2. Операция пересечения и кольцевой суммы: а – граф G1; б – граф G2; в – граф G1 G2 ; г – матрица смежности графа G1 G2 ; д – граф G1 G2 ; е – матрица смежности графа G1 G2
Кольцевая сумма двух графов G1 и G2 , обозначаемая как G1 G2 , представляет собой граф G5 , порожденный на множестве ребер A1 A2 . Другими словами, граф G5 не имеет изолированных вершин и состоит только из ребер, присутствующих либо в G1 , либо в G2 , но не в обоих одновременно. Кольцевая сумма графов G1 и G2 показана на рис. 2.2,д, а результирующая матрица смежности получается операцией поэлементного логического сложения по mod 2 матриц смежности исходных графов G1 и G2 . показана на рис. 2.2.е.
Легко убедиться в том, что три рассмотренные операции коммутативны т. е. G1 G2 = G2 G1, G1 G2 = G2 G1, G1 G2 = G2 G1 , и многоместны, т. е. G1 G2 G3 G4 ..., G1 G2 G3 G4 ... и так далее.
Рассмотрим унарные операции на графе.
Удаление вершины. Если хi -вершина графа G = (X, A), то G–хi -порожденный подграф графа G на множестве вершин X–хi , т. е. G–хi является графом, получившимся после удаления из графа G вершины хi и всех ребер, инцидентных этой вершине. Удаление вершины х3 показано на рис. 2.3,б (для исходного графа, изображенного на рис. 2.3,а). Матрица смежности исходного графа представлена на таблице 2.1а). Результирующая матрица смежности графа после выполнения операции удаления вершины хi получается путем удаления соответствующего i- го столбца и i-ой строки из исходной матрицы и "сжимания" матрицы по вертикали и горизонтали начиная с (i+1)- го столбца и (i+1)-ой строки (таблица 2.1б). В дальнейшем элементы графа могут быть переобозначены.
Рис. 2.3.
Удаление ребра или удаление дуги. Если ai -дуга графа G = = (X, A), то G-ai – подграф графа G, получающийся после удаления из G дуги ai . Заметим, что концевые вершины дуги ai не удаляются. Удаление из графа множества вершин или дуг определяется как последовательное удаление определенных вершин или дуг. Удаление дуг a4 и a7 показано на рис. 2.3,в. Результирующая матрица смежности графа после выполнения операции удаления дуги ai получается путем удаления соответствующих элементов из исходной матрицы (таблица 2.1в).
Таблица 2.1a.
X1
X2
X3
X4
X5
X1
X2
X3
X4
X5
Таблица 2.1б.
X1
X2
X4
X5
X1
X2
X4
X5
Таблица 2.1в.
X1
X2
X3
X4
X5
X1
X2
X3
X4
X5
Таблица 2.1г.
X1-2
X3
X4
X5
X1-2
X3
X4
X5
Таблица 2.1д.
X1-2
X3
X4
X5
X1-2
X3
X4
X5
Таблица 2.1е.
X1-2
X3-4
X5
X1-2
X3
X5
Замыкание или отождествление. Говорят, что пара вершин хi и xj в графе G замыкается (или отождествляется), если они заменяются такой новой вершиной, что все дуги в графе G, инцидентные хi и xj , становятся инцидентными новой вершине. Например, результат замыкания вершины х1 и х2 показан на рис. 2.3,г для графа G (рис. 2.3,а). Матрица смежности графа после выполнения операции замыкания вершин хi и xj получается путем поэлементного логического сложения i- го и j- го столбцов и i-ой и j- строк в исходной матрице и "сжимания" матрицы по вертикали и горизонтали (таблица 2.1г).
Стягивание. Под стягиванием подразумевают операцию удаления дуги или ребра и отождествление его концевых вершин. Граф, изображенный на рис. 2.3,д получен стягиванием дуги a1 , а на рис. 2.3,е – стягиванием дуг a1 , a6 и a7 . Соответствующие результирующие матрицы смежности показаны в таблицах 2.1д и 2.1е.
Многозначные отображения
Прямые отображения
Прямое отображение 2-го порядка вершины хi – это прямое отображение от прямого отображения 1-го порядка, т. е. Г+2( хi ) = Г+( Г+1 ( хi ) ).
Аналогично можно записать для прямого отображения 3-го и т. д. n-го порядка.
… Г+3(xi)= Г+(Г+2(xi))= Г+(Г+(Г+1(xi)))
Обратные отображения
Обратные отображения 2-го, 3-го и т. д. n-го порядка определяются следующим образом:
Г-2(xi)= Г-(Г-1(xi)),
Г-3(xi)= Г-(Г-2(xi)),
Транзитивные замыкания
Прямое транзитивное замыкание
T+( хi ) = хi Г+1 ( хi ) Г+2( хi ) ...
Многозначные отображения находятся до тех пор, пока в них добавляются новые… Так, для графа на рис. 3.1.
Обратное транзитивное замыкание
T-( хi ) = хi Г-1(хi ) Г-2(хi ) ...
Иначе, обратное транзитивное замыкание для некоторой вершины хi – T-( хi )–… Рассмотрим построение обратного транзитивного замыкания для графа на рис. 3.1.
Нахождение транзитивных замыканий по матрице смежности
Рис. 3.3. Построение прямого (а) и обратного (в) транзитивных замыканий для… Это возможно сделать только для вершины х3, так как вторая клетка уже занята. Анализ 3-й строки матрицы на 4-м шаге…
Достижимость и контрдостижимость
Достижимость в графе описывается матрицей достижимости R=[rij], i, j=1, 2, ... n, где n – число вершин графа, а каждый элемент определяется… rij=1, если вершина хj достижима из хi ,
rij=0, в противном случае.
Нахождение множества вершин, входящих в путь
Рис. 4.2. Орграф
Так для графа на рис. 4.2 нахождение вершин, входящих в путь, например из…
Матричный метод нахождения путей в графах
a(2) ik= n j=1aijajk
Слагаемое в формуле равно 1 тогда и только тогда, когда оба числа aij и ajk… На таблице 4.1a представлена матрица смежности графа, изображенного на рис. 4.2. Результат возведения матрицы…
Лекция: Типы графов
Рассматриваются типы графов такие как полный, симметрический, антисимметрический, двудольный, дерево, планарный и их возможные комбинации. Дается теорема о двудольности графов. Цель лекции: Дать представление о типах графов и их свойствах
Содержание
Теорема о двудольности Граф G = (X, A) называют полным, если для любой пары вершин хi и хj в X существует ребро (хi, хj) в неориентированном графе
G=(X,A)
т. е. для каждой пары вершин графа G должна существовать по крайней мере одна дуга, соединяющая их (рис. 5.1,а).
Граф G =(X, A)называется симметрическим, если в множестве дуг A для любой дуги (хi, хj) существует также противоположно ориентированная дуга (хj, хi) (рис. 5.1,б).
Рис. 5.1. а – полный граф; б – симметрический граф; в – антисимметрический граф; г – полный симметрический;
Антисимметрическим называется такой граф, для которого справедливо следующее условие: если дуга (хi, хj) A, то во множестве A нет противоположно ориентированной дуги, т. е. ( хj, хi) A (рис. 5.1,в). Очевидно, что в антисимметрическом графе нет петель.
В качестве примера можно рассмотреть граф, являющийся моделью некоторой группы людей: вершины графа интерпретируют людей, а дуги – их взаимоотношения. Так, если в графе дуга, нарисованная от вершины хi к вершине хj , означает, что хi является другом или родственником хj , тогда данный граф должен быть симметрическим. Если дуга, направленная от хi к хj , означает, что вершина хj подчинена вершине хi , то такой граф должен быть антисимметрическим.
Комбинируя определения полного и симметрического графов и полного и антисимметрического графов, получили следующие определения:
граф G =(X, A), в котором любая пара вершин (хi, хj) соединена двунаправленными дугами, называется полным симметрическим (рис. 5.1,г); граф G =(X, A), имеющий для каждой пары вершин (хi, хj) только одну дугу, называется полным антисимметрическим или турниром. Связный граф, не имеющий циклов, либо граф, в котором каждая пара вершин соединена одной и только одной простой цепью, называется деревом (рис. 5.2, а, б).
Рис. 5.2. Граф типа “дерево”: а – неориентированное дерево, б – ориентированное дерево
Ориентированное дерево представляет собой ориентированный граф без циклов, в котором полустепень захода каждой вершины, за исключением одной (например, вершины х1 ), равна 1, а полустепень захода вершины х1 (называют корнем этого дерева) равна 0 (рис. 5.2,б).
Граф G =(X, A), который может быть изображен на плоскости или сфере без пересечений называется планарным (рис. 5.3).
Рис. 5.3. Планарный граф
На рис. 5.4 показаны непланарные графы. Эти два графа играют важную роль в теории планарных графов и известны как графы Куратовского.
Рис. 5.4. Непланарные графы
Неориентированный граф G = (X, A)называют двудольным, если множество его вершин X может быть разбито на такие два подмножества Xа и Xb , что каждое ребро имеет один конец в Xа , а другой в Xb (рис. 5.5,а).
Ориентированный граф G называется двудольным, если его неориентированный двойник – двудольный граф (рис. 5.5,б,в).
Двудольный граф G=(Xа Xb, A) называют полным, если для любых двух вершин хi Xа и хj Xb существует ребро (хi,хj) в G=(X,A) (рис. 5.5,г).
Рис. 5.5. Двудольные графы: а, б, в – двудольные графы; г – полный двудольный граф
Для доказательства двудольности графа существует теорема.
Теорема о двудольности
Граф G = (X, A) является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины.
Доказательство
Пусть существует цикл нечетной длины хi1 , хi2, ...,хi q , хi1 . Без потери общности допустим, что хi1 Xа . Согласно определению одна из двух… Мы предположили, что длина цикла нечетная. Поэтому из соотношения хi q Xа… Для большей ясности можно рассмотреть цикл нечетной длины для графа, изображенного на рис. 5.6:
Лекция: Виды подграфов
Пусть дан граф G = (X, A), где X = {хi}, i = 1, 2, ..., n – множество вершин,… Подграфом G'= (X', A') исходного графа G называется такой граф G', для которого X' X и A' A. Примеры подграфов…
Сильно связные графы и компоненты графа
Орграф называется сильно связным, или сильным, если для двух любых различных его вершин хi и xj существует, по крайней мере, один путь, соединяющий…
Рис. 6.2. Виды графов по связности: а – cильно связный граф; б – односторонне связный граф; в – cлабо связный граф; г…
Метод Мальгранжа
Рассмотрим этот алгоритм более подробно на примере разбиения графа, представленного на рис. 7.1,a, матрица смежности которого показана на рис.…
Рис. 7.1.
Пути и маршруты
Например, для графа на рис. 8.1 последовательности дуг
M1: a6, a5, a9, a8, a4 ,
M2: a1, a6, a5, a9, a7 ,
Вес и длина пути
Граф G, описываемый тройкой вида
G = (X, A, С),
где Х = { хi }, i =1, 2, 3, ..., n – множество вершин,
Орциклы и циклы
М1: a3, a6, a11,
М2: a11, a3, a4, a7, a1, a12, a9 ,
М3: a3, a4, a7, a10, a9, a11.
Лекция: Алгоритм Дейкстра поиска кратчайших путей в графе
Наиболее эффективный алгоритм решения задачи о кратчайшем пути первоначально дал Дейкстра . В общем случае этот метод основан на приписывании… Дан граф G = (X, A, C) со взвешенными дугами, пример которого показан на рис.…
Присвоение начальных значений
Ш А Г 1. Положить L(s) = 0 и считать эту пометку постоянной. Для всех вершин хi s положить L(хi)= ∞ и считать эти пометки временными. За текущую рассматриваемую вершину с постоянной пометкой возьмем вершину p, т. е. положить p = s.
Обновление пометок
Ш А Г 2. Для вершин, входящих в прямое отображение вершины р, т. е. для всех хi , принадлежащих Г(p), пометки которых временные, изменить пометки в соответствии со следующим выражением:
L(хi) min [ L(хi), L(p) + C(p, хi) ].
Превращение пометки в постоянную
L(x*i)=min[L(xi)].
Ш А Г 4. Считать пометку вершины x*i постоянной и положить p=x*i .
Ш А Г 5(a ). {При нахождении пути отs к t}
Если текущая вершина p является искомой, т. е. p = t, то L(p) …
Первая итерация
L(x2)=min[L(x2),L(x1) + c(x1,x2)]=min[∞,0+10]=10
L(x7)=min[∞,0+3]=3
L(x8)=min[∞,0+6]=6
Вторая итерация
Рис. 9.3. Пометки в конце первой итерации
Ш А Г 2. Находим Г(х7) = { х2, х4, х6, х9}. Метки всех вершин временные, следовательно пересчитываем их значения:
Третья итерация
Рис. 9.4. Пометки в конце второй итерации
Ш А Г 2. Находим Г(х2) = {х1, х3, х7, х9}. Метки вершин х3 и х9 временные, следовательно пересчитываем их значения:
…
Четвертая итерация
L(х5) = min [ ∞ , 6 + 23 ] = 29,
L(х6) = min [ 17, 6 + 15 ] = 17,
L(х9) = min [ 12, 6 + 5 ] = 11.
Пятая итерация
L(х3) = min [ 23, 7 + 25 ] = 23,
L(х5)= min [ 29, 7 + 5 ] = 12,
L(х6)= min [17, 7 + 16] = 17.
Шестая итерация
L(х6) = min [17, 11 + 9] = 17.
Ш А Г 3. На данном шаге итерации имеем следующие временные метки вершин:
L(х3) = 23, L(х5) = 12, L(х6) = 17.
Седьмая итерация
L(х6)= min [17, 12 + 10 ] = 17.
Ш А Г 3. На данном шаге итерации имеем следующие временные метки :
L(х3) = 23, L(х6) = 17.
Восьмая итерация
L(х3) = min [ 23, 17 + 20 ] = 23.
Ш А Г 3. На данном шаге итерации имеем одну временную метку вершины: L(х3) =… Ш А Г 4. Все вершины имеют постоянные метки, поэтому алгоритм окончен.