<aside> 💡 Table of contents

</aside>

Алгоритмы на графах

Терминология

В литературе часто используются следующие обознаечния:

• $G=(V,E)$ - граф
• $V(G)$ - множество вершин в графе $G$.
• $E=\{(u,v)\ \lvert\ u,v\in V\}$ - множество пар ребер графа $G$.

Полный граф - граф, в котором все вершины соединены со всеми. В полном графе $E=V^2$.

Степень вершины - количество ребер инцидентных вершине.

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

Обходы

Обход в глубину DFS

Обход в ширину BFS

Топологическая сортировка

Компоненты связности

Компонента связности - класс эквивалентности относительно отношения связности.

В случае слабой связности, утверждается, что в графе существует путь из $u$ в $v$, обозначается как $u\rightsquigarrow v$. Сильная связность подразумевает собой выполнение условия слабой связности, при этом выполняется и обратное условие ($u\rightsquigarrow v \wedge v\rightsquigarrow u$).

Граф называется связным, если он состоит из одной компоненты связности, в противном случае - несвязным.

Нахождение компонент связности в неориентированном графе

Конденсация графа/поиск компонент сильной связности (алгоритм Косарайю)