Jump to content

Теорема о двух факторах

В математической дисциплине теории графов теорема о двух факторах , открытая Юлиусом Петерсеном , является одной из самых ранних работ по теории графов. Это можно сформулировать следующим образом: [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]

  1. ^ Jump up to: а б Ловас, Ласло; Пламмер, доктор медицины (2009), Теория соответствия , Американское математическое общество , ISBN  978-0-8218-4759-6 .
  2. ^ Малдер, Х. (1992), «Теория регулярных графов Юлиуса Петерсена», Discrete Mathematics , 100 : 157–175, doi : 10.1016/0012-365X(92)90639-W .
  3. ^ Лютцен, Дж.; Сабидусси, Г.; Тофт, Б. (1992), «Юлиус Петерсен 1839–1910, биография», Discrete Mathematics , 100 (1–3): 9–82, doi : 10.1016/0012-365X(92)90636-T .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 6e3126084cdda8c6ecaf7e1ef4a05552__1699458600
URL1:https://arc.ask3.ru/arc/aa/6e/52/6e3126084cdda8c6ecaf7e1ef4a05552.html
Заголовок, (Title) документа по адресу, URL1:
2-factor theorem - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)