Теорема о двух факторах
В математической дисциплине теории графов теорема о двух факторах , открытая Юлиусом Петерсеном , является одной из самых ранних работ по теории графов. Это можно сформулировать следующим образом: [1]
Пусть G — регулярный граф которого , степень равна четному числу 2 k . Тогда ребра G можно разбить на k непересекающихся по ребрам 2-факторов.
Здесь 2-фактор — это подграф G , все вершины которого имеют степень два; то есть это набор циклов, которые вместе касаются каждой вершины ровно один раз.
Доказательство
[ редактировать ]Чтобы доказать эту обобщенную форму теоремы, Петерсен сначала доказал, что 4-регулярный граф можно разложить на два 2-фактора, взяв чередующиеся ребра в эйлеровом следе. Он отметил, что тот же метод, который использовался для 4-регулярного графа, дает факторизацию 2k - регулярного графа на два k -фактора. [2]
Для доказательства этой теоремы достаточно рассмотреть связные графы. Связный граф четной степени имеет эйлеров след. Обход этого эйлерова следа генерирует ориентацию D группы G такую, что каждая точка имеет степень входа и выхода = k . Затем замените каждую вершину v ϵ V ( D ) двумя вершинами v' и v” и замените каждое направленное ребро uv ориентированного графа неориентированным ребром из u' в v” . Поскольку D имеет входную и выходную степени, равные k, полученный двудольный граф G' будет k -регулярным. Ребра G' можно разбить на k совершенных паросочетаний по теореме Кенига . Теперь слияние v' с v” для каждого v восстанавливает граф G и отображает k совершенных паросочетаний G' на k 2-факторов G , которые разбивают его ребра. [1]
История
[ редактировать ]Теорему открыл Юлиус Петерсен , датский математик. Это один из первых результатов, когда-либо открытых в области теории графов . Теорема впервые появляется в статье 1891 года «Теория регулярных графов» . Основная идея Петерсена для доказательства теоремы заключалась в том, чтобы «окрасить» края следа или пути поочередно в красный и синий цвета, а затем использовать края одного или обоих цветов для построения других путей или испытаний. [3]
Ссылки
[ редактировать ]- ^ Jump up to: а б Ловас, Ласло; Пламмер, доктор медицины (2009), Теория соответствия , Американское математическое общество , ISBN 978-0-8218-4759-6 .
- ^ Малдер, Х. (1992), «Теория регулярных графов Юлиуса Петерсена», Discrete Mathematics , 100 : 157–175, doi : 10.1016/0012-365X(92)90639-W .
- ^ Лютцен, Дж.; Сабидусси, Г.; Тофт, Б. (1992), «Юлиус Петерсен 1839–1910, биография», Discrete Mathematics , 100 (1–3): 9–82, doi : 10.1016/0012-365X(92)90636-T .