# Дискретка - 4 пачка дз


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

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

1) ребра:
1, 2
1, 3
2, 3
4, 5
4, 7
5, 7
5, 6
6, 7

$$
\begin{pmatrix}
. & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
1 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\
2 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\
3 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\
4 & 0 & 0 & 0 & 0 & 1 & 0 & 1\\
5 & 0 & 0 & 0 & 1 & 0 & 1 & 1\\
6 & 0 & 0 & 0 & 0 & 1 & 0 & 1\\
7 & 0 & 0 & 0 & 1 & 1 & 1 & 0
\end{pmatrix}
$$

**Матрица инцидентности** — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).
В случае ориентированного графа каждой дуге <x,y> ставится в соответствующем столбце: «1» в строке вершины x и «-1» в строке вершины y; если связи между вершиной и ребром нет, то в соответствующую ячейку ставится «0».

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

Для неориентированных графов без петель и кратных рёбер матрица инцидентности бинарна (состоит из нулей и единиц). Для ориентированных графов без петель и кратных рёбер матрица инцидентности состоит из нулей, единиц и −1. (-1 для той вершины куда идет ребро. 1 для вершины из которой идет ребро)

$$
\begin{pmatrix}
. & e1 & e2 & e3 & e4 & e5 & e6 & e7 & e8 & e9\\
1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
2 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
3 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\
4 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0\\
5 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1\\
6 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0\\
7 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1
\end{pmatrix}
$$


**Компонентой сильной связности** называется класс эквивалентности множества вершин ориентированного графа относительно отношения сильной связности. Другими словами компонента сильной связности = сильно связный подграф

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

Компоненты сильной связности: {1,2}, {3,4}

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

Построение матрицы достижимости:
1. Находим булевы степени матрицы A. от 2 до n, где n - размерность матрицы
2. С помощью логического сложения складываем все булевы степени от 1 до n


E из A получаются преобразованием записью 1 везде где есть не ноль.

$$
E = E^1 + E^2 + E^3 + E^4 = \begin{pmatrix}1 & 1 & 1 & 1\\1 & 1 & 1 & 1\\0 & 0 & 1 & 1\\0 & 0 & 1 & 1\end{pmatrix}
$$

Матрица сильной связности простого орграфа — бинарная матрица, содержащая информацию обо всех сильно связанных вершинах в орграфе. Матрица сильной связности симметрична. У сильно связного графа такая матрица заполнена единицами.
Для построения матрицы сильной связности берем матрицу достижимости и составляем матрицу той же размерности по формуле для конкретной ячейки: Cij = ((eij)\*(eji)). Другими словами, если еденичка расположена в изначальной матрице симетрично другой еденичке (или она находится на главной диагонали) - она пойдет в матрицу сильной связности

$$
S = \begin{pmatrix}1 & 1 & 0 & 0\\1 & 1 & 0 & 0\\0 & 0 & 1 & 1\\0 & 0 & 1 & 1\end{pmatrix}
$$

Начинаем определять компоненты сильной связности. Объединяем еденички построчно, убираем строки и столбцы тех еденичек, которые были объединены
В 1 строчке компонент сильной связности - { 1,2 }
Убираем 2 крайних левых столбца и 2 крайних верхние строчки

$$
S2 = \begin{pmatrix}1 & 1\\1 & 1\end{pmatrix}
$$
В 3 строчке компонент сильной связности - { 3,4 }

Для проверки - тут видно, что компоненты сильной связности действительно {1,2}, {3,4}


**О́стовное де́рево графа (Остов)** — это дерево, подграф данного (**неориентированного**) графа, с тем же числом вершин, что и у исходного графа. Остовное дерево получается из исходного графа удалением максимального числа рёбер, входящих в циклы, но без нарушения связности графа. Остовное дерево включает в себя все n вершин исходного графа и содержит n-1 ребро.

Любое остовное дерево в графе с n вершинами содержит ровно n-1 ребро.

**Матричная теорема о деревьях или теорема Кирхгофа** — даёт выражение на число остовных деревьев графа через определитель определённой матрицы.

Пусть G — связный помеченный граф с матрицей Кирхгофа M. Все алгебраические дополнения матрицы Кирхгофа M равны между собой и их общее значение равно количеству остовных деревьев графа G.

**Матрица Кирхгофа**: квадратная матрица, в которой каждый элемент высчитывается по формуле
:
Степень (валентность) вершины графа (deg) — количество рёбер графа G, инцидентных вершине x.Другими словами - сколько ребер выходит из графа При подсчёте степени ребро-петля учитывается дважды
(ui, uj) принадлежит E(G) - значит, что в графе есть ребро от i до j

Составим матрицу Кирхгофа
$$
\begin{pmatrix}
. & a & b & c & d\\
a & 3 & -1 & -1 & -1\\
b & -1 & 2 & 0 & -1\\
c & -1 & 0 & 2 & -1\\
d & -1 & -1 & -1 & 3
\end{pmatrix}
$$

Найдем любое алгебраическое дополнение
$$
1*
\begin{bmatrix}
3 & -1 & -1\\
-1 & 2 & 0\\
-1 & 0 & 2
\end{bmatrix} = (2*2) - (-1*2) + (2) = 4 + 2 + 2 = 8
$$

Число остовных деревеьев = 8

на пикче номера сдвинуты на 4 вперед :(


**Плана́рный граф** — граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам. Какое-либо конкретное изображение планарного графа на плоскости без пересечения рёбер не по вершинам называется плоским графом. Иначе говоря, планарный граф изоморфен некоторому плоскому графу, изображённому на плоскости так, что его вершины — это точки плоскости, а рёбра — кривые на плоскости, которые если и пересекаются между собой, то только по вершинам.

Если граф содержит подграф гомеоморфный графу К5 или К3.3, то он непланарный
При удалении вершины 3 получаем граф К5, следовательно исходный граф непланарный.


Источник - вершина 1. Ищем путь в вершину 5
Присвоим 1-й вершине метку равную 0, потому как эта вершина — источник. Остальным вершинам присвоим метки равные бесконечности.

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


После того как мы рассмотрели все вершины, в которые есть прямой путь из W, вершину W мы отмечаем как посещённую, и выбираем из ещё не посещенных такую, которая имеет минимальное значение метки, она и будет следующей вершиной W. В данном случае это вершина 2 или 5. Если есть несколько вершин с одинаковыми метками, то не имеет значения какую из них мы выберем как W.
Закрываем вершину 3
Закрываем вершины 2, 6 и 4

Крадчайший путь из вершины 1 в вершину 5 = 4

6) Найдите максимальный поток в заданной транспортной сети (s – начальная вершина, t – конечная), используя алгоритм Форда-Фалкерсона. Проверьте ответ по теореме Форда-Фалкерсона (найдите минимальный разрез графа сети).


Теорема форда-фалкерсона: величина максимального потока в графе путей равна величине пропускной способности его минимального разреза.

### Алгоритм форда-фалкерсона
Следует понимать остаточную сеть как тот же граф, который имеется на входе, но в этом случае мы будем производить над ним некоторые операции:

1. Отправлять определенное количество потока из текущей вершины в соседние.
2. Возвращать определенное количество потока из соседних вершин в текущую.

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

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

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

Из веса рёбер на этом пути высчитываем размер потока, который мы пустили.

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

Возвращаемся обратно к нахождению пути в остаточной сети после модификации.

Нарисуем ориентированный граф по матрице смежности:


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

Проделываем аналогичные действия до тех пор, пока существует путь от S до T
Находим путь s-t. Пропускаем по потоку 15 едениц. Перестраиваем остаточную сеть

Находим путь s-a-b-t
Пропускаем по потоку 2 еденицы. Перестраиваем остаточную сеть

Находим путь s-d-b-c-t
Пропускаем по потоку 5 едениц. Перестраиваем остаточную сеть

Находим путь s-d-c-t
Пропускаем по потоку 10 едениц. Перестраиваем остаточную сеть

Пути из истока в сток не существует. Работу алгоритма можно прекратить. Ответом к поставленной задаче будет служить сумма потоков всех найденных увеличивающихся путей (сколько пустили едениц, такой и ответ)
2 + 15 + 2 + 5 + 10 = 34

**Доказать через теорему - я хз как искать минимальный разрез графа TODO**

Минимальный разрез в данном контексте разрез с минимальной пропускной способностью
Разрез ищем так - берем и стираем ребра так, чтобы нельзя было попасть из s в t, чтобы сумма весов этих ребер была минимальной
Два варианта
1) (Стабильный понятный) Берем и пробуем все варианты разрезов

Тут разрезы:
18+2+15 = 35
10+9+4+15 = 34 (минимальный)
20 + 4 + 15 = 39

2) (Я сам не до конца понял, но как-то натянул сову на глобус) Выделяем вершины с возможным избыточным потоком (те, в которые может прийти больше чем они могут отдать). Здесь это 4 (все еще может отдать 4, а 2 забрать их не может) и 1 (может прийти сколько угодно)
Разрезаем ребра, которые соединяют выделенные вершины и невыделенные

Брал отсюда