Связный граф

Прямым применением теории графов является теория сетей — и её приложение — теория электронных сетей. Например, все компьютеры, включённые в сеть Интернет, образуют связный граф, и хотя отдельная пара компьютеров может быть не соединена напрямую (в формулировке для графов — не быть соединёнными ребром), от каждого компьютера можно передать информацию к любому другому (есть путь из любой вершины графа в любую другую)^[1].

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

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

Ориентированный граф называется слабо связным, если является связным неориентированным графом, полученным из него заменой ориентированных рёбер неориентированными.

Здесь приведены некоторые критериальные (эквивалентные) определения связного графа.
Граф называется односвязным (связным), если:

1. У него одна компонента связности.
2. Существует путь из любой вершины в любую другую вершину.
3. Существует путь из заданной вершины в любую другую вершину.
4. Содержит связный подграф, включающий все вершины исходного графа.
5. Содержит в качестве подграфа дерево, включающее все вершины исходного графа (такое дерево называется остовным).
6. При произвольном делении его вершин на две группы всегда существует хотя бы одно ребро, соединяющее пару вершин из разных групп.