3.1.6. Связность. Компоненты связности

Определение. Вершина w орграфа D (графа G) достижима из вершины v, если либо v=w, либо существует путь из v в w(маршрут, соединяющий v, w).

Дадим более удобное определение связных графов.

Определение.

Граф называется связным, если для любых двух его вершин v, w существует простая цепь из v в w.

Определение. Граф (орграф) называется связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v, w (из v и w).

Определение. Орграф называется односторонне связным, если для любых его двух вершин, по крайней мере, одна достижима из другой.

Определение. Если граф не является связным, то он называется несвязным.

Определение. Компонентой связности графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа.

В дальнейшем количество компонент связности графа будем обозначать k.

Пример 79.

Данный граф не является связным: k = 3.

Данный граф является связным: k = 0.

Теорема. Пусть G – простой граф с n вершинами и k компонентами. Тогда число m его ребер удовлетворяет неравенствам

Следствие. Любой простой граф с n вершинами и более чем (т-1)(т-2)/2 ребрами связен.

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

Определение. Вершина графа, удаление которой увеличивает число компонент связности, называется разделяющейся.

Определение. Разделяющим множеством связного графа G называется такое множество его ребер, удаление которого приводит к несвязному графу.

Определение. Разрезом называется такое разделяющее множество, никакое собственное подмножество которого не является разделяющим.

Определение. Разрез, состоящий из одного ребра, называется мостом (перешейком).

Пример 80.

Для графа, изображенного на рис.33, каждое из множеств {e1, e2, e5} и {e3, e6, e7, e8} является разделяющим.

Разрезом является множество ребер {e1, e2}.

В графе возможно выделить несколько разделяющих множеств и разрезов.

3.2. Задачи поиска маршрутов (путей) в графе (орграфе)

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 3.1.6. Связность. Компоненты связности:

  1. И это означает, что анализ механизмов творчества мы должны начинать с конкретных психологических компонентов, которые так или
  2. § 4. ПУБЛИЧНАЯ ЛЕКЦИЯ ЮРИСТА
  3. ГЛАВА 2. Основные компоненты взаимодействия институтов силовых и политической в правовом государстве
  4. Гетерогенность, сбалансированность, роль государства
  5. 4.1. Компоненты внутреннего анализа ресурсов организации
  6. 2. Метод компонент, или метод передвижки возрастов.
  7. Продуктовая группа «Компоненты»
  8. 1.2.2. Особенности организации высокомолекулярных компонентов нефтяных систем
  9. 1.4. Ванадиловые комплексы и свободные стабильные радикалы в нефтях и нефтяных компонентах
  10. Аппаратный компонент Интернета