Основы теории графов (Учебное пособие)


ГБОУ СПО «АМТ» КК
Учебное пособие
Основы теории графов
для студентов специальности
«Программирование в компьютерных системах»
Автор: Беляева Татьяна Юрьевна
Содержание
1. Понятие графа и его элементов. Типы графов 4
1.1. Из истории развития теории графов 4
1.2. Понятие графа. Элементы графа 5
1.3. Типы графов 6
1.4. Степень вершины. Однородные графы 7
1.5. Изоморфные графы 8
1.6. Плоские и неплоские графы 10
2. Части графа. Операции с частями графа 11
3. Маршруты. Связность графов. Эйлеровы и гамильтоновы графы 13
3.1. Маршруты, цепи и циклы 13
3.2. Связность и разделимость графов 14
3.3. Эйлеровы графы 15
3.4. Гамильтоновы линии 16
4. Матричный способ задания графов 16
4.1. Матрица смежности 17
4.2. Матрица инцидентности 18
4.3. Список ребер 18
5. Ориентированные графы 19
5.1. Понятие ориентированного графа 19
5.2. Степени вершин орграфа 20
5.3. Ориентированные маршруты 20
5.4. Связность орграфов 21
5.5. Матрица смежности орграфа 22
5.6. Матрица инцидентности орграфа 23
5.7. Графы и бинарные отношения 23
6. Деревья 24
6.1. Понятие дерева. Свойства свободных деревьев 24
6.2. Дерево с корнем, ветви дерева 25
6.3. Типы вершин и центры деревьев 26
6.4. Ориентированное дерево 26
6.5. Бинарные деревья 27
7. Взвешенные графы. Раскраска графов 29
8. Приложения теории графов в различных областях науки и техники 31
8.1. Графы и информация 31
8.2. Графы и химия 32
8.3. Графы и биология 32
8.4. Графы и физика 33
Задания для самостоятельного решения 34
Контрольные вопросы 37

Понятие графа и его элементов. Типы графов
1.1. Из истории развития теории графов
4057651222375A
00A
Первая работа по теории графов была опубликована Л. Эйлером в 1736 году. Она содержала решение задачи о кенигсбергских мостах: «Можно ли совершить прогулку по городу таким образом, чтобы выйдя из любого места города, вернуться в него, пройдя в точности один раз по каждому мосту?»
110109024955500141541523749000220599025908000231076525654000 3644265-4445A
00A
4057659271000
101536500015392409525003769360920750036442659842500
1672590169545001644015245745003425190125730B
00B
5073015173355D
00D
121539040005B
00B
237744040005D
00D
1980565400050010725154000500
136779015240001501140247650010058402921000872490-698500225361524765002120265-6985003768090863600037680908636000
4724405016500
55816546355C
00C
3644265149860C
00C


Т.к. неважно, как проходит путь по частям суши, то их можно представить точками. А так как связи между этими частями осуществляются только через 7 мостов, то каждый из них можно изобразить некоторой линией, соединяющей соответствующие точки. В результате получается граф.
Эйлер дал отрицательный ответ на поставленный вопрос. Более того, он доказал, что подобный маршрут имеется только для такого графа, каждая из вершин которого связана с четным числом ребер.
Вначале теория графов имела дело в основном с математическими развлечениями и головоломками. Но уже в 19 веке графы стали использоваться при решении ряда важных практических проблем: при построении схем электрических цепей, молекулярных схем, при решении транспортных задач. Несмотря на это, теория графов как математическая дисциплина сформировалась только в 30-х годах 20 века, когда венгерский математик Денеш Кёниг ввел понятие «граф».
Теория графов тесно связана с такими разделами математики, как теория множеств, теория матриц, математическая логика и теория вероятностей. Во всех этих разделах графы применяют для представления различных математических объектов, и в то же время сама теория графов широко использует аппарат родственных разделов математики. Теория графов располагает также мощным аппаратом решения прикладных задач из самых разных областей науки и техники: в программировании, экономике, психологии, биологии.
1.2. Понятие графа. Элементы графа
Опр. Графом называется совокупность 2-х множеств: V (точек) и E (линий, соединяющих какие-либо две точки). Элементы множества V называются вершинами графа, а элементы множества E - его ребрами.
Обозначение: G
Напр.: Построим граф игр, сыгранных командами, если в соревнованиях участвуют 6 команд А, B, C, D, E и F, причем некоторые команды уже сыграли друг с другом:
А – с C, D, F; B – c C, E, F; C – c A, B;
329565151765B
C
D
F
E
A
00B
C
D
F
E
A
D – c A, E, F; E – c B, D, F; F – c A,B, D, E.

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

188087039687500Опр. Ребра с одинаковыми граничными вершинами называются кратными.
188214025400018808701206500
337185015621000Их можно изобразить так: 3
Опр. Вершины, которые не имеют инцидентных ребер, называются изолированными вершинами.
Напр.: В графе:
9677402190750014344652114550099631521145500 e1 v3 е6 – петля
v2 e2 е2 и е3 – кратные ребра
93916515240002152651905000 v1 e1 e4 e5 v4 v4 – изолированная вершина
151066529807000 v3 и v5 – смежные инцидентны ребру е5 v5 e6
1.3. Типы графов
Опр. Если множества V и E конечны, то граф называется конечным. Конечный граф, содержащий p вершин и q ребер, называется (p; q) – графом.
Опр. Граф, состоящий только из изолированных вершин, называется пустым или нуль-графом.
Обозначение: Оп, где п – число вершин
Напр.:
О1 - О2 - О3 - О4 -

Опр. Граф без петель и кратных ребер называется простым.
Опр. Простой граф, в котором любые две вершины соединены ребром, называется полным.
Обозначение: Uп, где п – число вершин
Напр.:
505396531750046539153175004653915-95250046545503175004654550317500128206511811000304419041910002758440419100027584404191000 U2 - U3 - U4 -
465391511366500
Опр. Если множество вершин простого графа V допускает такое разбиение на два непересекающиеся подмножества V1 и V2 , что не существует ребер, соединяющих вершины одного и того же подмножества, то он называется двудольным или биграфом.
Напр.:
96774052387500967740285750009201152857500092011595250009677405715000V1 ●●● ●●●● V2
Опр. Граф без петель, но с кратными ребрами называется мультиграфом.
Опр. Граф, содержащий хотя бы одну петлю, называется псевдографом.
(!!) В псевдографе могут быть кратные ребра.
1.4. Степень вершины. Однородные графы
Опр. Число ребер, инцидентных вершине, называется степенью вершины.
Обозначение: ρ(vi)(!!) При подсчете степени вершины петля учитывается дважды.
Так, для графа игр: (А) = (В) = (Д) =(Е) = 3, (F) = 4, (C) = 2.
Опр. Вершины, степени которых являются четными числами, называются четными вершинами. Вершины с нечетной степенью называются нечетными.
Опр. Вершина, степень которой равна 1, называется концевой вершиной.
(!!) Очевидно, что:
1) степень изолированной вершины равна 0;
2) сумма степеней всех его вершин равна удвоенному числу ребер, т.е. является четным числом;
3) число нечетных вершин любого графа четно.
Опр. Граф, степени вершин которого одинаковы и равны r, называется однородным степени r.
843915561975004819655619750079629093345007962909334500481965752475004819659525000Напр.:
- однородный степени 3 (полный)
415290381000 920115-254000-264160-254000415290-2540001367790-254000415290-254000415290-254000
89154060960 - однородный степени 4 (неполный)
386715111125009156701225550041529011620500
(!!) Полный граф с п вершинами – всегда однородный степени (п – 1), а пустой граф – однородный степени 0.
1.5. Изоморфные графы
Один и тот же граф можно изобразить по-разному, т.к. вершины можно располагать на плоскости произвольно и ребра рисовать либо прямыми линиями, либо кривыми.
4653915274320A
00A
Так, например, три графа, изображенные на рисунках,
5530215226695E
00E
4234815251460004819650251460004234815251460001482090259080A
F
B
C
D
E
00A
F
B
C
D
E
-203835169545B
C
D
F
E
A
00B
C
D
F
E
A

3891915350520D
00D
495871550165004234815501650042348155016500
5596890235585C
00C
495871532321500423481511176000
389191583185F
00F
4872990281940B
00B
423481517081500
в некотором смысле, один и тот же граф, т.к. они содержат одну и ту же информацию.
Опр. Два графа называются изоморфными, если они имеют одно и то же число вершин, и для любых 2-х вершин первого графа, соединенных ребром, соответствующие им вершины второго графа тоже соединены ребром и обратно.
Нередко приходится решать вопрос о том, являются ли два данных графа изоморфными. Иногда сразу ясно, что это не так. Например, графы
5581654572000320040-381000192976543815001929765438150019297654381500
32004018161000
не могут быть изоморфными, т.к. они имеют разное число вершин.
Не могут быть изоморфными и графы
2444115-70485002396490-70485002444115-70485002167890-7048500558165-7048500472440-7048500558165-7048500177165-7048500216789018669000239649018669000216789018669000263461518669000216789018669000758190139065001771651390650017716513906500
23964901346200047244013462000
т.к. у них неодинаковое число ребер.
Однако, если сразу не видно, как доказать, что два графа не изоморфны, то вопрос об их изоморфности может оказаться довольно трудным. Например, рассмотрим два изоморфных графа:
2644140400051
001
558165400051
001

19107151727202
3
4
5
6
7
002
3
4
5
6
7
10629902012955
005
-514351727204
004
65341519177000100965191770006534151917700026289019177000
87249012001500262890120015002628901200150010058401200150010096512001500
12058651346202
002
-1752601346207
007
33909028702000100965287020001009652870200087249028702000
758190584206
006
100965584203
003
3390901079500
Их изоморфность становится очевидной только после соответствующего обозначения их вершин.
1.6. Плоские и неплоские графы
Сравним два изоморфных графа, изображенных на рисунках:
2577465209550025774652095500208216520955008191597155008191597155009105909715500819159715500819159715500
257746520193000208216520193000
2082165106680008191510668000
На первом из них ребра пересекаются в точке, не являющейся вершиной графа, на втором – все точки пересечения ребер графа служат его вершинами.
Опр. Граф называется плоским, если его ребра не пересекаются в точках, отличных от вершин данного графа.
Опр. Граф называется планарным, если существует изоморфный ему плоский граф, т.е. если его можно изобразить на плоскости таким образом, чтобы его ребра пересекались только в вершинах.
Так, граф, изображенный на первом рисунке, является планарным, т.к. существует изоморфный ему граф, не имеющий лишних точек пересечения.
Примерами плоских графов являются карты дорог, планы городов, где улицы служат ребрами, а площади и уличные перекрестки – вершинами. Еще одним примером применения плоских графов служит построение схем электрических цепей. Так, один из наиболее эффективных способов массового производства стандартных электрических схем для радио- и телевизионных приемников состоит в том, что схема наносится печатным способом в виде металлической фольги на бумажную или пластмассовую основу. Однако, для того чтобы оно было осуществимо, граф рассматриваемой сети проводов должен иметь плоское представление, ведь пересечение 2-х ребер привело бы к короткому замыканию в системе.
Задача о трех колодцах. Можно ли от каждого из 3-х домов проложить тропинку к каждому из 3-х колодцев так, чтобы тропинки не пересекались?
8534409588500853440958850014249409588500202501579375001424940958850014249409588500872490958850085344095885008724909588500 ● ● ●

● ● ●
Задача не может быть решена положительно, т.к. граф этой задачи не является плоским.
2. Части графа. Операции с частями графа
Опр. Граф G = (V; E) называется частью графа G = (V; E), если V V и Е Е.
Опр. Часть графа, которая не содержит изолированные вершины, называется подграфом.
Опр. Часть графа, которая, наряду с некоторым подмножеством ребер графа, содержит и все вершины графа, называется суграфом.
48926755651500340614021844000Напр.:v3v3v2e2v3v2e2
291084049530-394335106680100965381000174879075565003406140180340004892040749300012153903810009867903810001104903181350011049038100010096531813500v2e2v2e2v3
e6е7e3e6 e1 e111049031369000 e1e4v1v4
v1e5 v1v1
v4
граф часть графа подграф суграф
Пусть даны две части графа G: G1 и G2
1. Объединение графов – это граф G = G1 U G2, множества вершин и ребер которого определяются так: V = V1 ∪ V2, E = E1 ∪ E2.
2. Пересечение графов – это граф G = G1 ∩ G2, множества вершин и ребер которого определяются так: V = V1 ∩ V2, E = E1 ∩ E2.
Если V1 ∩ V2 = ∅ и E1 ∩ E2 = ∅, то графы называются непересекающимися.3. Сложение по модулю 2 – это граф G = G1 ⊕ G2, множество вершин которого V = V1 ∪ V2, а множество ребер E = (E1 ∪ E2) \ (E1 ∩ E2).
Напр.: Найдем G1 ∪ G2, G1 ∩ G2 и G1 ⊕ G2, если - части графа
3034665240665356806591440001510665140970003676651409700036766514097000G1 v3G2v3
356743028575003676657810500 v2v2356870013525500 v1v1v4v4374903925463515201901403350367665130810367665130810G1 ∪ G2 v3 G1 ∩ G2 v3
37490401993900-14668527940003676651993900 v2 v2367665290830
v1 v1 ●
v4 v4
G1 ⊕ G2
17868901327150501014113665 v3
342906985v2
501014203200 v1
v4
4. Дополнение графа
Пусть G - часть графа G, тогда совокупность всех ребер графа G, не принадлежащих его части G, вместе с инцидентными вершинами образует дополнение части G до графа G.
Так, дополнением для G2 будет граф:
15709861752601824990165735539114165735 v3
v2
v4
3. Маршруты. Связность графов. Эйлеровы и гамильтоновы графы
3.1. Маршруты, цепи и циклы
Опр. Маршрутом длины т называется последовательность т ребер графа (не обязательно различных) таких, что два соседних ребра имеют общую вершину.
224409012827000 e2
22345659334500255841593345002234565933450013868409334500Напр.: v2e3 v3
v1e1 e6 e4
v4
23012407493000 v5
e5
Маршрут (e1, e2, e3, e6, e5, e6) имеет длину т = 6, проходит через вершины v1, v2, v3, v2, v5, v5, v2 и соединяет вершины v1 c v2.
Маршрут (e5, e4, e3, e1) имеет длину т = 4, проходит через вершины v5, v5, v3, v2, v1 и соединяет вершины v5 c v1.
Опр. Маршрут, все ребра которого различны, называется цепью, а маршрут, для которого различны все вершины, называется простой цепью.
Напр.: (е2; е4; е6) – цепь
(е1; е2; е4) – простая цепь
Опр. Маршрут, который приводит в ту же вершину, из которой начался, называется замкнутым.
Опр. Замкнутая цепь называется циклом, а простая замкнутая цепь – простым циклом.
Напр.: (е2; е4; е5; е6) – цикл
(е3; е6; е4) – простой цикл
Опр. Граф называется циклическим, если он содержит хотя бы один цикл, в противном случае он называется ациклическим.
(!!) Очевидно, что мультиграфы и псевдографы являются циклическими.
3.2. Связность и разделимость графов
Опр. Две вершины графа называется связанными, если существует маршрут, соединяющий эти вершины. Граф, любая пара вершин которого связана, называется связным графом.
Очевидно, в связном графе между любыми двумя вершинами существует простая цепь, т.к. из связывающего их маршрута всегда можно удалить циклический участок, проходящий через некоторую вершину более одного раза.
Если граф несвязный, то множество его вершин можно единственным образом разделить на непересекающиеся подмножества, каждое из которых содержит все связанные между собой вершины и вместе с ребрами образует связный подграф. Такие подграфы называются компонентами несвязного графа.
400621593345003596640933450028346409334500283464093345005295909334500Напр.:
40062151460500052959050800005295905080000
283464015811500
Связный Несвязный
Связный граф можно разделить на несвязные подграфы, если удалить из него некоторые вершины и ребра. При удалении вершин исключаются и все ребра, для которых эта вершина является граничной, при удалении же ребер вершины сохраняются.
Опр. Вершина, удаление которой превращает связный граф в несвязный, называется точкой сочленения. Ребро с такими свойствами называется мостом.
(!!) При наличии моста в графе имеются, по крайней мере, одна точка сочленения.
3453765264160003806190264160004615815264160004301490264160004615815264160002806065264160001558290-571500Напр.:точки сочленения
7677152540001624965254000767715254000767715254000
280606511176000467296511176000430149012128500280606512128500345376511176000377190207010001771652051050037719020701000
858520307340003771901739900076771517399000 мост
точкасочленения
Опр. Связный граф называется разделимым, если он имеет хотя бы одну точку сочленения, в противном случае граф называется неразделимым.
3.3. Эйлеровы графы
370141564008000Опр. Цикл, который содержит все ребра графа, называется эйлеровым циклом, а граф, в котором имеется такой цикл, называется эйлеровым графом.
Эйлеров цикл можно считать следом пера, вычерчивающего этот граф, не отрываясь от бумаги. Т.о., эйлеровы графы – это такие графы, которые можно изобразить одним росчерком пера, причем процесс такого изображения начинается и заканчивается в одной и той же точке.
314896514795500342519014795500Напр.:
4819651797050048196518859500
304419016510003044190165100031489651651000140589078740009677408826500
48196566675009677406667500
Т1. (Эйлера) Конечный неориентированный граф эйлеров тогда и только тогда, когда он связен и степени всех его вершин четны.
Можно поставить задачу и об отыскании цепи, которая бы начиналась в одной вершине, оканчивалась в некоторой другой вершине и проходила бы по всем ребрам в точности по одному разу. Такие цепи называется эйлеровыми.
Т2. Для того чтобы на связном граф имелась эйлерова цепь, необходимо и достаточно, чтобы в графе были ровно две нечетные вершины, которые и были бы концами этой цепи.
958215254000358140254000Напр.:
35814012636500358140124460003581401244600014535151244600038671512446000

92011575565
35814019621500
3.4. Гамильтоновы линии
Опр. Простой цикл, который проходит через все вершины графа, называется гамильтоновым.
В отличие от эйлерового этот цикл не покрывает всех ребер графа.
Напр.:
758190224155001805940223520009201152235200092011522352000164401522352000
13677901117601043940111125107251511430000164401511430000136779011430000136779011430000136779028575000116776528575000
967740287655001567815287655009677402095500758190290830001805940290830001015365241300017202152413000116776529083000146304029083000156781524130001463040908050012630152908300011677659080500
11677651016001367790101600136779057150007581905715000136779023812500136779010477500
Если критерий существования эйлерового цикла очень прост, то для гамильтоновых циклов никакого общего правила не найдено.
4. Матричный способ задания графов
4.1. Матрица смежности370141564008000
Отношение смежности на множестве вершин можно определить, представив каждое ребро как пару смежных вершин, т.е.
ek = (vi; vj) = (vj; vi).Очевидно, что петля при вершине vi представляется парой (vi; vi.).
Множество вершин V вместе с определенным на нем отношением смежности полностью определяет граф. При этом граф можно представить матрицей смежности, строки и столбцы которой соответствуют вершинам графа, а ее (i; j) - элемент равен числу кратных ребер, связывающих вершины vi и vj.
Напр.: Для графа
224409012827000 e2
22345659334500255841593345002234565933450013868409334500 v2e3 v3
v1e1 e6 e4
v4
23012407493000 v5
e5
матрица смежности имеет вид:
v1 v2 v3 v4 v5 0 1 0 0 0 v1
1 0 2 0 1 v2
0 2 0 0 1 v3
0 0 0 0 0 v4
0 1 1 0 2 v5
(!!)1 Матрица смежности симметрична относительно главной диагонали. В столбцах и строках, соответствующих изолированной вершине, все элементы равны нулю. Петле соответствует «2» на главной диагонали.
(!!)2 Элементы матрицы простого графа равны нулю или единице, причем все элементы главной диагонали нулевые.
4.2. Матрица инцидентности
Рассматривая инцидентность вершин и ребер (p; q) – графа, можно представить его матрицей инцидентности размера p × q, строки которой соответствуют вершинам, а столбцы – ребрам. Элементы этой матрицы определяются по правилу: (i; j) - элемент равен 1, если вершина vi инцидентна ребру еj, и равен 0, если vi и еj не инцидентны.
Так, для изображенного в предыдущем пункте графа матрица инцидентности имеет вид:
е1 е2 е3 е4 е5 е6 1 0 0 0 0 0 v1
1 1 1 0 0 1 v2
0 1 1 1 0 0 v3
0 0 0 0 0 0 v4
0 0 0 1 2 1 v5
(!!) Каждый столбец матрицы инцидентности содержит два единичных элемента. Если в вершине vi имеется петля, то в соответствующей клетке ставится цифра 2. Нулевая строка соответствует изолированной вершине.
4.3. Список ребер
Это еще один способ задания графа. Каждая строка этого списка соответствует ребру: в ней записаны номера вершин, инцидентных ему.
Для рассмотренного выше графа список ребер можно записать следующим образом:
Ребра Вершины
е1 1,2
е2 2,3
е3 2,3
е4 3,5
е5 5,5
е6 2,5

5. Ориентированные графы
5.1. Понятие ориентированного графа
Часто связи между объектами характеризуются вполне определенной ориентацией. Например, на некоторых улицах допускается одностороннее движение, ток по проводам течет в одном направлении. Вершины соответствующих графов оказываются неравноправными, они рассматриваются в определенном порядке. При этом каждому ребру можно приписать направление от первой из вершин ко второй. Для указания направления соответствующее ребро отмечается стрелкой.
Опр. Направленные ребра называется дугами, а граф, содержащий их, - ориентированным графом. Первая по порядку вершина дуги называется ее началом, вторая – концом.
Напр.:v1е7v2
9772655905500232981513335007562856096000232981562865009817106286500232981453340009817096286500 e3e4
2325370209550023298151778000 e1 e2 е8 e5 v3
98171021463000e6
v5е9v4
Опр. Две кратные дуги называются строго параллельными, если они одинаково направлены, и нестрого параллельными, если противоположно направлены.
Напр.: е1 и е2 – строго параллельные дуги
е3 и е4, е5 и е6 – пары нестрого параллельных дуг
(!!) Нестрого параллельные дуги, отображающие ориентацию связи в обоих направлениях, по существу, равноценны неориентированной связи и могут быть заменены ребром.
Опр. Граф, который содержит ребра и дуги, называется смешанным.
Так, изображенный выше ориентированный граф можно изобразить в виде смешанного:
v1 v2
2325370381000757555-571500990600-3810009912355715002329180-381000989965-381000
23304502730500 v3
99123515748000
v5v4
(!!) Всякий неориентированный граф можно превратить в ориентированный, заменив в нем каждое ребро на пару нестрого параллельных дуг.
Опр. Если изменить направления всех дуг орграфа на противоположные, то получится орграф, обратный исходному.
5.2. Степени вершин орграфа
В орграфе различают положительные +(vi)и отрицательные -vi степени вершин, которые равны соответственно числу исходящих из vi и входящих в vi дуг.
Напр.: +(v1) = 3 -(v1) = 0
758190245745007581902647950012058652616200016814802457450075819026225500v1v2 +(v4) = 1 -(v4) = 2
75819013779500120586512827000 v5
72009025654000
v4 v3
(!!) Очевидно, суммы положительных и отрицательных степеней всех вершин орграфа равны между собой и равны числу всех дуг.
Опр. Вершина, положительнаяотрицательная степень которой равна нулю, называется стокомистоком.
Так, v1 – исток, v5–сток
(!!) Концевая вершина орграфа может быть либо стоком, либо истоком.
5.3. Ориентированные маршруты
Маршруты на орграфе определяются аналогично, с той лишь разницей, что начальная вершина каждой последующей дуги маршрута должна совпадать с конечной вершиной предыдущей дуги. Иначе говоря, движение по маршруту допускается только в указанных направлениях (по направлению стрелок).
Опр. Маршрут, не содержащий повторяющихся дуг, называется путем, а не содержащий повторяющихся вершин, - простым путем.
Опр. Замкнутый путь называется контуром, а простой замкнутый путь – простым контуром.
Опр. Орграф, содержащий хотя бы один контур, называется контурным.
Задачи, связанные с маршрутами в орграфе, имеют большое практическое значение. Наиболее часто встает вопрос о минимальных и максимальных расстояниях и о числе маршрутов определенной длины.
ПР. Дан орграф. Сколько в нем маршрутов длины 3? (8)
1 2 3
19964401162050090106511620500199643911620500901065116205009010641162050090106511620400199644011620400 ● ● ●
90106513525400 ● ●
4 5

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

5.5. Матрица смежности орграфа
Каждую дугу орграфа ек представляют как упорядоченную пару вершин (vi; vj), при этом (i; j) - элемент матрицы смежности равен числу дуг, направленных от вершины vi к вершине vj.
Напр.: v1 е v2
2329815133350075628560960002329815628650098171062865002329815533400098171062865009817105334000 e3 e4
2329815177800023298151968500 e1 e2 е8 e5 v3
9817108191500e6
v5е9v4
v1 v2 v3 v4 v5 1 1 v1
1 1 v2
1 1 v3
1 1 v4
2 v5
(!!) Матрица смежности орграфа, в общем случае, несимметрична. Петлям соответствуют единицы на главной диагонали. Нулевая строка и нулевой столбец с тем же номером соответствуют изолированной вершине.
5.6. Матрица инцидентности орграфа
В случае орграфа ненулевой элемент матрицы инцидентности равен +1, если vi – начальная вершина дуги еj, и равен -1, если vi – конечная вершина дуги еj. В клетке, соответствующей петле, ставится ±1.Напр.: Матрица смежности для приведенного выше орграфа имеет вид:
е1 е2 е3 е4 е5 е6 е7 е8 е9 -1 -1 1 1 v1
1 -1 -1 v2
-1 1 1 -1 v3
-1 1 -1 1 v4
1 1 -1 v5
5.7. Графы и бинарные отношения
Пусть на множестве Х задано бинарное отношение R. Ему соответствует ориентированный граф, вершины которого изображают элементы из Х, а дуга (xi; xj) существует тогда и только тогда, когда xi R xj.
Если имеют место соотношения xi R xj и xj R xi, то вершины связываются 2-мя нестрого параллельными дугами, которые можно заменить ребром. Таким образом, симметричному отношению соответствует неориентированный граф.
Соотношению xi R xi соответствует петля, выходящая из xi и входящая в ту же вершину. Значит, если R рефлексивно, то соответствующий граф имеет петли во всех вершинах.
Если R транзитивно, то в графе для каждой пары рёбер (xi; xj) и (xj; xk) имеется замыкающее ребро (xi; xk).
Если бинарное отношение х R у устанавливает связь между элементами х ∈Х и элементами у ∈У, то граф такого отношения будет ориентированным биграфом.
Рассмотрим теперь соответствие между операциями над отношениями и операциями над графами. Для каждого отношения R существует обратное ему отношение R-1, граф которого отличается от графа отношения R тем, что направления всех дуг заменены на противоположные.
6. Деревья
6.1. Понятие дерева. Свойства свободных деревьев
Опр. Связный ациклический граф называется деревом.
(!!) Очевидно, что деревья не имеют петель и кратных ребер, т.е. являются простыми графами.
Среди различных деревьев выделяют 2 важных частных случая:
Последовательное дерево, представляющее собой простую цепь.
Звездное дерево, в котором одна из вершин смежна со всеми остальными вершинами.
ПР. а) Различные свободные деревья с 4-мя вершинами:
340614014605000
4248155080000901065508000060579051435004248155080000
321564016129000337756516129000

б) Различные свободные деревья с 5-ю вершинами:
4663440666750049015656667500324421512382500
488442023622000452247023622000321564016954500260604016954500219646516954500113919016954500796290361950042481536195005334012192000


в) Различные свободные деревья с 6-ю вершинами:
490156514795500
326326530226000489204030226000434911525463500388239025463500180594014986000136779030226000108394583185005200658318500-381020510500
4501515268605003882390268605003882390268605003329940268605002747010268605006515103238500012915903238500012915903238500012915908763000-381021145500
7239011811000
-2286010604500
7239022034500-15621022034500723902032000
32632651231902196465123190
326326510922027965401092202196465109220

Очевидно:
Для каждой пары вершин дерева существует единственная соединяющая их простая цепь.
Дерево на множестве р вершин всегда содержит q = p – 1 ребер.
Любое ребро дерева является мостом.
В любом дереве имеются, по крайней мере, 2 концевые вершины.
При добавлении в дерево ребра образуется цикл, а при удалении хотя бы одного ребра дерево распадается на компоненты, каждая из которых представляет собой также дерево или изолированную вершину.
Опр. Несвязный граф, компонентами которого являются деревья, называется лесом.
(!!) Лес из к деревьев, содержащий р вершин, имеет в точности р – к ребер.
Опр. Остовным деревом (остовом, каркасом или скелетом) неориентированного графа G называется его подграф, содержащий все вершины графа и являющийся деревом.
Ребра графа, не входящие в остов, называются хордами графа относительно остова.
6.2. Дерево с корнем, ветви дерева
Если в дереве отметить некоторую вершину v0, то ее называют корнем дерева, а само дерево – деревом с корнем.
Обозначая вершины, смежные с вершиной v0 соответственно v1, v2,…, с v1 – v11, v12,…,а с v2 – v21, v22,…и т.д., можно построить дерево с корнем.
(!!) Очевидно, что каждая вершина дерева может служить его корнем.
Если v – вершина дерева с корнем v0, тогда множество всех вершин, связанных с корнем цепями, проходящими через вершину v, порождает подграф, который называется ветвью вершины v в дереве с корнем v0. Очевидно, что эта ветвь связна и сама является деревом с корнем в этой вершине v.
6.3. Типы вершин и центры деревьев
Пусть дано конечное дерево G. Все его концевые вершины называются вершинами типа 1. Если удалить из графа все такие вершины вместе с инцидентными им ребрами, то получится подграф G, который будет деревом. Концевые вершины дерева G называются вершинами типа 2 в дереве G. Аналогично определяются вершины типов 3, 4, и т.д.
Ясно, что в конечном дереве G имеются вершины лишь конечного числа типов.
Опр. Вершины максимального типа называются центрами дерева.
(!!) Дерево имеет либо 1, либо 2 центра.
Опр. Каждая цепь, соединяющая центр дерева с его концевой вершиной, называется радиальной, а цепь, соединяющая две концевые вершины дерева и проходящая через его центр или оба центра (если их два), - диаметральной цепью.
(!!) Если в дереве 1 центр2 центра, то длина диаметральной цепи равна 2к – 22к – 1, где к – максимальный тип вершин дерева.
6.4. Ориентированное дерево
Опр. Ориентированное дерево называется прадеревом с корнем v0, если существует путь между вершиной v0 и любой другой его вершиной.
(!!) Прадерево имеет единственный корень, и все ребра в нем имеют направление от корня. При этом в каждую вершину ордерева входит только одно ребро.
891540346710004248159906000
891540193675008915401365250042481531750001524019367500152403175000
8248653175004248151460500042481531750042481514605000
701040212725007010402127250070104010795000
Опр. Концевая вершина ордерева называется листом.
Опр. Путь из корня в лист называется ветвью.
Опр. Длина наибольшей ветви ордерева называется его высотой.
Опр. Уровнем вершины ордерева называется расстояние от корня до этой вершины. Вершины одного уровня образуют ярус дерева.
(!!) Корень имеет уровень равный 0.
Опр. Если изменить направления всех ребер ордерева на противоположные (к корню), то получится орграф, который называется сетью сборки.
6.5. Бинарные деревья
Опр. Бинарным (двоичным) деревом называется ориентированное дерево, в котором каждая вершина (узел) имеет не более двух потомков.
Бинарное дерево имеет корень и два непересекающихся подмножества, каждое из которых само является бинарным деревом. Эти подмножества называются правым и левым поддеревьями исходного дерева.
8915401243330294894012147552948940852805138684012433300013868406242051786890624205208216599568022726659956802272665624205245364062420517868902336802167890233680Напр.:
Для практических целей, обычно, используют два подвида бинарных деревьев: двоичное дерево поиска и двоичная куча.
Опр. Двоичное дерево называется двоичным деревом поиска, если его элементы расположены так, что для каждого элемента n все элементы в левом поддереве n будут меньше, чем n, а все элементы в правом поддереве - больше, чем n.
В общем случае существует огромное число двоичных деревьев поиска (различной формы) для любого заданного набора элементов.
Напр.: Три двоичных дерева поиска с одним и тем же набором элементов (2, 3, 5, 7, 8)

ПР. Предположим, что нужно сформировать двоичное дерево, узлы (элементы) которого имеют следующие значения признака: 20, 10, 35, 15, 17, 27, 24, 8, 30. В этом же порядке они и будут поступать для включения в двоичное дерево.

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


Существуют также кучи, где значение в любой вершине, наоборот, меньше, чем значения ее потомков.
7. Взвешенные графы. Раскраска графов
Часто, особенно когда графы используются для моделирования реальных систем, их вершинам, или ребрам, или и тем, и другим приписываются некоторые числа. Природа этих чисел может быть самая разнообразная. Например, если граф представляет собой модель железнодорожной сети, то число, приписанное ребру, может указывать длину перегона между двумя станциями, или наибольший вес состава, который допустим для этого участка пути, или среднее число поездов, проходящих через этот участок в течение суток и т.п. Что бы ни означали эти числа, сложилась традиция называть их весами, а граф с заданными весами вершин и или ребер - взвешенным графом.
В графе можно взвесить вершины таким образом, что каждой вершине будет сопоставлено целое число. Если числа трактовать как номера краски, то такое взвешивание вершин называют вершинной раскраской графа.
Раскраска называется правильной, если никакие смежные вершины не окрашены в один цвет.
Раскраска графа, в которой используется минимальное число красок, называется минимальной. Число красок минимальной раскраски является одной из характеристик графа и называется хроматическим числом. Так, например, хроматическое число биграфа равно 2. Двум равно и хроматическое число любого дерева. Дерево – биграф?
С задачей определения минимальной раскраски графа связана известная проблема четырех красок: «Пусть имеется географическая карта. Можно ли, используя только 4 краски, изобразить эту карту так, чтобы соседние страны (имеющие общую границу) были окрашены в разный цвет?» (В соответствующем графе вершинами являются страны, а смежными вершинами являются соседние страны. После 1976 года ответ на этот вопрос является положительным.)
В теории графов ставится часто вопрос о реберной раскраске графов. Какое минимальное число цветов (это число иногда называют реберно-хроматическим) нужно, чтобы раскрасить ребра графа так, что любые 2 ребра, имеющие общую вершину, были бы окрашены в разный цвет? Для реберно-хроматического числа графа верна следующая теорема Визинга: Если в графе максимальная степень вершин равна r, то реберно-хроматическое число равно либо r, либо r +1.
Опр. Минимальное остовное дерево в связанном, взвешенном, неориентированном графе - это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него ребер.
Задача о нахождении минимального остовного дерева часто встречается в подобной постановке: допустим, есть n городов, которые необходимо соединить дорогами, так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Разрешается строить дороги между заданными парами городов и известна стоимость строительства каждой такой дороги. Требуется решить, какие именно дороги нужно строить, чтобы минимизировать общую стоимость строительства.
Эта задача может быть сформулирована в терминах теории графов как задача о нахождении минимального остовного дерева в графе, вершины которого представляют города, ребра - это дороги, которые можно проложить напрямую между двумя городами, а вес ребра равен стоимости строительства соответствующей дороги.
Напр.:


8. Приложения теории графов в различных областях науки и техники 8.1. Графы и информация
Двоичные деревья играют весьма важную роль в теории информации. Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.
Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось.
Таким образом, если кому-то понадобится взять интервью у различных людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.
8.2. Графы и химия
Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов.
Все атомы углеводорода четырехвалентны, все атомы водорода одновалентны. Молекула каждого предельного углеводорода представляет собой дерево. Если удалить все атомы водорода, то оставшиеся атомы углеводорода также будут образовывать дерево, каждая вершина которого имеет степень не выше 4. Следовательно, число возможных структур предельных углеводородов, т. е. число гомологов данного вещества, равно числу деревьев с вершинами степени не больше четырех.
Таким образом, подсчет числа гомологов предельных углеводородов также приводит к задаче о перечислении деревьев определенного типа. Эту задачу и ее обобщения рассмотрел Д. Пойа.
8.3. Графы и биология
Деревья играют большую роль в биологической теории ветвящихся процессов. Для простоты мы рассмотрим только одну разновидность ветвящихся процессов - размножение бактерий. Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства одной бактерии мы получим двоичное дерево.
Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.
8.4. Графы и физика
Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.
Печатной схемой называют пластинку из какого-либо диэлектрика (изолирующего материала), на которой в виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы (диоды, триоды, резисторы и другие), их пересечение в других местах вызовет замыкание электрической цепи.
В ходе решения этой задачи необходимо вычертить плоский граф, с вершинами в указанных точках.

Задания для самостоятельного решения
Определите типы графов:
72961523685500978535236855002729865122555002628903365500
5213352222500051054022225000739140222250003396615222250032442152222500272986522225002729865222250026301702222500
275844020383500
272986512636500362521512890500
324421553975002729865539750027298655397500


681990359410009582153594100068199035941000118681535941000144399029273500297751522606000

2921002457450077597018986500
153924011112500758190149225003308351460500079756017462500118681513652500380619026987500352996526987500380619022225003168015222250038061902222500-47053574612500
31686507302500382524011811000352996511811000380619011874500316865011811000316801511811000
29146597155003105158699500
Нарисуйте фигуру, не отрывая руки:
35566356235700034810705060950033362903733803128010199390
Постройте граф, соответствующий данной матрице смежности:
1 2 1 2 1 1 2 2 2 1 1 1 1 2 1
1 Охарактеризуйте полученный граф.
Найдите степени всех его вершин.
3) Найдите в нем точки сочленения и мосты, если они есть.
4) Запишите для него матрицу инцидентности.
4. Дан граф:
16249656032500 v6
167640285751624965176530007677152095500v7
1624965254000767715254000767715254000767715254000377190540385001771655384800037719054038500v5

v2
v3 v4
133286512001540576543815007772403873500 v1
1) Постройте:
- часть графа, состоящую из 4 вершин и 3 ребер;
- суграф с 5 ребрами.
2) Найдите какой-либо маршрут длины 5, 6, 7, 8, 9 и 10 между вершинами v4 и v2.
Какова наименьшая длина такого маршрута?
5. Постройте граф, соответствующий данной матрице смежности:
1 1 1 1 1 2
2 1 1 1
1 1 1) Определите все имеющиеся в нем виды маршрутов.
2) Найдите степени его вершин
6. Во множестве N = 1;2;3;4;5 задано бинарное отношение R = 1;2;1;4;1;5;2;3;3;2;3;4;4;4;4;5;5;3;(5;4). Для данного отношения запишите область определения и область значений. Нарисуйте граф этого отношения. Составьте для него матрицу смежности и инцидентности.
6. Представьте ордерево в ярусном виде, обозначив его вершины соответствующим образом. Найдите листья, вершины всех ярусов, высоту дерева. 8343901905000034861519050000348615357505001676403575050016764068199000-11811068199000-19431068199000-19431072961500-33718572961500-50863572961500291465106362500167640106362500145351519050000145351519050000145351547625001863090476250018630904762500186309057213500

Контрольные вопросы
Дайте понятие графа.
Какие ребра называются кратными?
Что такое петля?
Какие две вершины называются смежными?
Какая вершина называется изолированной?
Объясните, что означает инцидентность вершин и ребер.
Дайте понятие нуль-графа.
Какой граф называется простым?
Дайте понятие полного графа.
Определите биграф.
Какой граф называется мультиграфом?
Дайте определение псевдографа.
Что означает степень вершины?
Какие существуют типы вершин в зависимости от четности их степени?
Какая вершина называется концевой?
Чему равна степень изолированной вершины?
Дайте понятие однородного графа.
Какие два графа называются изоморфными? Объясните, как проверить изоморфность графов.
Какой граф называется плоским?
Какой граф является планарным?
Дайте определение части графа.
Какая часть графа называется подграфом?
Что такое суграф?
Какие операции можно выполнять с частями графа? Определите каждую из них.
Дайте понятие маршрута длины т.
Какой маршрут называется цепью? простой цепью?
Дайте понятие замкнутого маршрута.
Что такое цикл? простой цикл?
Какой граф называется циклическим? ациклическим?
Дайте понятия эйлерового цикла и эйлеровой цепи.
Какой граф называется эйлеровым?
Какой цикл называется гамильтоновым?
Какие две вершины называются связанными?
Дайте определения связного и несвязного графов.
Какой граф называется разделимым?
Дайте понятие точки сочленения.
Какое ребро графа называется мостом?
Дайте понятие матрицы смежности.
Что представляет собой матрица инцидентности?
Как составляется список ребер?
Как называется направленное ребро?
Дайте понятие ориентированного графа.
Какие кратные дуги называются строго параллельными? нестрого параллельными?
Какой граф называется смешанным?
Как превратить неориентированный граф в ориентированный?
Дайте понятие графа, обратного данному.
Что понимают под положительной и отрицательной степенью вершины?
Что показывает сумма положительных (отрицательных) степеней всех вершин?
В чем состоит отличие ориентированного маршрута от неориентированного?
Дайте определения пути и простого пути.
Что такое контур? простой контур?
Какой граф называется контурным?
Определите понятие сильной связности орграфа.
Каковы особенности матрицы смежности оргафа?
Сформулируйте правило написания матрицы инцидентности орграфа.
Какой граф соответствует симметричному бинарному отношению?
В чем особенность графа, соответствующего рефлексивному бинарному отношению?
Какой граф называется деревом?
Что значит последовательное дерево? звездное дерево?
Сформулируйте свойства деревьев.
Что такое остовное дерево неориентированного графа?
Дайте понятие леса.
Какая вершина дерева может служить его корнем?
Определите ветвь вершины v у дерева с корнем v0.
Дайте определение центра дерева. Сколько центров может быть у дерева? Как найти центра дерева?
Дайте понятия радиальной и диаметральной цепи в дереве.
Какое дерево называют прадеревом с корнем?
Определите лист, ветвь, уровень вершины и ярус прадерева.
Как определить высоту прадерева?
Дайте определение бинарного дерева.
Как составляется двоичное дерево поиска? двоичная куча?
Что понимают под взвешенным графом?
Поясните, что такое хроматическое число графа? Каково хроматическое число дерева? биграфа?

Приложенные файлы

  • docx file4.doc
    Размер файла: 819 kB Загрузок: 3