Редактирование: Точка сочленения, эквивалентные определения

Перейти к: навигация, поиск

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 34: Строка 34:
 
|proof=
 
|proof=
 
<tex>1 \Rightarrow 3</tex> Так как <tex>v</tex> {{---}} точка сочленения графа <tex>G</tex>, то граф <tex>G \setminus v</tex> не связен и имеет по крайней мере две компоненты. Образуем разбиение <tex>V \setminus \{v\}</tex>, отнеся к <tex>U</tex> вершины одной из этих компонент, а к <tex>W</tex> {{---}} вершины всех остальных компонент. Тогда любые две вершины <tex>u \in U</tex> и <tex>w \in W</tex> лежат в разных компонентах графа <tex>G \setminus v</tex>. Следовательно, любой простой путь из <tex>u</tex> в <tex>w</tex> графа <tex>G</tex> содержит <tex>v</tex>.
 
<tex>1 \Rightarrow 3</tex> Так как <tex>v</tex> {{---}} точка сочленения графа <tex>G</tex>, то граф <tex>G \setminus v</tex> не связен и имеет по крайней мере две компоненты. Образуем разбиение <tex>V \setminus \{v\}</tex>, отнеся к <tex>U</tex> вершины одной из этих компонент, а к <tex>W</tex> {{---}} вершины всех остальных компонент. Тогда любые две вершины <tex>u \in U</tex> и <tex>w \in W</tex> лежат в разных компонентах графа <tex>G \setminus v</tex>. Следовательно, любой простой путь из <tex>u</tex> в <tex>w</tex> графа <tex>G</tex> содержит <tex>v</tex>.
 
<tex>3 \Rightarrow 2</tex> Следует из того, что (2) - частный случай (3).
 
 
<tex>2 \Rightarrow 1</tex>  Если <tex>v</tex> принадлежит любому простому пути в <tex>G</tex>, соединяющему <tex>u</tex> и <tex>w</tex>, то в <tex>G</tex> нет простого пути, соединяющего эти вершины в <tex>G \setminus \{v\}</tex>. Поскольку <tex>G \setminus \{v\}</tex> не связен, то <tex>v</tex> {{---}} точка сочленения графа <tex>G</tex>.
 
}}
 
 
 
{{Теорема
 
|statement=
 
Пусть <tex>G</tex> {{---}} связный граф с не менее чем тремя вершинами. Следующие утверждения эквивалентны:
 
# <tex>G</tex> {{---}} блок ;
 
# любые две вершины графа <tex>G</tex> принадлежат некоторому общему простому циклу;
 
# любая вершина и любое ребро графа <tex>G</tex> принадлежат некоторому общему простому циклу;
 
# любые два ребра графа <tex>G</tex> принадлежат некоторому общему простому циклу;
 
# для любых двух вершин и любого ребра графа <tex>G</tex> существует простая цепь, соединяющая эти вершины и включающая данное ребро;
 
# для любых трех различных вершин графа <tex>G</tex> существует простая цепь, соединяющая две из них и проходящая через третью;
 
# для каждых трех различных вершин графа <tex>G</tex> существует простая цепь, соединяющая  две из них и не проходящая через третью.
 
 
|proof=
 
<tex>1 \Rightarrow 2</tex> Пусть <tex>u</tex>,<tex>v</tex> - различные вершины графа <tex>G</tex>, а <tex>U</tex> - множество вершин, отличных от <tex>u</tex>, которые лежат на простом цикле, содержащем <tex>u</tex>. Поскольку в <tex>G</tex> по крайней мере три вершины и нет точек сочленения, то в <tex>G</tex> нет также мостов. Значит, каждая вершина, смежная с <tex>u</tex>, принадлежит <tex>U</tex>, т.е. <tex>U</tex> не пусто. Предположим, что <tex>u</tex> не принадлежит <tex>U</tex>. Пусть <tex>w</tex> - вершина в <tex>U</tex>, для которой расстояние <tex>d</tex>(<tex>w</tex>-<tex>u</tex>)-цепь минимально. Пусть <tex>P_0</tex> - кратчайшая простая (<tex>w</tex>-<tex>u</tex>)- цепь, а <tex>P_1</tex> и <tex>P_2</tex> -  две простые (<tex>u</tex>-<tex>w</tex>)-цепи цикла, содержащего <tex>u</tex> и <tex>w</tex>. Так как <tex>w</tex> не является точкой сочленения, то существует простая (<tex>u</tex>-<tex>v</tex>)-цепь <tex>P'</tex>, не содержащая <tex>w</tex>. Обозначим через <tex>w'</tex> ближайшую к <tex>u</tex> вершину, принадлежащую <tex>P'</tex>, которая также принадлежит <tex>P_0</tex>, и через <tex>u'</tex> последнюю вершину (<tex>u</tex>-<tex>w'</tex>)-подцепи в <tex>P'</tex>, которая принадлежит или <tex>P_1</tex>, или <tex>P_2</tex>. Не теряя общности, предположим, что <tex>u</tex>' принадлежит  <tex>P_1</tex>.
 
Пусть <tex>Q_1</tex> - простая (<tex>u</tex>-<tex>w'</tex>)-цепь, содержащая (<tex>u</tex>-<tex>u'</tex>)-подцепь цепи <tex>P_1</tex> и (<tex>u'</tex>-<tex>w'</tex>)-подцепь цепи  <tex>P'</tex>, а <tex>Q_2</tex> - простая (<tex>u</tex>-<tex>w'</tex>)-подцепь, содержащая <tex>P_2</tex> вслед за (<tex>w</tex>-<tex>w</tex>')-подцепью цепи <tex>P_0</tex>. Ясно, что <tex>Q_1</tex> и <tex>Q_2</tex> - непересекающиеся простые (<tex>u</tex>-<tex>w'</tex>)-цепи. Вместе они образуют простой цикл, так что <tex>w'</tex> принадлежит <tex>U</tex>. Поскольку <tex>w'</tex> принадлежит кратчайшей цепи, <tex>d</tex>(<tex>w'</tex>,<tex>u</tex>)<<tex>d</tex>(<tex>w</tex>,<tex>u</tex>). Это противоречит выбору <tex>w</tex> и, следовательно,  доказывает, что <tex>u</tex> и <tex>v</tex> лежат на одном простом цикле.
 
  
 
<tex>3 \Rightarrow 2</tex> Следует из того, что (2) - частный случай (3).
 
<tex>3 \Rightarrow 2</tex> Следует из того, что (2) - частный случай (3).

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)