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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
Строка 4: Строка 4:
 
|proof=
 
|proof=
  
Рассмотрим граф <tex>G,</tex> который содержит <tex>2N</tex> вершин, имеющих нечетную степень. Докажем, что его можно покрыть <tex>N</tex> рёберно-простыми путями.  
+
Рассмотрим граф <tex>G,</tex> который содержит <tex>2N</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> путей, которые являются простыми, так как рассматриваемый цикл эйлеров, и покрывают весь граф, поэтому полученное разбиение является искомым.
 
Соединим попарно вершины, имеющие нечётные степени, и получим связный граф <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> путей, которые являются простыми, так как рассматриваемый цикл эйлеров, и покрывают весь граф, поэтому полученное разбиение является искомым.

Версия 21:09, 13 октября 2018

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

Теорема:
Пусть [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]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