Теория Графов 5

Определение и основные свойства двусвязных графов

Доказательство

Пусть v1 2 B1 è v2 2 B2

ò. ê. åñòü (v1;u2)-öåïü â B1 è (u2;v2)-öåïü â B2 сцепляя их получаем (v1;v2) ïóòü

Определение и основные свойства двусвязных графов

Доказательство

Пусть v1 2 B1 è v2 2 B2

ò. ê. åñòü (v1;u2)-öåïü â B1 è (u2;v2)-öåïü â B2 сцепляя их получаем (v1;v2) ïóòü

4) åñëè v любая другая вершина из B1 \B2,

Расин О.В. Двусвязные графы

Определение и основные свойства двусвязных графов

Доказательство

Пусть v1 2 B1 è v2 2 B2

ò. ê. åñòü (v1;u2)-öåïü â B1 è (u2;v2)-öåïü â B2 сцепляя их получаем (v1;v2) ïóòü

4) åñëè v любая другая вершина из B1 \B2,

Определение и основные свойства двусвязных графов

Доказательство

Следовательно, при удалении любой вершины из B1 [B2 îí остается связным

Определение и основные свойства двусвязных графов

Доказательство

Следовательно, при удалении любой вершины из B1 [B2 îí остается связным

Таким образом B1 [B2 двусвязен, а значит является блоком

Определение и основные свойства двусвязных графов

Доказательство

Следовательно, при удалении любой вершины из B1 [B2 îí остается связным

Таким образом B1 [B2 двусвязен, а значит является блоком

Последнее противоречит тому, что B1 è B2 блоки

Определение и основные свойства двусвязных графов

Доказательство

Следовательно, при удалении любой вершины из B1 [B2 îí остается связным

Таким образом B1 [B2 двусвязен, а значит является блоком

Последнее противоречит тому, что B1 è B2 блоки (т. к. они не максимальные двусвязные компоненты) #

Определение и основные свойства двусвязных графов

о пересечении блоков

Теорема 1.3

1) Если два различных блока графа G имеют общую вершину v, òî v точка сочленения.

Определение и основные свойства двусвязных графов

о пересечении блоков

Теорема 1.3

1)Если два различных блока графа G имеют общую вершину v, òî v точка сочленения.

2)Любая точка сочленения принадлежит хотя бы двум блокам.

Определение и основные свойства двусвязных графов

о пересечении блоков

Теорема 1.3

1)Если два различных блока графа G имеют общую вершину v, òî v точка сочленения.

2)Любая точка сочленения принадлежит хотя бы двум блокам.

Д о к а з а т е л ь с т в о. 1) Пусть v 2 B1 \B2