Элементы теории графов

Основные понятия и определения

Теория графов представляет собой область дискретной математики, особенностью которой является геометрический подход к изучению объектов и связей между ними. Первые задачи теории графов относились к решению математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задача о перевозках и др.). В настоящее время теория графов получила широкое практическое применение. Графы используются при анализе и проектировании сетей электроснабжения, водоснабжения, газоснабжения, теплоснабжения; при анализе и проектировании транспортных сетей, грузовых и пассажирских перевозок; при разработке и воплощении в жизнь проектов строительства, разработки новых технологий и изделий, а также во многих других областях.

Основной объект теории графов — граф, его характеристики и обобщения.

Определение 2.1. Граф — это множество вершин V = {у,, у2, ..., у„} и множество неупорядоченных и упорядоченных пар вершин Е = {е2, ..., ет}.

Обозначается граф так: (7 = (V, Е). Неупорядоченная пара вершин называется ребром, упорядоченная пара — дугой. Граф, содержащий только ребра, называется неориентированным. Граф, содержащий только дуги, называется ориентированным или орграфом. Если граф содержит и ребра и дуги, он называется смешанным. Ориентация дуг указывается стрелкой.

На рис. 2.1 представлены все три указанные разновидности графов.

Пары вершин графа (7 могут соединятся двумя и более ребрами (дугами одного направления). Такие дуги (ребра) называются кратными. Граф с кратными дугами (ребрами) называется мультиграфом (рис. 2.2, а).

^2

Смешанный (а), неориентированный (б) и ориентированный (в) графы

Рис. 2.1. Смешанный (а), неориентированный (б) и ориентированный (в) графы

VI

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

Мультиграф (а) и псевдограф (б)

Рис. 2.2. Мультиграф (а) и псевдограф (б)

Вершины графа (7, соединенные ребром или дугой, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро (дуга), соединяющее две вершины графа (7, называется инцидентным этим вершинам, а любая из вершин — инцидентной ребру. Говорят, что ребро (и, г) соединяет вершины

и, у, а дуга < и, у > начинается в вершине и и направлена к вершине V или исходит из вершины и и заходит в вершину V.

Множество соседей вершины у, графа С — это множество смежных ей вершин, т.е. вершин, соединенных с V, ребрами. На рис. 2.2, а множество соседей вершины у4 — это вершины у2, у3,

^5 ’ V

Определение 2.2. Степенью вершины у, графа С, обозначаемой <3У , называется число ее соседей, или, что то же, число ребер, смежных у,, или число инцидентных ей ребер.

Для орграфов используют выражения «полустепень захода» и «полустепень исхода».

Определение 2.3. Полустепенью захода вершины у,. орграфа С

называется число заходящих в нее дуг. Полустепенью исхода вершины у, графа С называется число исходящих из нее дуг.

На рис. 2.2, а степень вершины у2 равна 5, степень вершины у5 — 3. На этом же рисунке (б) полустепень захода вершины у5 равна 3, исхода — 1. Полустепень захода вершины у, равна О, исхода — 2.

Сумма полустепеней исхода, а также сумма полустепеней захода в орграфе С равны числу его ребер |?|. Сумма степеней вершин неориентированного графа равна 2Е, где Е число ребер (дуг) графа.

Вершина у, графа С называется изолированной, если ее степень (I = 0. Если степень вершины у, =1, она называется концевой. На рис. 2.2, а вершина v1 является концевой, а вершина у8 изолированной.

Определение 2.4. Граф G называется полным, если он не содержит петель и каждые две различные его вершины соединены ребром.

На рис. 2.3 изображены полный (а) и неполный графы (б).

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

Таким образом, дополнением графа G (рис. 2.3, б) является граф G = (у,, у 2, у з, у4 , (у і, у2)> (v2,v3), (у4,у,))-

В полном графе Gen вершинами —— ребер.

Определение 2.6. Подграфом С = (V', Е') графа С = (V, Е) называется граф, у которого V' сКД'с Е. Если V' - V, то С' — ос-товной подграф графа С (рис. 2.4).

Полный (а) и неполный (б) графы (7

Рис. 2.3. Полный (а) и неполный (б) графы (7

У2

Граф (7 (а), его подграф (б) и остовной подграф

Рис. 2.4. Граф (7 (а), его подграф (б) и остовной подграф <7' (в)

^2

Определение 2.7. Неориентированный граф (7 = (У, Е) называется двудольным, если множество его вершин Сможет быть разбито на такие два непересекающиеся подмножества Уа, У, что каждое ребро графа (7 имеет один конец в Уа, а другой в . Ориентированный граф С двудольный, если неориентированный его двойник тоже двудольный граф (рис. 2.5).

Неориентированный (а) и ориентированный (б) двудольные графы

Рис. 2.5. Неориентированный (а) и ориентированный (б) двудольные графы

Множество вершин Уа неориентированного графа составляют вершины {а, Ь, с, с1, е}, множество вершин составляют вершины {/, g, /, у'}. Множество вершин Уа ориентированного графа составляют вершины {а, Ь, с, с/}, множество вершин составляют вершины {е, /, #}.

Определение 2.8. Паросочетанием неориентированного графа 6? = (V, Е) называется подмножество его ребер Е' с Е, выбранное так, что никакие два ребра из Е' не являются смежными, т.е. не имеют общей вершины.

Паросочетания в двудольном графе (а) и орграфе (б) показаны на рис. 2.6.

1 ? /г у

Е'= {(д,/),(М), (?,?),(

/ ё И у /

УХ/

а Ь с (1

Е'= {<а,?>,<Ь, у>, <с,И> ,<с], />} а) б)

Рис. 2.6. Паросочетание в неориентированном (я) и ориентированном (б) двудольном графе

Определение 2.9. Доминирующим множеством (покрытием) вершин орграфа С = {V, Е} называется такое подмножество его вершин V' с V, что для каждой вершины у,- е V', не входящей в множество V', т.е. у, е V' существует дуга, идущая из некоторой вершины множества V' в вершину .

На рис. 2.7 покрытиями являются следующие множества вершин: {у,, У4, V6}, {у,, У4}, {у3, у5, у6}•

Определение 2.10. Минимальным доминирующим множеством (покрытием) вершин орграфа С = {V, Е) называется доминирующее множество (покрытие) с минимальным числом вершин.

Минимальным покрытием для графа, изображенного на рис. 2.7, является множество вершин {у,, у4}.

Очень часто в практических применениях ребрам или дугам графа 6? = {V, Е} приписывают числовые значения — веса, которые в зависимости от смысла задачи отождествляются с расстоянием, временем или стоимостью.

Сеть с истоком а и стоком /

4 Рис. 2.8. Сеть с истоком а и стоком /

Рис. 2.7. Вершинные покрытия орграфа С = (V, Е)

Определение 2.11. Граф (7 = {V, Е} называется взвешенным, если его ребрам (дугам) приписаны веса.

Часто взвешенный граф называют сетью. Рассмотрим сеть, изображенную на рис. 2.8. Вершина а этой сети не имеет заходящих дуг, а только дуги, которые исходят из нее в вершины подмножества Уа с Е.

Таким образом, полустепень захода вершины а равна нулю.

Полустепень исхода с!а = 3. Такая вершина называется истоком сети или начальной вершиной графа. Вершина у данного графа не имеет исходящих дуг, а только заходящие, которые выходят из некоторого подмножества с Е. Полустепень захода ее равна 3, полустепень исхода с!] = 0. Такая вершина называется стоком сети или конечной вершиной графа. Очевидно, что любая сеть задает отображение /: V —> /?, где Я — множество действительных чисел.

Рассмотрим граф (7 = {V, Е}, изображенный на рис. 2.9.

Как по ребрам этого графа перейти из вершины а в вершину сП Вот четыре возможных последовательности ребер перехода:

  • 1) (о, с) (с, (Г)
  • 2) (о, Ь) (Ь, с) (с, ф
  • 3) (а, е) (е, с) (с, 0)
  • 4) (а, с) (с, Ь) (Ь, а) (а, с) (с, ф.

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

Ь

Граф С = (V, Е)

Рис. 2.9. Граф С = (V, Е)

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

Определение 2.12. Маршрутом в неориентированном графе (7 = {V, Е) называется такая последовательность ребер ... е{, е2, ..., еп, что каждые два соседних ребра е,_,, е1 имеют общую инцидентную им вершину.

Таким образом, все приведенные последовательности ребер графа (7 = {V, Е}, изображенного на рис. 2.9, — это маршруты. В связи с тем, что в маршруте каждые два соседние ребра имеют инцидентную вершину, которая записана дважды, название одной из этих вершин в записи маршрута можно опустить и представить его не последовательностью ребер, а последовательностью вершин V,, у2, уп. Тогда маршруты 1)—4) будут записаны так: 1) а, с, (1 2) а, Ь, с, с1 3) а, е, с, с! 4) а, с, Ь, а, с, <3. В любой последовательности вершин, описывающей маршрут, есть первая вершина, с которой начинается маршрут, и последняя вершина, которой заканчивается маршрут. Первая вершина называется началом маршрута, последняя — его концом. Если первая и последняя вершины маршрута совпадают, т.е. у, = у„, маршрут называют циклическим. Говорят, маршрут содержит цикл. Начало цикла обычно не фиксируется.

Определение 2.13. Маршрут называется цепью, если каждое ребро графа С или, что то же, каждая его вершина встречается в маршруте не более одного раза.

Маршрут а, с, Ь, а, с, с! графа С = {V, Е}, изображенного на рис. 2.9, не является цепью. Кроме того, он содержит цикл а, с, Ь, а. Остальные маршруты 1)—3) — это цепи.

Определение 2.14. Граф С = {V, Е}, не содержащий циклов, называется ациклическим.

с1 (1

Орграф С = (V, Е)

Рис. 2. 10. Орграф С = (V, Е)

Для орграфов аналогом маршрута является путь. Путь может записываться в виде последовательности дуг, соединяющих вершины, или последовательности вершин. Для пути всегда имеется начальная вершина, которая называется его началом, и конечная вершина, заканчивающая путь. Он называется простым, если каждая его вершина встречается в нем не более одного раза. Если начальная и конечная вершины пути совпадают, т.е. у, = V", путь содержит цикл. Орграф, не содержащий циклов, также называется ациклическим.

На рис. 2.10 изображен орграф (7 = {V, Е}, в котором из вершины а в вершину к имеются такие пути:

  • 1) а, Ь, с, с1, е, к
  • 2) а, Ь, / е, к
  • 3) а, Ь, g, е, /г;
  • 4) а, Ь, с, <3, е, Ь, / е, к;
  • 5) а, Ь, / е, Ь, g, е, к.

Простые пути графа — это пути 1)—3). Путь 4) содержит циклы к, с, с1, е, Ь и е, Ь,/, е. Путь 5) содержит циклы Ь,/, е, Ь и е, Ь, g, е. Иногда цикл в орграфе называют контуром. Длиной цикла называется число дуг в этом цикле. Длина пути из вершины vi в вершину у] число ребер этого пути. Во взвешенном орграфе длина пути — это сумма весов дуг.

Определение 2.15. Гамильтоновым циклом в графе С - {V, Е}

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

Определение 2.16. Граф С = {V, Е), содержащий гамильтоно-

вый цикл, называется гамильтоновым графом.

На рис. 2.11 изображен граф С = {V, Е} и жирной линией показан один из его гамильтоновых циклов 1, 2, 3, 4.

Определение 2.17. Вершины у,., у.

2 3

Гамильтонов цикл графа Є = (Г, Е)

Рис. 2.11. Гамильтонов цикл графа Є = (Г, Е)

графа (7 = {V, Е) называются связанными, если существует маршрут или цепь с началом и концом у,. Для орграфов вершины у,., у. орграфа (7 = {V, Е} называются связанными, если существует путь или простой путь ИЗ У,- В У .. В этом случае говорят, что вершина у. достижима из вершины у, . Определение 2.18. Граф или орграф (7 = {V, Е} называется

связным (сильно связным, сильным), если все его вершины связаны между собой, т.е. взаимно достижимы. Граф или орграф (7 = {V, Е} называется несвязным, если хотя бы две его вершины несвязные (рис. 2.12).

Связный (а) и несвязные (б, в) графы С = (V, Е)

Рис. 2.12. Связный (а) и несвязные (б, в) графы С = (V, Е)

На рис. 2.12, б представлены два подграфа графа (7, каждый из которых является связным. Такие подграфы называются компонентами связности графа (7 = {V, Е}. Компоненты получены удалением в графе (7 ребра (с, сі).

Определение 2.19. Ребро в графе (7 = {V, Е} называется мостом,

если после его удаления начальная и конечная вершины ребра оказываются несвязными. В данном случае мост — это ребро (с, сі).

Определение 2.20. Связный ациклический граф С = {V, Е} называется деревом. Объединение деревьев образует лес.

На рис. 2.13 показаны все различные деревья с шестью вершинами. Весь рисунок можно считать лесом, состоящим из 36 вершин и 6 компонент.

Все различные деревья с шестью вершинами

Рис. 2.13. Все различные деревья с шестью вершинами

Для каждой пары вершин дерева существует единственный соединяющий их путь. Вершина дерева, степень которой равна единице, называется висячей вершиной.

Всякое ребро в дереве является мостом. Дерево с и вершинами имеет п - 1 ребро. Удобно считать, что граф, состоящий из одной изолированной вершины, тоже является деревом. Каждое дерево сп >2 вершинами имеет по крайней мере две висячие вершины.

Дерево, у которого одна вершина выделяется среди всех других, называется корневым деревом. Выделенная вершина называется корнем дерева, висячие вершины — его листьями. Таким образом, имеем следующее

Определение 2.21. Ацикличный граф, в котором только одна вершина имеет нулевую степень захода, а все остальные вершины имеют степень захода 1, называется корневым деревом.

Определение 2.22. Ацикличный граф, в котором только одна вершина имеет нулевую полустепень захода, а все остальные вершины имеют полустепень захода 1, называется ориентированным корневым деревом.

Обычно корневые деревья изображаются так, что корень оказывается наверху, а все остальные вершины — ниже его, на уровнях (ярусах), соответствующих расстоянию от корня. Количество уровней дерева называется его высотой.

На рис. 2.14 представлены трехуровневые неориентированное (а) и ориентированное (б) деревья.

Широко используемым среди корневых деревьев, является специальный их вид, называемый двоичным бинарным корневым деревом. Ориентированное двоичное корневое дерево изображено на рис. 2.15.

Корень Уровень Корень

  • 0
  • 2 3
  • а) 6)

Рис. 2.14. Неориентированное (а) и ориентированное (б) корневые деревья

Корень Уровень

Изоморфные графы

Рис. 2.16. Изоморфные графы

Если (7 = (V, Е) — двоичное корневое дерево высотой / с т вершинами, то т — нечетно, а количество висячих вершин п < 2‘.

Один и тот же граф можно изобразить на рисунках по-разному. Например, на рис. 2.16 а, б, в, г, мало похожих друг на друга, изображен один и тот же граф.

Чтобы убедиться, что два рисунка изображают один и тот же граф, необходимо показать, что: 1) две вершины графа на первом рисунке соединены ребром, если соединена ребром соответствующая пара вершин графа на втором рисунке; 2) две вершины графа на втором рисунке соединены ребром, если соединена ребром соответствующая пара вершин на первом рисунке. Если эти условия выполняются, два графа (7, (?' называются изоморфными, т.е. одинаковыми.

Пусть на чертеже изображен связный граф.

Определение 2.23. Граф (7 = (V, Е) называется плоским (планарным), если его можно нарисовать на плоскости так, что ребра графа пересекаются только в его вершинах.

Плоский (а) и неплоский (б) графы

Рис. 2.17. Плоский (а) и неплоский (б) графы

Определение 2.24. Граф Є - (V, Е), на котором та или иная числовая характеристика принимает минимальное или максимальное значение, называется экстремальным.

 
< Пред   СОДЕРЖАНИЕ     След >