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