Связный граф
Материал из Википедии — свободной энциклопедии
Связный граф — граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует по крайней мере один путь.
Содержание |
[править] Примеры применения
Прямым применением теории графов является теория сетей - и её приложение - теория электронных сетей. Например, все компьютеры, включенные в сеть Интернет, образуют связный граф, и хотя отдельная пара компьютеров может быть не соединена напрямую (в формулировке для графов - не быть соединены ребром), от каждого компьютера можно передать информацию к любому другому(есть путь из любой вершины графа в любую другую).
[править] Связность для орграфов
В связном ориентированном графе из любой вершины в любую существует путь, при этом связный ориентированный граф содержит ровно одну сильно связную компоненту.
[править] Некоторые критерии связности
Здесь приведены некоторые критериальные(эквивалентные) определения связного графа:
Граф называется односвязным (связным), если:
1 У него одна компонента связности
2 Существует путь из любой вершины в любую
3 Существует путь из заданной вершины в любую
4 Содержит связный подграф, включающий все вершины исходного графа
5 Содержит в качестве подграфа дерево,включающее все вершины исходного графа(оно называется остовным)
6 При произвольном делении его вершин на 2 группы всегда существет хотя бы 1 ребро, соединяющее пару вершин из разных групп
