Покрытие рёбер графа путями — различия между версиями
(→См. также) |
(→Покрытие ребер графа путями) |
||
| Строка 1: | Строка 1: | ||
==Покрытие ребер графа путями== | ==Покрытие ребер графа путями== | ||
Следующее утверждение являются следствием из [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|критерия Эйлеровости]] [[Основные определения теории графов|графа]]: | Следующее утверждение являются следствием из [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|критерия Эйлеровости]] [[Основные определения теории графов|графа]]: | ||
| − | + | {{Утверждение|statement= | |
| − | Пусть < | + | Пусть <tex>G</tex> - [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов#cite_note-almost-0|почти связный]] граф, в котором <tex>2N</tex> вершин имеют нечетную [[Основные определения теории графов|степень]]. Тогда множество ребер <tex>G</tex> можно покрыть <tex>N</tex> реберно простыми путями. |
| + | }} | ||
==См. также== | ==См. также== | ||
Версия 23:34, 13 октября 2010
Покрытие ребер графа путями
Следующее утверждение являются следствием из критерия Эйлеровости графа:
| Утверждение: |
Пусть - почти связный граф, в котором вершин имеют нечетную степень. Тогда множество ребер можно покрыть реберно простыми путями. |
См. также
Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
Источники
1. Ф.Харари. Теория графов. Москва, издательство "Едиториал УРСС". 2003 г.
