Покрытие рёбер графа путями — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
Пусть <tex>G</tex> {{---}} [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов#cite_note-almost-0|почти связный]] граф, в котором <tex>2N</tex> вершин имеют нечетную [[Основные определения теории графов|степень]]. Тогда множество ребер <tex>G</tex> можно покрыть <tex>N</tex> реберно простыми путями.
 
Пусть <tex>G</tex> {{---}} [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов#cite_note-almost-0|почти связный]] граф, в котором <tex>2N</tex> вершин имеют нечетную [[Основные определения теории графов|степень]]. Тогда множество ребер <tex>G</tex> можно покрыть <tex>N</tex> реберно простыми путями.
 
|proof=
 
|proof=
 +
[[Файл:Make_edges_paths_1.png|200px|right|thumb|Пример графа для <tex>N = 2</tex>]]
 +
 
'''Необходимость'''<br/>
 
'''Необходимость'''<br/>
 
Докажем, что <tex>G</tex> можно покрыть <tex>N</tex> реберно-простыми цепями.<br/>  
 
Докажем, что <tex>G</tex> можно покрыть <tex>N</tex> реберно-простыми цепями.<br/>  
 
Добавим в <tex>G</tex> <tex>N</tex> ребер <tex>uv</tex> таких, что <tex>uv</tex> &notin; <tex>G</tex> и степени вершин <tex>u</tex> и <tex>v</tex> нечетные. Тогда степени всех вершин станут четными, и в <tex>G</tex> появится Эйлеров цикл <tex>c</tex>. Удалим из <tex>c</tex> добавленные ребра.<br/>
 
Добавим в <tex>G</tex> <tex>N</tex> ребер <tex>uv</tex> таких, что <tex>uv</tex> &notin; <tex>G</tex> и степени вершин <tex>u</tex> и <tex>v</tex> нечетные. Тогда степени всех вершин станут четными, и в <tex>G</tex> появится Эйлеров цикл <tex>c</tex>. Удалим из <tex>c</tex> добавленные ребра.<br/>
 
Тогда цикл <tex>c</tex> распадется на <tex>N</tex> путей, которым будут принадлежать все ребра <tex>G</tex>.
 
Тогда цикл <tex>c</tex> распадется на <tex>N</tex> путей, которым будут принадлежать все ребра <tex>G</tex>.
 +
<br clear="all"/>
 +
 +
[[Файл:Make_edges_paths_2.png|200px|right|thumb|Пример графа для <tex>N = 3</tex>]]
  
 
'''Достаточность'''<br/>
 
'''Достаточность'''<br/>

Версия 22:52, 16 марта 2012

Следующее утверждение являются следствием из критерия Эйлеровости графа:

Теорема:
Пусть [math]G[/math]почти связный граф, в котором [math]2N[/math] вершин имеют нечетную степень. Тогда множество ребер [math]G[/math] можно покрыть [math]N[/math] реберно простыми путями.
Доказательство:
[math]\triangleright[/math]
Пример графа для [math]N = 2[/math]

Необходимость
Докажем, что [math]G[/math] можно покрыть [math]N[/math] реберно-простыми цепями.
Добавим в [math]G[/math] [math]N[/math] ребер [math]uv[/math] таких, что [math]uv[/math][math]G[/math] и степени вершин [math]u[/math] и [math]v[/math] нечетные. Тогда степени всех вершин станут четными, и в [math]G[/math] появится Эйлеров цикл [math]c[/math]. Удалим из [math]c[/math] добавленные ребра.
Тогда цикл [math]c[/math] распадется на [math]N[/math] путей, которым будут принадлежать все ребра [math]G[/math].

Пример графа для [math]N = 3[/math]

Достаточность
Докажем, что [math]G[/math] нельзя покрыть менее, чем [math]N[/math] реберно-простыми путями.
Предположим, что такое возможно, и существует набор реберно-простых путей [math]p_1, p_2, ... p_k, k \lt N[/math], такой что он покрывает все ребра [math]G[/math].
Пусть [math]i-[/math]й путь из этого набора имеет вид [math] w_i = u_{i_0}e_{i_1}u_{i_1}...u_{i_l}[/math]. Добавим в [math]G[/math] все ребра вида [math]u_{i_l}u_{{i+1}_0}[/math] и ребро [math]u_{k_l}u_{1_0}[/math]. В новом графе появится Эйлеров цикл. Всего будет добавлено [math]k[/math] ребер, которые изменят четность не более, чем [math]2k[/math] вершин. Т.к. [math]k \lt N[/math], то в графе останутся вершины нечетной степени.

Противоречие. Значит, такого набора, что его мощность меньше [math]N[/math], не существует.
[math]\triangleleft[/math]

См. также

Литература

  • Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6