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

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

Эквивалентные условия двусвязности графа

4любые два ребра лежат на простом цикле.

Äо к а з а т е л ь с т в о. Эквивалентность условий (1) и (2) следует из теоремы 1.1

(2) =) (3)

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

Эквивалентные условия двусвязности графа

4любые два ребра лежат на простом цикле.

Äо к а з а т е л ь с т в о. Эквивалентность условий (1) и (2) следует из теоремы 1.1

(2) =) (3) Возьмем вершину v и ребро e = zt. Согласно условию (2) существует цикл C, проходящий через v è z.

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

Эквивалентные условия двусвязности графа

4любые два ребра лежат на простом цикле.

Äо к а з а т е л ь с т в о. Эквивалентность условий (1) и (2) следует из теоремы 1.1

(2) =) (3) Возьмем вершину v и ребро e = zt. Согласно условию (2) существует цикл C, проходящий через v è z.

Åñëè t 2 C, то доказывать нечего

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

Доказательство (2) =) (3)

Пусть t 2= C.

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

Доказательство (2) =) (3)

Пусть t 2= C. Согласно условию (2) существует цикл C1, проходящий через v è t.

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

Доказательство (2) =) (3)

Пусть t 2= C. Согласно условию (2) существует цикл C1, проходящий через v è t.

Åñëè z 2 C1, то доказывать нечего

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

Доказательство (2) =) (3)

Пусть t 2= C. Согласно условию (2) существует цикл C1, проходящий через v è t.

Åñëè z 2 C1, то доказывать нечего

Пусть z 2= C1. Öèêë C1 представляет собой две простые непересекающиеся (v;z)-öåïè.

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

Доказательство (2) =) (3)

Пусть t 2= C. Согласно условию (2) существует цикл C1, проходящий через v è t.

Åñëè z 2 C1, то доказывать нечего

Пусть z 2= C1. Öèêë C1 представляет собой две простые непересекающиеся (v;z)-öåïè.

Выберем одну из них P10

P3

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

Доказательство (2) =) (3)

Пусть t 2= C. Согласно условию (2) существует цикл C1, проходящий через v è t.

Åñëè z 2 C1, то доказывать нечего

Пусть z 2= C1. Öèêë C1 представляет собой две простые непересекающиеся (v;z)-öåïè.

Выберем одну из них P10

P3

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

Доказательство (2) =) (3)

Пусть t 2= C. Согласно условию (2) существует цикл C1, проходящий через v è t.

Åñëè z 2 C1, то доказывать нечего

Пусть z 2= C1. Öèêë C1 представляет собой две простые непересекающиеся (v;z)-öåïè.

Выберем одну из них P10