ТГиК-2019-Лекция-30.09.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Тема лекции - графы.

Понятие графа

Рис.1. Иллюстрация задачи о Кёнигсбергских мостах

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем городским мостам, не проходя ни по одному из них дважды.

Графически задача представляется так: имеются некоторые земли (коричневый цвет, рис.1), остров (зелёный цвет, рис.1) и несколько мостов (жёлтый цвет, рис.1), по которым и нужно пройти так, чтобы ни по одному из них не ходить дважды.

Схематично эту задачу можно представить в виде рис.2, где элементы - это земли и остров, а мосты - это некоторые связи.

Рис.2. Схематическое изображение задачи о Кёнигсбергских мостах

Граф - пара \(<V,E>\), где \(V\) - конечное множество вершин, \(Е\) - множество связей между вершинами.

Виды графов

Обыкновенный граф

\( E \subseteq \left \{ \left \{v,u \right \} \mid v \ne u; v,u \in V \right \}\)

Рёбра - связи между вершинами обыкновенного графа

Ориентированный граф (орграф)

\( E \subseteq \left \{ <v,u> \mid v \ne u; v,u \in V \right \}\)

Рис.3. Дуга и ребро

Напоминаем, что \(<v,u>\) - это упорядоченные пары

Почему мы не написали \(E \subseteq V^2\)? Эта запись означает все возможные пары \(<v,u>\), а запись выше исключает повторы.

Для орграфов существуют понятия дуга и ребро. Они изображены на рис.3. Связь дуги и ребра представлена на рис.4

Графы и орграфы с петлями

Рис.4. Эквивалентность изображения орграфа

\(E \subseteq V^2\) - для орграфов

Рис.5 Гиперграф

Мультиграфы

Е - мультимножество; \(\eta : E \longrightarrow N_0 \), где \(N_0 = N \bigcup \left \{0 \right \}\)

Гиперграфы

\(E \subseteq 2^V\)

Маршрут

Рис. 6

Маршрут - это \(<v_0, v_1 e_2, ..., v_{n-1} e_{n}, v_{n}>, \) где \(v_{i} \in V, e_{i} \in E, e_{i}=\left \{ v_{i-1}, v \right \}\), а для орграфа \(e_{i}=\left \{ v_{i-1}, v_{i} \right \}\)

Например, для рис.6 маршрут, выделенный жирно, записывается так \(<1, \left \{ 1, 6\right \}, 6, \left \{6, 4 \right \}, 4, \left \{ 4, 5\right \}, 5>\)

Цикл

Цикл - это маршрут, в котором \(v_0 = v_n\)

Простой цикл - это цикл, в котором выполняется следующие условия:

1. \( \left \{ v_i = v_0 \right \} \Longleftrightarrow \left \{i=0 \bigvee i=n \right \}\)

2. \( v_0, v_1,..., v_{n-1}\) - различные вершины

3. \( e_1, e_1,..., e_{n}\) - различные рёбра

Эйлеров цикл - это маршрут, проходящий по всем вершинам и рёбрам графа так, что все рёбра встречаются только 1 раз.

Кроме того, для обыкновенных графов цикл длины 2 не является циклом, но для орграфов - является.

Достижимость

Если существует такой маршрут, что \( v_0 = v\), \( v_n = u\), то вершина \(u\) - достижимая из \(v\); \( v, u \in D\), где \(D\) - отношение достижимости.

Свойства достижимости

  1. Симметрично для обыкновенного графа. Несимметрично для орграфа
  2. Транзитивно для любого вида графа

Стоит отметить 3 важнейших свойства:

  1. \( v, v \in D\)
  2. \( v, u \in D \Longrightarrow u, v \in D\) для обыкновенных графов
  3. \( v, u \in D; u,z \in D \Longrightarrow v,z \in D\)

Следовательно, для обыкновенных графов достижимость - это отношение эквивалентности. Значит, достижимость разбивает множество \(V\) на некоторые подмножества, то есть \(V\) - дизъюнктивная сумма некоторых подмножеств\[V=V_1 \bigsqcup V_2 \bigsqcup ... \bigsqcup V_{k} \]

\(V_{i}\) - компонента связности. Что это такое? Это некоторое подмножество, которое удовлетворяет некоторым условиям

  • Любая пара взаимодостижима

\( V_i = \left \{ v_{i_1} ... v_{i_n} \right \}, v_{i_j}, v_{i_k} \in D \)

  • Если взять вершину вне, то она не связана с исходными

\( v_{i_j},v \not \in D,\) если \( v \in V \backslash V_i \)

Пример.

Рис.7

Рассмотрим рис.7

  • Множество вершин - \( \left \{1, 2, ... 6 \right \} \)
  • Замечание для множества рёбер.

Для обыкновенного графа рёбра \( \left \{5, 6 \right \} \) и \( \left \{6, 5 \right \} \) - это один и тот же элемент множества.

  • Компонентов связности - 2

\( V_1 = \left \{1, 2, 3, 4 \right \} \)

\( V_2 = \left \{5, 6 \right \} \)

Проверка

\(V_1 \bigsqcup V_2\) образует всё множество вершин.

Внутри все вершины взаимодостижимы.

Из, например, 1 вершины в, например, 5 вершину попасть мы не можем.

Связный граф

Связный граф определяется следующим образом \( \forall v,u \in V \Longrightarrow v,u \in D \)

Как граф на рис.7 превратить в связный граф? Можно соединить вершины 2 и 5.

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

Задача №1: связаны ли 2 конкретно заданные вершины между собой?

Рис.8

Рассмотрим изображение графа в виде матрицы (рис.8, верхний левый угол). \(V_1, V_2, ..., V_{n}\) - вершины графа.

Матрицу заполняем по следующему принципу:

  • \( 1: \exists ребро \left \{V_{i}, V_{j} \right \} \)
  • \( 0: \not \exists ребро \left \{V_{i}, V_{j} \right \} \)

Замечание: если вместо 1 записать любое положительное число, например, 5, то оно будет означать кратность ребра

Можно заметить, что "верхний треугольник" матрицы после заполнения всех ячеек будет повторять "нижний". "Обрежем" верхнюю часть и получим новую конструкцию (рис.8, нижний правый угол). По памяти она занимает \(O(\frac{n^2 - n}{2})\)

В С++ такую матрицу можно создать с помощью Vector:

Vector<vector<int>>

Задача №2: найти всех соседей конкретно заданной вершины.

Рис.9

Если мы будем решать эту задачу с помощью "обрезанной матрицы", то обнаружим следующее: чтобы найти всех соседей, нужно будет перемещаться не только по строкам, но и по столбцам матрицы, а между столбцами переход медленнее, чем переход между строками.
Запишем всех соседей для каждой вершины на рис.7

\(V_1 \longrightarrow \left \langle V_2, V_4\right \rangle\)

\(V_2 \longrightarrow \left \langle V_1, V_3\right \rangle\)

\(V_3 \longrightarrow \left \langle V_1, V_4\right \rangle\)

\(V_4 \longrightarrow \left \langle V_1, V_3\right \rangle\)

\(V_5 \longrightarrow \left \langle V_6 \right \rangle\)

\(V_6 \longrightarrow \left \langle V_5 \right \rangle\)

Эти данные также можно выразить через Vector как матрицу, а можно с помощью map:

map <int, map <int,int>>

Деревья

Рис.10

Дерево - это связный граф без циклов.

Обычно для анализа дерева используют структуру, изображённую на рис.9

Представление деревьев в памяти

1 способ.

Ход по дереву "снизу вверх"

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

Тогда в соответствие дереву можно поставить массив, как изображено на рис.10

2 способ.

Ход по дереву "сверху вниз" (рис.11)

Рис.11
struct Node
{Node *left, *right;
int val;}