Структуры данных. Граф

Это краткий дополненный конспект части о графах в книге Гид по Computer Science, Вильям Спрингер.

Задача о кенигсбергских мостах

Задача о кенигсбергских мостах - с нее началась теория графов.

Задача: В городе Кенигсберге (ныне Калининград) протекает река. Она делит город на четыре части, которые соединяются семью мостами. Вопрос: можно ли прогуляться по городу, проходя каждый мост ровно один раз?

Однажды этот вопрос задали математику Леонарду Эйлеру. Главное заключение - топологические деформации неважны для решения (изменение размера и формы различных деталей не меняет задачу при условии, что не меняются соединения). Эйлер назвал это геометрией положения.

Мы можем упростить карту - заменяем каждую часть города вершиной, а каждый мост — ребром, соединяющим две вершины. В результате получим граф.

Граф на основе задачи о кёнигсбергских мостах

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

Любой участок суши (не начальная и не конечная точка маршрута) - конечная точка для четного числа мостов.

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

Эйлеровый путь - путь через граф, который проходит через каждое ребро ровно один раз.

Некоторые задачи являются NP-сложными на произвольных графах, но имеют эффективные (часто O(n)) решения на графах, имеющих определенные свойства.

Основная информация

Граф — это способ представления взаимосвязей в множестве данных. Часто изображаются в виде кружков (вершин) и линий между ними (ребра).

Смежные вершины - между ними есть ребро, не смежные - нет ребра.

Вершину также называют узлом. Обычно термины взаимозаменяемы, но есть исключения. Точка многоугольника в котором встречаются два и более ребер - всегда вершина. Участок памяти с вершиной и ее набором ребер - всегда узел.

Подграф графа – любое количество вершин графа вместе с любым количеством ребер (которые также принадлежат исходному графу) между этими вершинами.

Порожденный подграф —любое подмножество вершин вместе со всеми ребрами графа, соединяющими эти вершины.

Строгое подмножество - содержит меньше вершин, чем исходном графе.

Регулярное подмножество - может содержат все множества вершин.

Класс графов — это (как правило, бесконечный) набор графов, который обладает определенным свойством; принадлежность данного графа к этому классу зависит от того, есть ли у этого графа это свойство.

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

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

Полный (под)граф (клика) - граф, который содержит все возможные ребра между его вершинами.

Пример: K₈ - полный граф из восьми вершин

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

Независимое (внутренне устойчивое) множество - множество вершин без ребер между ними.

Связный граф/подграф - в котором существует путь от любой вершины к любой другой вершине.

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

Пример: разъединённый граф с шестью компонентами связности размером 1.

Говоря «граф» и не указывая иное, мы всегда имеем в виду простой граф.

Непростой граф - граф с петлями (ребро, которое заканчивается в той же вершине, в которой началось)

Мультиграф - граф с кратными ребрами (несколько ребер, соединяющих одни и те же вершины).

Направленные и ненаправленные графы

Ненаправленный граф (Просто граф) - по которому можно проходить в обоих направлениях (A связана с B, то B связана с A).

Ориентированный граф (орграф) - каждое ребро имеет направление. Альберт пишет Виктору, но это не значит (Стрелочка от А к В), что Виктор всегда пишет в ответ Алберту. Если он все же пишет, то стрелка будет и в обратном направлении от В к А.

Симметричный орграф - для каждого ориентированного ребра в нем существует ребро соединяющее те же две вершины, но направленное в противоположную сторону. Эквивалентен ненаправленному графу с одним ребром, поэтому обычные графы можно рассматривать как частный случай орграфа.

Направленный (антисимметричный) граф - между любыми двумя вершинами может существовать только одно ориентированное ребро;

Циклические и ациклические графы

Циклический граф - имеет хотя бы один цикл:

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

Ациклический граф - не более одного пути между любыми двумя вершинами;

Взвешенные и невзвешенные графы

В действительности, не все ребра графа имеют одинаковую длину.

Невзвешенный граф - ребра просто показывают, между какими вершинами есть прямой путь.

Взвешенные графы - каждому ребру присвоен вес. Чаще это неотрицательные целые числа. Вес - стоимость использования ребра.

Что именно означает вес, зависит от того, что описывает граф.

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

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

Представление графов

Обозначения размеров графа:

n - число вершин,

m -число ребер.

Обычно множество вершин обозначают буквой V, а множество ребер — буквой E, поэтому |V| = n, а |E| = m; то есть n — размер множества V, а m — размер множества E.

Размер матрицы — это сумма количества вершин (n) и количества ребер (m)

Количество места в памяти для хранения графа зависит от того, как мы его храним.

Как правило в виде:

Представление графов в виде списков смежности

Каждая вершина графа сохраняется вместе со списком смежных с ней вершин.

Эффективен для:

Разреженный граф - список смежности эффективнее по объему памяти. Не нужно хранить O(n2) нулей и можно легко перебрать все существующие ребра.
Динамический граф (Изменяется со временем) - проще добавлять и удалять вершины.

JavaScript

1// Полный граф
2const fullGraph = {
3	1: [2, 3, 4, 5, 6, 7, 8],
4	2: [1, 3, 4, 5, 6, 7, 8],
5	3: [1, 2, 4, 5, 6, 7, 8],
6	4: [1, 2, 3, 5, 6, 7, 8],
7	5: [1, 2, 3, 4, 6, 7, 8],
8	6: [1, 2, 3, 4, 5, 7, 8],
9	7: [1, 2, 3, 4, 5, 6, 8],
10	8: [1, 2, 3, 4, 5, 6, 7],
11};
12
13// Разъедененный граф
14const disconnectedGraph = {
15  1: [],
16  2: [],
17  3: [],
18  4: [],
19  5: [],
20  6: [],
21}

Объем занимаемого пространства составит O(n + m).

У разреженного графа (с очень небольшим числом ребер) - O(n).

Для плотного графа (графа с большим количеством ребер, такого как полный или почти полный граф) O(n^2) ( m = O(n^2)).

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

Матрица смежности имеет следующие свойства:

Каждая ячейка матрицы либо 0 - нет смежных вершин, либо 1 - есть смежные вершины.
Число единиц в матрице равно удвоенному числу ребер в графе;
Ячейки по диагонали всегда равны нулю, так как ни у одной вершины нет ребра, которое и начинается, и заканчивается в ней;
Состоит из n строк и n столбцов и поэтому занимает n:^2 места. Для плотного графа линейная зависимость от размера матрицы сохраняется.

JavaScript

1// Полный граф
2const fullGraph = [
3  [0, 1, 1, 1, 1, 1, 1, 1],
4  [1, 0, 1, 1, 1, 1, 1, 1],
5  [1, 1, 0, 1, 1, 1, 1, 1],
6  [1, 1, 1, 0, 1, 1, 1, 1],
7  [1, 1, 1, 1, 0, 1, 1, 1],
8  [1, 1, 1, 1, 1, 0, 1, 1],
9  [1, 1, 1, 1, 1, 1, 0, 1],
10  [1, 1, 1, 1, 1, 1, 1, 0],
11]
12
13// Разъедененный граф
14const disconnectedGraph = [
15  [0, 0, 0, 0, 0, 0,],
16  [0, 0, 0, 0, 0, 0,],
17  [0, 0, 0, 0, 0, 0,],
18  [0, 0, 0, 0, 0, 0,],
19  [0, 0, 0, 0, 0, 0,],
20  [0, 0, 0, 0, 0, 0,],
21]

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

Эффективен для:

Приложения, где необходима предсказуемость - в матрице смежности эффективней организован доступ к ребрам(A[i] [j] = 1 значит вершины смежные). В ней поиск занимает постоянное количество времени.
В приложениях реального времени следует быть готовыми пожертвовать некоторой производительностью, чтобы получить более жесткие ограничения на максимальное время, которое может потребоваться для выполнения операции.

Примеры представлений для направленного и ненаправленного графа можно посмотреть здесь.

Представление взвешенного графа

Возьмем в качестве примера взвешенного графа карту метро, где вес ребра - время между станциями в минутах.

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

Значение веса указываем вместо обозначения наличия связи (1 и 0).

JavaScript

1const Graph = [
2  [0, 10, 8, 0, 0, 0,],
3  [0, 0, 0, 0, 0, 12,],
4  [0, 0, 0, 11, 5, 0,],
5  [0, 0, 0, 0, 0, 10,],
6  [0, 0, 0, 0, 0, 11,],
7]

Список смежности

У каждой вершины указываем вес ребра.

JavaScript

1// Пример взвешенного графа с вложенными массивами
2let weightedGraph1 = {
3	a: [
4		[b, 10],
5		[c, 8],
6	],
7	b: [[f, 12]],
8	c: [
9		[d, 11],
10		[e, 5],
11	],
12	d: [[f, 10]],
13	e: [[f, 11]],
14};
15
16//  с помощью объектов
17let weightedGraph2 = {
18	a: { b: 10, c: 8 },
19	b: { f: 12 },
20	c: { d: 11, e: 5 },
21	d: { f: 10 },
22	e: { f: 11 },
23};

Представление графов в памяти

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

Бесхордовые циклы

Хорда — это ребро между двумя вершинами цикла, которое само не является частью цикла.

Бесхордовый цикл — это цикл, который состоит хотя бы из четырех вершин и не содержит хорд.

Пример бесхордового цикла из шести вершин:

Хордальный граф - Граф без порожденных бесхордовых циклов.

Раскраска графа

Многие графовые задачи связаны с раскраской.

Раскраска графа - способ маркировки вершин (или ребер) графа. Разделение вершин на независимые множества.

Правильная раскраска вершин - смежные вершины (то есть вершины, между которыми есть ребро) раскрашены в разные цвета.

Правильная раскраска ребер - два ребра, инцидентные (имеют общую вершину) одной и той же вершине, раскрашены в разные цвета.

Раскраска графа необязательно должна происходить цветами. Судоку — это форма раскраски графа, числами от 1 до 9.

Хроматическое число графа

Хроматическое число графа — это количество цветов, необходимых для его правильной раскраски.

Хроматическое число графа;

плоского графа (можно нарисовать так, чтобы никакие два ребра не пересекались, кроме как в вершине;) — не больше 4.
не имеющего ребер - 1 (все вершины могут быть одного цвета).
полного графа из n вершин - n.

Время выполнения

Проверка, может ли произвольный граф быть двухцветным, занимает линейное время. Для раскраски используется два цвета - достаточно окрашивать в разные цвета соседние вершины. Работа завершиться когда все вершины окрашены/соседняя вершина имеет тот же цвет

А вот трехцветная раскраска является NP-полной задачей.

Алгоритмы, определяющие, является ли граф k-раскрашиваемым, занимают экспоненциальное время.

Если граф принадлежит конкретному классу(например, идеальный), найти раскраску можно за полиномиальное время.

Использование

Алгоритмы раскраски обычно используются в таких приложениях, как:

планирование,
анализ данных,
работа в сетях и т. п.

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

Структуры данных на основе графов

1) Деревья

2) Кучи

Реализация на JavaScript

Пример взят с этого сайта.

Основные методы:

addVertex – добавление новой вершины;
addEdge – добавление нового ребра.

JavaScript

1class Graph {
2	constructor() {
3		this.vertices = {}; // список смежности графа
4	}
5
6	addVertex(value) {
7		if (!this.vertices[value]) {
8			this.vertices[value] = [];
9		}
10	}
11
12	addEdge(vertex1, vertex2) {
13		if (!(vertex1 in this.vertices) || !(vertex2 in this.vertices)) {
14			throw new Error("В графе нет таких вершин");
15		}
16
17		if (!this.vertices[vertex1].includes(vertex2)) {
18			this.vertices[vertex1].push(vertex2);
19		}
20		if (!this.vertices[vertex2].includes(vertex1)) {
21			this.vertices[vertex2].push(vertex1);
22		}
23	}
24}
25
26const graph = new Graph();
27
28graph.addVertex("A");
29graph.addVertex("B");
30graph.addVertex("C");
31graph.addVertex("D");
32graph.addVertex("E");
33graph.addVertex("F");
34graph.addVertex("G");
35graph.addVertex("H");
36
37graph.addEdge("A", "B");
38graph.addEdge("A", "C");
39graph.addEdge("C", "D");
40graph.addEdge("C", "E");
41graph.addEdge("A", "F");
42graph.addEdge("F", "G");
43
44// Graph {
45//   vertices: {
46//     A: [ 'B', 'C', 'F' ],
47//     B: [ 'A' ],
48//     C: [ 'A', 'D', 'E' ],
49//     D: [ 'C' ],
50//     E: [ 'C' ],
51//     F: [ 'A', 'G' ],
52//     G: [ 'F' ],
53//     H: []
54//   }
55// }

Другие посты

Ничего не найдено