ЛЕКЦИЯ 5.1. Основные определения

ЛЕКЦИЯ 5.1.

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

 

 

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

Неформально граф – это диаграмма, состоящая из кружков и линий, соединяющих кружки (рис.1). Кружки называются вершинами графа, а линии – ребрами.… Говорят, что задан неориентированный граф, Если заданы

Определение. Степеньювыхода вершины v ориентированного графа называют число дуг, выходящих из этой вершины. Если = 0, то вершина v называется стоком.

Определение. Степеньювхода вершины v ориентированного графа называют число дуг, входящих в эту вершину. Если = 0, то вершина v называется источником.

Некоторые виды графов

Рис. 6 Степень каждой вершины графа Кр равна . Следовательно, число ребер графа Кр равно.

Маршруты, цепи, циклы

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

В случае простого графа маршрут однозначно определяется последовательностью вершин или последовательностью ребер. Если маршрут в простом графе задан последовательностью вершин v₀, v₁,, … , v_k, то вершины v₀, v_k называют концами маршрута. Если v₀ = v_k, то маршрут называют замкнутым, в противном случае – незамкнутым.

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

Определение. Простой цикл с р вершинами обозначается Ср . Например, граф – это одновременно граф С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.

Матрица смежности графа

Матрица смежности неориентированного графа.

Определение. Матрицей смежности неориентированного графа называется квадратная матрица с р строками и с р столбцами. Элементы матрицы определяются… Матрицу смежности обозначим буквой А.

Свойства матрицы смежности неориентированного графа.

· Число единиц в i-й строке равно степени i-ой вершины, i = 1, 2, …, р.

· Число единиц в -м столбце равно степени -ой вершины, = 1, 2, …, р.

· Число единиц в матрице равно удвоенному числу ребер.

· <=> , матрица смежности симметрична относительно главной диагонали, она совпадает со своей транспонированной.

Матрица смежности ориентированного графа.

Пример орграфа и его матрицы смежности показан на рис. 10.     …

Свойства матрицы смежности ориентированного графа.

· Число единиц в i-ой строке равно степени выхода i-ой вершины, i = = 1, 2, … , р.

· Число единиц в -м столбце равно степени входа -ой вершины, = 1, 2, …, р.

· Число единиц в матрице равно числу дуг в графе.

· Матрица смежности не симметрична относительно главной диагонали.

Матрица инцидентности графа

Матрица инцидентности неориентированного графа.

Определение. Матрицей инцидентности графа называется матрица с р строками (каждая строка соответствует одной из вершин графа) и q столбцами (каждый… Пример графа и его матрицы инцидентности приведен на рис. 11

Свойства матрицы инцидентности неориентированного графа.

· Число единиц в i-й строке равно степени i-ой вершины, i = 1, 2, … , р.

· Число единиц в -м столбце равно двум, так как любое ребро инцидентно двум вершинам, = 1, 2, …, р.

· Число единиц в матрице равно удвоенному числу ребер графа.

Матрица инцидентности ориентированного графа.

i = 1, …, p; j = 1, … , q. Пример орграфа и его матрицы инцидентности показан на рис. 12.   …

Свойства матрицы инцидентности орграфа.

· Число единиц в i-й строке равно степени входа i-ой вершины, i = 1, 2, … , р.

· Число единиц с минусом в i-ой строке равно степени выхода i-ой вершины, i = 1, 2, … , р.

· Число единиц в матрице равно числу единиц с минусом и равно числу дуг в графе.

· В каждом столбце матрицы есть ровно одна единица и ровно одна единица с минусом, так как всякая дуга из одной вершины выходит и в одну вершину входит.