WikiSort.ru - Не сортированное

В математике теорема Веблена, доказанная Вебленом^[1], утверждает, что множество рёбер конечного графа можно представить в виде объединения непересекающихся простых циклов в том и только в том случае, когда любая вершина имеет чётную степень. Таким образом, эта теорема тесно связана с теоремой Эйлера^[2], о том, что конечный граф имеет эйлеров цикл (единичный, не обязательно простой, цикл, покрывающий все рёбра графа) в том и только в том случае, когда граф связен и любая вершина имеет чётную степень. Более того, представление графа в виде объединения простых циклов можно получить из эйлерового цикла путём повторяющегося деления обхода на более мелкие циклы в случае присутствия в цикле повторяющейся вершины. Однако теорема Веблена справедлива и для несвязных графов и может быть обобщена на бесконечные графы, в которых каждая вершина имеет конечную степень^[3].

Если в счётном бесконечном графе G нет вершин с нечётной степенью, он может быть представлен в виде объединения непересекающихся (конечных) простых циклов в том и только в том случае, если любой конечный подграф можно расширить (путём добавления рёбер и вершин из графа G) до эйлерового графа. В частности, любой счётный бесконечный граф с единственным концом^[en], не имеющий вершин нечётной степени, может быть представлен как объединение непересекающихся циклов^[3].

См. также

• База циклов
• Гипотеза о двойном покрытии циклами
• Эйлеров матроид^[en]

Примечания

Ссылки

• L. Euler. Solutio problematis ad geometriam situs pertinentis // Commentarii Academiae Scientiarum Imperialis Petropolitanae. — 1736. — Т. 8. — С. 128—140.
• N. L. Biggs, E. K. Lloyd, R. J. Wilson. Graph Theory 1736–1936. — Oxford University Press, 1976.
• Gert Sabidussi. Infinite Euler graphs // Canadian Journal of Mathematics. — 1964. — Т. 16. — С. 821—838. — DOI:10.4153/CJM-1964-078-x.
• Oswald Veblen. An Application of Modular Equations in Analysis Situs // Annals of Mathematics. — 1912. — Т. 14, вып. 1. — С. 86—94.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка.