Файл: Введение в теорию графов.docx

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 23.11.2023

Просмотров: 166

Скачиваний: 3

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Введение в теорию графов

Графом называется множество узлов и связей между ними. Каждый узел называется вершиной, а каждая связь – ребром. Каждое ребро соединяет две вершины.

Виды графов

Графы делятся на ориентированные и неориентированные. Ориентированный граф – такой граф, в котором можно двигаться от вершины к вершине только в одном направлении. Например, на рисунке 1 можно двигаться из вершины v0 в v1, а из v1 в v0 нельзя. В неориентированных графах можно двигаться в обе стороны. Например, на рисунке 2 из вершины 1 можно двигаться в вершину 2, и наоборот.Рисунок 1 – Ориентированный графРисунок 2 – Неориентированный граф Граф, в котором присутствуют как ориентированные ребра, так и неориентированные, называется смешанным.Рисунок 3 – Смешанный графКроме того, графы делятся на взвешенныеи невзвешенные. Граф, в котором каждому ребру в соответствие поставлено некоторое числовое значение – вес, называется взвешенным графом (например, длина дороги). Если никакого числового значения рёбрам не поставлено, то граф называется невзвешенным. Чаще всего, в названии графа указывают как его ориентированность или неориентированность, так и его взвешенность или невзвешенность.Граф, в котором между любой парой вершин существует, как минимум, один путь, называется связным. Если в графе существует хотя бы одна вершина, не связанная с другими, он называется несвязным.Рисунок 4 – Взвешенный связанный ориентированный графГраф, в котором число рёбер близко к максимальному (когда каждая вершина графа связана с любой другой вершиной графа рёбрами), называется
плотным графом.Граф с противоположным свойством, имеющий малое число рёбер, называется разреженнымграфом. Петлёйназывается ребро, которое соединяет вершины v1 и v2, причём v1 и v2 совпадают. Иными словами, петля – это ребро, которое начинается и заканчивается в одной вершине.Рисунок 5 – Несвязный графРисунок 6 – Плотный графРисунок 7 – Граф с петлёйИнцидентность – понятие, используемое только в отношении ребра и вершины. Если v1, v2 - вершины, а e = (v1, v2) - соединяющее их ребро, тогда вершина v1 и ребро e инцидентны, вершина v2 и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Например, на рисунке 7 вершина 1 инцидентна ребру 1-2.Смежность – понятие, используемое в отношении только двух рёбер, либо только двух вершин: два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными. Например, на рисунке 7 вершины 1 и 2 смежные, поскольку инциденты одному ребру.Маршрутомназывается такая чередующаяся последовательность вершин и рёбер vertex0, edge1, vertex1, edge2, vertex2,….edgek, vertexk, v 0 , e 1 , v 1 , e 2 , v 2 , . . . , e k , v k {\displaystyle v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}} …..//в которой любые два соседних элемента инцидентны. Если v 0 = v k {\displaystyle v_{0}=v_{k}} vertex0 = vertexk, то маршрут замкнут, иначе маршрут открыт.Рисунок 8 – Открытый маршрут (вершины 2-4-1-2-3-4-1).Рисунок 9 – Замкнутый маршрут (вершины 2-3-5-4-3-2)Цепь – маршрут, все ребра которого различны. Если все вершины такого маршрута различны, то цепь называется
простой. В цепи vertex0, edge1, ….., edgek, vertexk вершины vertex0 и vertexk называются концами цепи.Рисунок 10 – Открытая цепь (вершины 2-5-1-2-4)Рисунок 11 – Замкнутая цепь (вершины 2-4-1-2-3-5-2)Циклом называется замкнутая цепь (см. рисунок 11).

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

Матрица смежности графа – это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1 для невзвешенного графа. Значения 1 и 0 отображают существование ребра между вершинами: если между вершинами 1 и 2 есть ребро, то в матрице на пересечении первой строки и второго столбца и второй строки и первого столбца будут стоять единицы. Если граф взвешенный, то элементами матрицы смежности будут числа, соответствующие весам ребер, соединяющих вершины, на пересечении которых в таблице стоит элемент.Рисунок 12 – Невзвешенный неориентированный графМатрица смежности для графа, изображенного на рисунке 7, представлена следующим образом:

№ вершины
1
2
3
4
5

1
0
1
0
0
1

2
1
0
1
1
1

3
0
1
0
1
0

4
0
1
1
0
1

5
1
1
0
1
0
Рисунок 13 – Невзвешенный ориентированный графМатрица смежности для графа, изображенного на рисунке 8, представлена следующим образом:

№ вершины
1
2
3
4

1
0
1
0
1

2
0
0
1
1

3
0
1
0
0

4
1
0
1
0
Рисунок 14 – Взвешенный неориентированный графМатрица смежности для графа, изображенного на рисунке 9, представлена следующим образом:

№ вершины
1
2
3
4
5

1
0
40
0
0
18

2
40
0
22
6
15

3
0
22
0
14
0

4
0
6
14
0
22

5
18
15
0
20
0
Граф может быть представлен с помощью вектора смежности. В векторе смежности для каждой вершины хранятся номера смежных с ней вершин. Рисунок 15 – Представление графа с помощью вектора смежностиЕще одной формой представления графа является матрица инцидентности, в которой указываются связи между инцидентными элементами графа (ребра и вершины). Столбцы матрицы соответствуют ребрам, строки – вершинам. Ненулевое значение в ячейке матрицы указывает на связь между вершиной и ребром (их инцидентность).Рисунок 16 – Взвешенный неориентированный графМатрица инцидентности, соответствующая графу, выглядит следующим образом:

№ вершины
a
b
c
d
e

1
1
1
0
0
0

2
1
0
1
1
0

3
0
0
0
1
1

4
0
1
1
0
1

Смотрите также файлы