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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 12 промежуточных версий 6 участников)
Строка 1: Строка 1:
 
Следующее утверждение являются следствием из [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|критерия Эйлеровости]] [[Основные определения теории графов|графа]]:
 
Следующее утверждение являются следствием из [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|критерия Эйлеровости]] [[Основные определения теории графов|графа]]:
 
{{Теорема|statement=
 
{{Теорема|statement=
−
Пусть <tex>G</tex> {{---}} граф, в котором <tex>2N</tex> вершин имеют нечетную [[Основные определения теории графов|степень]]. Тогда множество ребер <tex>G</tex> можно покрыть <tex>N</tex> [[Основные определения теории графов|реберно-простыми]] путями.
+
Пусть <tex>G</tex> {{---}} связный граф, в котором <tex>2N</tex> вершин имеют нечётную [[Основные определения теории графов|степень]]. Тогда множество рёбер <tex>G</tex> можно покрыть <tex>N</tex> [[Основные определения теории графов|рёберно-простыми]] путями.
 
|proof=
 
|proof=
−
[[Файл:Make_edges_paths_1.png|180px|right|thumb|Пример графа для <tex>N = 2</tex>]]
 
  
−
'''Необходимость'''<br/>
+
Рассмотрим связный граф <tex>G,</tex> который содержит <tex>2N</tex> вершин, имеющих нечётную степень. Докажем, что его можно покрыть <tex>N</tex> рёберно-простыми путями.  
−
Докажем, что <tex>G</tex> можно покрыть <tex>N</tex> реберно-простыми путями.<br/>
 
−
Добавим <tex> N </tex> ребер <tex>uv</tex> таких, что <tex>uv</tex> <tex>\notin</tex> <tex>G</tex> и степени вершин <tex>u</tex> и <tex>v</tex> нечетные. Тогда степени всех вершин станут четными, и в <tex>G</tex> появится Эйлеров цикл <tex>c</tex>. Удалим из <tex>c</tex> добавленные ребра.<br/>
 
−
Заметим, что теперь цикл распадается на <tex> N </tex> простых путей. В самом деле: отметим удаленные ребра в порядке их обхода в Эйлеровом цикле. Тогда <tex> c </tex> разбивается на <tex> N </tex> реберно-непересекающихся путей, т.к. каждый такой путь мы можем сопоставить удаленному ребру. Необходимость доказана.
 
−
 
 
−
 
 
−
'''Достаточность'''<br/>
 
−
Докажем, что <tex>G</tex> нельзя покрыть менее, чем <tex>N</tex> реберно-простыми путями.<br/>
 
−
Предположим, что такое возможно, и существует набор реберно-простых путей <tex>p_1, p_2, ... p_k, k < N</tex>, такой что он покрывает все ребра <tex>G</tex>.<br/>
 
−
Пусть <tex>i-</tex>й путь из этого набора имеет вид <tex> w_i = u_{i_0}e_{i_1}u_{i_1}...u_{i_l}</tex>. Добавим в <tex>G</tex> все ребра вида <tex>u_{i_l}u_{{i+1}_0}</tex> и ребро <tex>u_{k_l}u_{1_0}</tex>. В новом графе появится Эйлеров цикл, т.к. мы добавили ребра, соединяющие конец и начало <tex> i </tex> и <tex> i + 1 </tex> пути соответственно. Всего добавлено <tex>k</tex> ребер, которые меняют четность не более, чем <tex>2k</tex> вершин. Т.к. <tex>k < N</tex>, то в графе останутся вершины нечетной степени, что не удовлетворяет критерию Эйлеровости графа.<br/>
 
−
Противоречие. Значит, такого набора, что его мощность меньше <tex>N</tex>, не существует.
 
  
 +
Добавим в граф <tex>N</tex> рёбер, соединив попарно вершины, имеющие нечётные степени, и получим связный граф <tex>G',</tex> все вершины которого имеют чётную степень. Такой граф удовлетворяет [[Эйлеровость_графов#.D0.9A.D1.80.D0.B8.D1.82.D0.B5.D1.80.D0.B8.D0.B9_.D1.8D.D0.B9.D0.BB.D0.B5.D1.80.D0.BE.D0.B2.D0.BE.D1.81.D1.82.D0.B8|критерию эйлеровости]] и содержит эйлеров цикл. Рассмотрим этот цикл и удалим из него <tex>N</tex> добавленных ребер <tex>G' \backslash G.</tex> Цикл распадётся на <tex>N</tex> путей, которые являются простыми, так как рассматриваемый цикл эйлеров, и покрывают весь граф, поэтому полученное разбиение является искомым.
 
}}
 
}}
  
 
==См. также==
 
==См. также==
−
* [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
+
* [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеровость графов]]
  
 
==Источники информации==
 
==Источники информации==

Текущая версия на 19:35, 4 сентября 2022

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

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

Рассмотрим связный граф [math]G,[/math] который содержит [math]2N[/math] вершин, имеющих нечётную степень. Докажем, что его можно покрыть [math]N[/math] рёберно-простыми путями.

Добавим в граф [math]N[/math] рёбер, соединив попарно вершины, имеющие нечётные степени, и получим связный граф [math]G',[/math] все вершины которого имеют чётную степень. Такой граф удовлетворяет критерию эйлеровости и содержит эйлеров цикл. Рассмотрим этот цикл и удалим из него [math]N[/math] добавленных ребер [math]G' \backslash G.[/math] Цикл распадётся на [math]N[/math] путей, которые являются простыми, так как рассматриваемый цикл эйлеров, и покрывают весь граф, поэтому полученное разбиение является искомым.
[math]\triangleleft[/math]

См. также

Источники информации

  • Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Покрытие_рёбер_графа_путями&oldid=85543»