Связный граф
Связный граф — граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует как минимум один путь.
Содержание
Примеры применения
Прямым применением теории графов является теория сетей — и её приложение — теория электронных сетей. Например, все компьютеры, включенные в сеть Интернет, образуют связный граф, и хотя отдельная пара компьютеров может быть не соединена напрямую (в формулировке для графов — не быть соединенными ребром), от каждого компьютера можно передать информацию к любому другому (есть путь из любой вершины графа в любую другую).
Связность для ориентированных графов
В ориентированных графах различают несколько понятий связности.
Ориентированный граф называется сильно-связным, если в нём существует (ориентированный) путь из любой вершины в любую другую, или, что эквивалентно, граф содержит ровно одну сильно связную компоненту.
Ориентированный граф называется слабо-связным, если является связным неориентированный граф, полученный из него заменой ориентированных рёбер неориентированными.
Некоторые критерии связности
Здесь приведены некоторые критериальные (эквивалентные) определения связного графа:
Граф называется односвязным (связным), если:
- У него одна компонента связности
- Существует путь из любой вершины в любую другую вершину
- Существует путь из заданной вершины в любую другую вершину
- Содержит связный подграф, включающий все вершины исходного графа
- Содержит в качестве подграфа дерево, включающее все вершины исходного графа (такое дерево называется остовным)
- При произвольном делении его вершин на 2 группы всегда существует хотя бы 1 ребро, соединяющее пару вершин из разных групп
См. также
Напишите отзыв о статье "Связный граф"
Отрывок, характеризующий Связный граф
– Но, князь, – робко сказал Десаль, – в письме говорится о Витебске…– А, в письме, да… – недовольно проговорил князь, – да… да… – Лицо его приняло вдруг мрачное выражение. Он помолчал. – Да, он пишет, французы разбиты, при какой это реке?
Десаль опустил глаза.
– Князь ничего про это не пишет, – тихо сказал он.
– А разве не пишет? Ну, я сам не выдумал же. – Все долго молчали.
– Да… да… Ну, Михайла Иваныч, – вдруг сказал он, приподняв голову и указывая на план постройки, – расскажи, как ты это хочешь переделать…
Михаил Иваныч подошел к плану, и князь, поговорив с ним о плане новой постройки, сердито взглянув на княжну Марью и Десаля, ушел к себе.
Княжна Марья видела смущенный и удивленный взгляд Десаля, устремленный на ее отца, заметила его молчание и была поражена тем, что отец забыл письмо сына на столе в гостиной; но она боялась не только говорить и расспрашивать Десаля о причине его смущения и молчания, но боялась и думать об этом.
Ввечеру Михаил Иваныч, присланный от князя, пришел к княжне Марье за письмом князя Андрея, которое забыто было в гостиной. Княжна Марья подала письмо. Хотя ей это и неприятно было, она позволила себе спросить у Михаила Иваныча, что делает ее отец.
– Всё хлопочут, – с почтительно насмешливой улыбкой, которая заставила побледнеть княжну Марью, сказал Михаил Иваныч. – Очень беспокоятся насчет нового корпуса. Читали немножко, а теперь, – понизив голос, сказал Михаил Иваныч, – у бюра, должно, завещанием занялись. (В последнее время одно из любимых занятий князя было занятие над бумагами, которые должны были остаться после его смерти и которые он называл завещанием.)
– А Алпатыча посылают в Смоленск? – спросила княжна Марья.
– Как же с, уж он давно ждет.
Когда Михаил Иваныч вернулся с письмом в кабинет, князь в очках, с абажуром на глазах и на свече, сидел у открытого бюро, с бумагами в далеко отставленной руке, и в несколько торжественной позе читал свои бумаги (ремарки, как он называл), которые должны были быть доставлены государю после его смерти.