В математике теорема Веблена , введенная Освальдом Вебленом ( 1912 ), утверждает, что множество ребер конечного графа может быть записано как объединение непересекающихся простых циклов тогда и только тогда, когда каждая вершина имеет четную степень. Таким образом, это тесно связано с теоремой Эйлера (1736 г.) о том, что конечный граф имеет эйлеров тур (единственный непростой цикл, покрывающий ребра графа) тогда и только тогда, когда он связани каждая вершина имеет четную степень. В самом деле, представление графа в виде объединения простых циклов может быть получено из эйлерова тура путем многократного разбиения тура на меньшие циклы всякий раз, когда есть повторяющаяся вершина. Однако теорема Веблена применима также к несвязным графам и может быть обобщена на бесконечные графы, в которых каждая вершина имеет конечную степень ( Sabidussi 1964 ).
Если счетно бесконечный граф G не имеет вершин нечетной степени, то он может быть записан как объединение непересекающихся (конечных) простых циклов тогда и только тогда, когда каждый конечный подграф G может быть расширен (добавлением большего количества ребер и вершин G ) к конечному эйлерову графу. В частности, любой счетный граф с одним концом и без нечетных вершин может быть записан как объединение непересекающихся циклов ( Sabidussi 1964 ).
Смотрите также
Рекомендации
- Эйлер, Л. (1736 г.), «Решение проблем с геометрией, подходящее место» (PDF) , Комментарии Academiae Scientiarum Imperialis Petropolitanae , 8 : 128–140. Перепечатано и переведено на Биггс, Нидерланды; Ллойд, EK; Уилсон, Р.Дж. (1976), Теория графов 1736–1936 , Oxford University Press.
- Сабидусся, Герт (1964), "Бесконечный Эйлер графы", Canadian Journal математики , 16 : 821-838, DOI : 10,4153 / CJM-1964-078-х , МР 0169236.
- Веблен, Освальд (1912), "Применение модульных уравнений в анализе Situs", Анналы математики , вторая серия 14 (1): 86-94, DOI : 10,2307 / 1967604 , JSTOR 1967604