Покрытие рёбер графа путями — различия между версиями
(→Покрытие ребер графа путями) |
м (rollbackEdits.php mass rollback) |
||
| (не показано 30 промежуточных версий 11 участников) | |||
| Строка 1: | Строка 1: | ||
| − | |||
Следующее утверждение являются следствием из [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|критерия Эйлеровости]] [[Основные определения теории графов|графа]]: | Следующее утверждение являются следствием из [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|критерия Эйлеровости]] [[Основные определения теории графов|графа]]: | ||
| − | {{ | + | {{Теорема|statement= |
| − | Пусть <tex>G</tex> - | + | Пусть <tex>G</tex> {{---}} связный граф, в котором <tex>2N</tex> вершин имеют нечётную [[Основные определения теории графов|степень]]. Тогда множество рёбер <tex>G</tex> можно покрыть <tex>N</tex> [[Основные определения теории графов|рёберно-простыми]] путями. |
| + | |proof= | ||
| + | |||
| + | Рассмотрим связный граф <tex>G,</tex> который содержит <tex>2N</tex> вершин, имеющих нечётную степень. Докажем, что его можно покрыть <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> путей, которые являются простыми, так как рассматриваемый цикл эйлеров, и покрывают весь граф, поэтому полученное разбиение является искомым. | ||
}} | }} | ||
==См. также== | ==См. также== | ||
| − | [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов| | + | * [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеровость графов]] |
| + | |||
| + | ==Источники информации== | ||
| + | * Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6 | ||
| − | + | [[Категория: Алгоритмы и структуры данных]] | |
| − | + | [[Категория: Обходы графов]] | |
| + | [[Категория: Эйлеровы графы]] | ||
Текущая версия на 19:35, 4 сентября 2022
Следующее утверждение являются следствием из критерия Эйлеровости графа:
| Теорема: |
Пусть — связный граф, в котором вершин имеют нечётную степень. Тогда множество рёбер можно покрыть рёберно-простыми путями. |
| Доказательство: |
|
Рассмотрим связный граф который содержит вершин, имеющих нечётную степень. Докажем, что его можно покрыть рёберно-простыми путями. Добавим в граф рёбер, соединив попарно вершины, имеющие нечётные степени, и получим связный граф все вершины которого имеют чётную степень. Такой граф удовлетворяет критерию эйлеровости и содержит эйлеров цикл. Рассмотрим этот цикл и удалим из него добавленных ребер Цикл распадётся на путей, которые являются простыми, так как рассматриваемый цикл эйлеров, и покрывают весь граф, поэтому полученное разбиение является искомым. |
См. также
Источники информации
- Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
