5.1.2. Некоторые виды графов
Определение. Граф
такой,
что любые две его вершины смежны,
называется полным графом. Полный
граф с р вершинами обозначается
.
На рис. 6 показаны графы
.
Рис. 6
Степень каждой вершины графа Кр
равна
.
Следовательно, число ребер графа Кр
равно
.
Определение. Граф называется регулярным степени k, если все его вершины имеют одну и туже степень k. На рис. 7 приведены примеры регулярных графов степени 3. Всякий полный граф Кр – это регулярный граф степени .
Рис.7
Определение. Граф с пустым множеством ребер называется вполне несвязным графом. Вполне несвязный граф с р вершинами будем обозначать через Np. Граф N1, состоящий из единственной вершины, называется тривиальным графом.
5.1.4. Маршруты, цепи, циклы
Определение. Маршрутом называют последовательность вершин и ребер, в которой любые два соседних элемента инцидентны.
В случае простого графа маршрут однозначно определяется последовательностью вершин или последовательностью ребер. Если маршрут в простом графе задан последовательностью вершин v0, v1,, … , vk, то вершины v0, vk называют концами маршрута. Если v0 = vk, то маршрут называют замкнутым, в противном случае – незамкнутым.
Определение. Маршрут, в котором нет повторений ребер, называется цепью. Цепь, в которой все вершины различны, кроме, может быть, ее концов называется простой. Замкнутая простая цепь называется простым циклом. Про цепь говорят, что она соединяет свои концы.
Определение. Простой цикл с р вершинами обозначается Ср . Например, граф – это одновременно граф с3.
Определение. Ориентированная простая цепь называется путем, ориентированный простой цикл называют контуром.
Рассмотрим граф на рис. 11. Маршруты в этом графе будем задавать последовательностью вершин.
Пример маршрута: 1 – 2 – 3 – 5 – 7 – 4 – 3 – 5 – 6 – 2 – 3 – 4.
Пример замкнутого маршрута: 3 – 4 – 5 – 7 – 3 – 4 – 1 – 3.
Пример цепи, соединяющий вершины 6 и 8: 6 – 5 – 3 – 4 – 5 – 7 – 3 – 2 – 6 – 8.
Пример цикла: 5 – 3 – 2 – 6 – 5 – 7 – 4 – 5.
Примеры простых цепей, соединяющих вершины 1 и 6: 1 – 3 – 4 – 5 – 6; 1 – 2 – 6; 1 – 4 – 7 – 8 – 6.
Примеры простых циклов: 3 – 5 – 7 – 4 – 3; 1 – 2 – 6 – 8 – 7 – 4 – 1;
1 – 2 – 6 – 5 – 7 – 3 – 1.
Рис. 11
Рассмотрим ориентированный граф на рис. 12. Ориентированные маршруты в этом графе будем задавать последовательностью вершин, проходимых в направлении ориентации дуг.
Рис. 12
Пример ориентированного маршрута: 1 2 3 5 2 6 8 5.
Пример замкнутого ориентированного маршрута: 1 4 5 2 6 8 5 2 3 1.
Пример ориентированной цепи: 4 5 7 8 5 2.
Пример замкнутой ориентированной цепи: 6 8 5 2 3 1 5 6.
Пример пути, соединяющего вершины 3 и 9: 3 1 4 5 6 9.
Пример контура: 5 7 4 5.
5.2.2. Матрица смежности графа
Матрица смежности неориентированного графа.
Пусть – граф и |V| = p.
Определение. Матрицей смежности
неориентированного графа
называется квадратная матрица с р
строками и с р столбцами. Элементы
матрицы определяются правилом:
Матрицу смежности обозначим буквой А.
Пример графа и его матрицы смежности показан на рис. 9.
j i |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
2 |
1 |
0 |
1 |
0 |
1 |
0 |
3 |
0 |
1 |
0 |
1 |
1 |
1 |
4 |
0 |
0 |
1 |
0 |
1 |
1 |
5 |
0 |
1 |
1 |
1 |
0 |
1 |
6 |
0 |
0 |
1 |
1 |
1 |
0 |
Рис. 9
Свойства матрицы смежности неориентированного графа.
Число единиц в i-й строке равно степени i-ой вершины, i = 1, 2, …, р.
Число единиц в
-м
столбце равно степени
-ой
вершины,
= 1, 2, …, р.Число единиц в матрице равно удвоенному числу ребер.
<=>
,
матрица смежности симметрична
относительно главной диагонали, она
совпадает со своей транспонированной.
Матрица смежности ориентированного графа.
Это квадратная матрица, в которой р строк и р столбцов, элементы которой определяются правилом
Пример орграфа и его матрицы смежности показан на рис. 10.
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
2 |
0 |
0 |
1 |
0 |
1 |
0 |
3 |
0 |
1 |
0 |
1 |
0 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
1 |
5 |
0 |
0 |
1 |
0 |
0 |
1 |
6 |
0 |
0 |
0 |
1 |
1 |
0 |
Рис. 10
Свойства матрицы смежности ориентированного графа.
Число единиц в i-ой строке равно степени выхода i-ой вершины, i = = 1, 2, … , р.
Число единиц в -м столбце равно степени входа -ой вершины, = 1, 2, …, р.
Число единиц в матрице равно числу дуг в графе.
Матрица смежности не симметрична относительно главной диагонали.