Файл: Учебника по курсу Основы дискретной математики и логики.pdf

соединяющей точки u[у] и v[вэ]. Если (u, v)[у вэ] – дуга, то на этой линии будем указывать стрелку от u[у] к v[вэ].
На рис. 3.1 представлены различные типы графов: а), б) – ориентированный и неориентированный псевдографы; в), г) – ориентированный и неориентированный мультиграфы; д), е) – ориентированный и неориентированный графы в узком смысле.
Cлайд 62
Графы можно задавать аналитически, указывая множества их вершин и ребер. Для того чтобы различать при таком задании ориентированные и неориентированные графы, договоримся для обозначения дуг использовать круглые скобки, а для обозначения неориентированных ребер – квадратные скобки.
Формулы (3.1) и (3.2) задают неориентированный и ориентированный графы. Их геометрические изображения представлены на рис. 3.2 и 3.3 соответственно.
Граф называется взвешенным, если каждому его ребру приписан некоторый вес, выражаемый числом. Пример взвешенного графа приведен на рис. 3.4.
Взвешенные графы часто используются в прикладных задачах.
Весовые числа могут обозначать, например, стоимость перевозок или расстояния между пунктами.
Слайд 63
Две вершины в графе G[жэ] называются смежными, если существует ребро, которое их соединяет. Пусть u[у], v[вэ] – вершины, e[е] – ребро, их соединяющее. Тогда вершина u[у] и ребро e[е] называются инцидентными, вершина v[вэ] и ребро e[е] также называются инцидентными. Два ребра, инцидентные одной и той же вершине, называются смежными.
В качестве примера рассмотрим граф G[жэ], изображенный на рис. 3.5.
В нем смежными являются вершины 1 и 2, 1 и 3, 1 и 1, а также ребра (1,

2)[один два] и (1, 1)[один один], (1, 3)[один три] и (1, 1)[один один], (1,
2)[один два] и (1, 3)[один три]. Ребро (1, 2)[один два] инцидентно вершинам
1 и 2, ребро (1, 3)[один три] – вершинам 1 и 3, ребро (1, 1)[один один] – вершине 1.
Степенью вершины v[вэ] неориентированного графа G[жэ] называется число ребер, инцидентных вершине v. Полустепенью исхода вершины v[вэ] орграфа G[жэ] называется число дуг, выходящих из вершины v[вэ].
Полустепенью захода вершины v[вэ] орграфа G[жэ] называется число дуг, входящих в вершину v[вэ]. Обозначения для введенных выше понятий приведены в формулах (3.3) и (3.4).
В случае неориентированного псевдографа вклад каждой петли при расчете степени инцидентной вершины равен 2. В случае ориентированного псевдографа каждая петля дает вклад 1 при расчете полустепени исхода и вклад 1 при расчете полустепени захода. В формуле (3.5) указаны степени вершин графа G[жэ], изображенного на рис. 3.5, а в формуле (3.6) – полустепени вершин графа D[дэ], изображенного на рис. 3.6.
Вершина графа, не инцидентная ни одному ребру, называется изолированной. Вершина, инцидентная только одному ребру, причем не петле, называется висячей.
Неориентированный граф называется регулярным, или однородным, если степени всех его вершин одинаковы. Пример регулярного графа F приведен на рис. 3.7.
Слайд 64
Пусть G[жэ] –
ориентированный или неориентированный граф, заданный формулой (3.7).
Матрицей смежности неориентированного графа G[жэ] называется квадратная матрица A[а] порядка p[пэ], каждый элемент a
ij
[а итое житое] которой равен количеству ребер, соединяющих вершину v
i
[вэ итое] c вершиной v
j
[вэ житое].

Матрицей смежности ориентированного графа G[жэ] называется квадратная матрица A[а] порядка p[пэ], каждый элемент a
ij
[а итое житое] которой равен количеству дуг, выходящих из вершины v
i
[вэ итое] и входящих в вершину v
j
[вэ житое].
Рассмотрим неориентированный граф G[жэ] и орграф D[дэ], изображенные на рис. 3.8 и 3.9 соответственно. Матрицы смежности данных графов представлены формулой (3.8).
Заметим, что матрица смежности неориентированного графа является симметричной.
Слайд 65
Построим матрицы смежности для графов, содержащих петли и кратные ребра. Рассмотрим неориентированный граф G[жэ] и орграф D[дэ], изображенные на рис. 3.10 и 3.11 соответственно.
Наличие петли в вершине 2 графа G[жэ] говорит о том, что элемент, стоящий во второй строке и во втором столбце матрицы смежности, равен 1.
Два ребра, соединяющие вершины 2 и 4 графа G[жэ], показывают, что элемент матрицы смежности, расположенный во второй строке и в четвертом столбце, равен 2. Таким же будет элемент, стоящий в четвертой строке и во втором столбце.
В вершине 3 графа D[дэ] имеется петля, а значит, элемент, расположенный в третьем столбце и в третьей строке матрицы смежности, равен 1. Из вершины 1 в вершину 2 идут две дуги. Это говорит о том, что элемент, стоящий в первой строке и во втором столбце, равен 2.
Матрицы смежности графов G[жэ] и D[дэ] представлены формулой
(3.9).
По заданному геометрическому изображению графа всегда можно составить его матрицу смежности. И наоборот, если задана матрица смежности, то определяемый ею граф можно изобразить геометрически.

Слайд 66
Рассмотрим примеры построения геометрических изображений графов по заданным матрицам смежности.
Сначала рассмотрим матрицу смежности неориентированного графа
G[жэ], заданную формулой (3.10). Проанализируем данную матрицу.
Вершины графа будем обозначать цифрами 1, 2, 3, 4.
Две двойки в матрице смежности графа G[жэ] говорят о том, что вершины 2 и 3 соединяются двумя ребрами. Имеющиеся в матрице нули показывают, что в графе нет ребер, соединяющих вершины 1 и 2, и нет петель в вершинах 2 и 4. Единицы, присутствующие в матрице смежности, свидетельствуют о том, что в вершинах 1 и 3 имеются петли и каждая из пар вершин (1, 4), (1, 3), (3, 4), (2, 4) [один четыре, один три, три четыре, два четыре] соединяется одним ребром.
Изображение графа G[жэ] представлено на рис. 3.12.
Теперь обратимся к матрице смежности графа ориентированного графа
D[дэ], заданной формулой (3.11). Имеющаяся в матрице двойка говорит о том, что из вершины 2 в вершину 3 идут две дуги. Единицы на главной диагонали матрицы показывают, что в каждой вершине есть петля.
Остальные единицы свидетельствуют о том, что по одной дуге идет из вершины 1 в вершины 2 и 4, из вершины 2 в вершину 4, из вершины 3 в вершину 1, из вершины 4 в вершину 1 и из вершины 4 в вершину 2.
Изображение графа D[дэ] представлено на рис. 3.13.
Слайд 67
Пусть G[жэ] – ориентированный или неориентированный граф, заданный формулой (3.12).
Матрицей инцидентности орграфа G[жэ] без петель называется матрица B[бэ] размера p x q[пэ на кю], элементы которой определяются формулой (3.13).

Матрицей инцидентности неориентированного графа G[жэ] без петель называется матрица B[бэ] размера p x q[пэ на кю], элементы которой определяются формулой (3.14).
Если G[жэ] псевдограф и e
j
[е житое] – петля в вершине v
i
[вэ итое], то элемент b
ij
[бэ итое житое] матрицы B[бэ] равен 1, а остальные элементы j- го[житого] столбца равны нулю.
Таким образом, каждый столбец матрицы инцидентности содержит либо только два ненулевых элемента, либо только один ненулевой элемент.
По заданному геометрическому изображению графа всегда можно составить его матрицу инцидентности. И наоборот, если задана матрица инцидентности, то определяемый ею граф можно изобразить геометрически.
Слайд 68
Рассмотрим неориентированный граф G[жэ] и орграф D[дэ], изображенные на рис. 3.14 и 3.15 соответственно. Матрицы инцидентности данных графов представлены формулой (3.15).
Наряду с матрицами смежности и инцидентности для задания графов используются списки смежности.
Для построения списка смежности в случае неориентированного графа рядом с каждой его вершиной приводится перечень смежных с ней вершин.
В случае орграфа рядом с каждой вершиной перечисляют концы всех дуг, выходящих из данной вершины. При этом при наличии кратных ребер рядом с соответствующими смежными вершинами в скобках указывают кратности.
Так, для графа G[жэ] на рис. 3.14 рядом с вершиной v
1
[вэ один] мы должны указать вершины v
2
[вэ два] и v
4
[вэ четыре], рядом с вершиной v
2
[вэ два] вершины v
1,
v
3,
v
4
[вэ один вэ три вэ четыре], рядом с v
3
– вершины v
2
и v
4
, рядом с v
4
– вершины v
1,
v
2,
v
3
[вэ один вэ два вэ три].
Для графа D[дэ] на рис. 3.15 рядом с вершиной v
1
[вэ один] мы должны записать вершину v
2
[вэ два], рядом с вершиной v
2
[вэ два] – вершины v
3
[вэ

три] и v
4
[вэ четыре], для вершины v
3
[вэ три] перечень будет пустым, рядом с вершиной v
4
[вэ четыре] следует записать вершины v
1
[вэ один] и v
3
[вэ три].
Слайд 69
Построим матрицы инцидентности и списки смежности для графов
G[жэ] и D[дэ], изображенных на рис. 3.16 и 3.17 соответственно.
Каждый из рассматриваемых графов имеет 7 ребер и 4 вершины, а значит, их матрицы инцидентности содержат 7 столбцов и 4 строки. Пятое ребро графа G[жэ] является петлей в вершине 2. Поэтому в пятом столбце матрицы инцидентности этого графа во второй строке стоит единица, а в остальных строках – нули. Аналогично седьмое ребро графа D[дэ] является петлей в вершине 3. Соответственно, седьмой столбец матрицы инцидентности данного графа имеет единицу в третьей строке и нули в остальных строках.
Матрицы инцидентности графов G[жэ] и D[дэ] представлены формулой
(3.16).
Табл. 3.17 задает списки смежности рассматриваемых графов. Каждый из графов G[жэ] и D[дэ] имеет по одному ребру кратности 2. Эта кратность указана в скобках при перечислении смежных вершин. В графе G[жэ] кратным является ребро, соединяющее вершины 2 и 4, а в графе D[дэ] – ориентированное ребро, идущее из вершины 1 в вершину 2.
Слайд 70
Маршрутом, соединяющим вершины u[у] и v[вэ] в графе G[жэ], называется чередующаяся последовательность вершин и ребер, определяемая формулой (3.18) с условиями (3.19). Вершины u[у] и v[вэ] называются начальной и конечной вершинами маршрута, остальные вершины называются внутренними. Число ребер в маршруте называется длиной маршрута. Заметим, что для задания маршрута достаточно указать начальную вершину и последовательность ребер. В случае графа без кратных ребер для задания маршрута достаточно указать последовательность вершин.

Если начальная и конечная вершины маршрута совпадают, то маршрут называется замкнутым, или циклическим, в противном случае – открытым.
Если все ребра в маршруте различны, то маршрут называется цепью.
Если все вершины, кроме, быть может, начальной и конечной, в маршруте различны, то маршрут называется простой цепью. В цепи начальная и конечная вершины называются концами цепи. Говорят, что цепь с концами
u[у] и v[вэ] соединяет вершины u[у] и v[вэ]. Обозначение цепи, соединяющей вершины u[у] и v[вэ], приведено в формуле (3.20).
Если существует цепь, соединяющая вершины u[у] и v[вэ], то существует и простая цепь, соединяющая эти вершины. Замкнутая цепь называется циклом; замкнутая простая цепь – простым циклом. Граф без циклов называется ациклическим. Для орграфов цепь называют также путем, а цикл – контуром.
Слайд 71
Рассмотрим примеры различных маршрутов на графе.
Обратимся к графу G[жэ], изображенному на рис. 3.18. В формуле
(3.21) представлен маршрут длины три, который не является цепью, так как в этой последовательности ребро (v
1
,
v
3
)[вэ один вэ три] повторяется.
В формуле (3.22) представлена цепь длины 5, которая не является простой цепью, так как в этой последовательности повторяется вершина v
3
[вэ три].
В формуле (3.23) представлена простая цепь длины четыре, так как в этой последовательности все ребра и вершины различны.
В формуле (3.24) представлен цикл длины шесть, который не является простым, так как в этой последовательности повторяется вершина v
3
[вэ три].
В формуле (3.25) представлен простой цикл длины три.

Слайд 72
Тема 3.2. Изоморфизм графов. Понятия полного и двудольного графов. Операции над графами. Измерение расстояний на графе. Связность
Важным понятием в теории графов является понятие изоморфизма.
Пусть граф G
1
[жэ один] имеет множество вершин V
1
[вэ один] и множество ребер E
1
[е один], а граф G
2
[жэ два] – множество вершин V
2
[вэ два] и множество ребер E
2
[е два].
Говорят, что граф G
1
[жэ один] изоморфен графу G
2
[жэ два], если существует биективное отображение V
1
[вэ один] на V
2
[вэ два], сохраняющее смежность вершин. Определение изоморфных графов с помощью математических символов представляет формула (3.26).
Изоморфизм графов является отношением эквивалентности.
Действительно, каждый граф изоморфен сам себе; если первый граф изоморфен второму, то и второй изоморфен первому; если первый граф изоморфен второму, а второй – третьему, то и первый граф изоморфен третьему.
Графы, не являющиеся изоморфными, называются неизоморфными.
Слайд 73
Из определения изоморфизма графов следует, что изоморфные графы отличаются лишь обозначением вершин и их расположением на плоскости.
Графы изучаются с точностью до изоморфизма, то есть рассматриваются не отдельно взятые графы, а классы эквивалентности относительно изоморфизма.
У изоморфных графов одинаково число вершин, число ребер, число вершин одинаковой степени или полустепени.
На рис. 3.19 приведены три внешне различные диаграммы, являющиеся диаграммами одного и того же графа. Требуемые соответствия между множествами вершин задаются формулой (3.27).

Количество вершин, ребер и количество смежных вершин для каждой вершины не определяют граф. У графов, изображенных на рис. 3.20, указанные характеристики совпадают, но при этом графы не являются изоморфными.
Слайд 74
Граф, состоящий из одной вершины, называется тривиальным.
Неориентированный граф без петель и кратных ребер, в котором любые две вершины смежны, называется полным