Теорема Веблена - Википедия - Veblens theorem

В математике Теорема Веблена, представлен Освальд Веблен (1912 ), утверждает, что множество ребер конечного графа можно записать как объединение непересекающихся простые циклы тогда и только тогда, когда каждая вершина имеет четную степень. Таким образом, он тесно связан с теоремой Эйлер (1736) что конечный граф имеет Эйлер тур (один непростой цикл, покрывающий ребра графа) тогда и только тогда, когда он связаны и каждая вершина имеет четную степень. Действительно, представление графа в виде объединения простых циклов может быть получено из эйлерова тура путем многократного разбиения тура на меньшие циклы всякий раз, когда есть повторяющаяся вершина. Однако теорема Веблена применима также к несвязным графам и может быть обобщена на бесконечные графы в котором каждая вершина имеет конечную степень (Сабидусси 1964 ).

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

Теорема Веблена - Википедия - Veblens theorem

Смотрите также

Рекомендации