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

Деревья

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

2) Покажем единственность простой цепи

î/ï Пусть найдутся вершины u è v, между которыми есть две различные простые цепи P1 è P2.

На рис. изображена иллюстрация к доказательству цепь P1 изображена идущей по прямой, а цепь P2 изображена участками кривых линий (на участке от u äî x öåïü P2 совпадает с P1)

Расин О.В. Деревья

Деревья

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

2) Покажем единственность простой цепи

î/ï Пусть найдутся вершины u è v, между которыми есть две различные простые цепи P1 è P2.

На рис. изображена иллюстрация к доказательству цепь P1 изображена идущей по прямой, а цепь P2 изображена участками кривых линий (на участке от u äî x öåïü P2 совпадает с P1)

Для доказательства будут важны участки цепей от u äî z

Расин О.В. Деревья

Деревья

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

2) Покажем единственность простой цепи

î/ï Пусть найдутся вершины u è v, между которыми есть две различные простые цепи P1 è P2.

На рис. изображена иллюстрация к доказательству цепь P1 изображена идущей по прямой, а цепь P2 изображена участками кривых линий (на участке от u äî x öåïü P2 совпадает с P1)

Для доказательства будут важны участки цепей от u äî z

Пусть x последняя общая вершина начальных участков цепей (случай u = x не исключен)

Расин О.В. Деревья

Деревья

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

2) Покажем единственность простой цепи

î/ï Пусть найдутся вершины u è v, между которыми есть две различные простые цепи P1 è P2.

На рис. изображена иллюстрация к доказательству цепь P1 изображена идущей по прямой, а цепь P2 изображена участками кривых линий (на участке от u äî x öåïü P2 совпадает с P1)

Для доказательства будут важны участки цепей от u äî z

Пусть x последняя общая вершина начальных участков цепей (случай u = x не исключен)

ßñíî, ÷òî x 6= v (иначе P1 = P2)

Расин О.В. Деревья

Деревья

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

Расин О.В. Деревья

Деревья

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

Пусть z следующая после x общая вершина для цепей P1 è P2

Расин О.В. Деревья

Деревья

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

Пусть z следующая после x общая вершина для цепей P1 è P2 (такая вершина есть, в крайнем случае z = v)

Расин О.В. Деревья

Деревья

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

Пусть z следующая после x общая вершина для цепей P1 è P2 (такая вершина есть, в крайнем случае z = v)

Между вершинами x è z по крайней мере на одной из цепей есть вершина y 6= x; z

Расин О.В. Деревья

Деревья

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

Пусть z следующая после x общая вершина для цепей P1 è P2 (такая вершина есть, в крайнем случае z = v)

Между вершинами x è z по крайней мере на одной из цепей есть вершина y 6= x; z (в противном случае есть ребро

xz 2 P1 \P2, что противоречит выбору x)

Расин О.В. Деревья