Связный граф

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Примеры применения[править | править вики-текст]

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

Связность для ориентированных графов[править | править вики-текст]

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

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

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

Некоторые критерии связности[править | править вики-текст]

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

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

См. также[править | править вики-текст]