Twierdzenie o 2 czynnikach

W matematycznej dyscyplinie teorii grafów , twierdzenie o 2 czynnikach , odkryte przez Juliusa Petersena , jest jednym z najwcześniejszych dzieł w teorii grafów. Można to stwierdzić następująco:

Twierdzenie o 2 czynnikach . Niech G będzie grafem regularnym , którego stopień jest liczbą parzystą, 2 k . Następnie krawędzie G można podzielić na k 2-czynników rozłącznych krawędzi.

Tutaj współczynnik 2 jest podgrafem G , w którym wszystkie wierzchołki mają stopień drugi; to znaczy jest to zbiór cykli, które razem dotykają każdego wierzchołka dokładnie raz.

Dowód

Aby udowodnić tę uogólnioną postać twierdzenia, Petersen najpierw udowodnił, że graf 4-regularny można rozłożyć na dwa czynniki 2-czynnikowe, biorąc naprzemienne krawędzie śladu Eulera. Zauważył, że ta sama technika zastosowana dla wykresu 4-regularnego daje faktoryzację wykresu 2- k -regularnego na dwa k -czynniki.

Aby udowodnić to twierdzenie, wystarczy rozważyć grafy połączone. Spójny graf o parzystym stopniu ma ślad Eulera. Przemierzanie tego szlaku Eulera generuje orientację D z G taką, że każdy punkt ma stopień wejściowy i zewnętrzny = k . Następnie zastąp każdy wierzchołek v ϵ V ( D ) dwoma wierzchołkami v' i v” oraz każdą krawędź skierowaną uv grafu zorientowanego zastąp krawędzią nieskierowaną od u' do v” . Ponieważ D ma stopień wejściowy i wyjściowy równy k , wynikowy graf dwudzielny G' jest k -regularny. Krawędzie G' można podzielić na k doskonałych dopasowań za pomocą twierdzenia Kőniga . Teraz scalając v' z v” dla każdego v odzyskujemy graf G i odwzorowujemy k doskonałych dopasowań G' na k 2-czynników G , które dzielą jego krawędzie. ^[1]

Historia

Twierdzenie zostało odkryte przez duńskiego matematyka Juliusa Petersena . W rzeczywistości jest to jeden z pierwszych wyników w teorii grafów . Twierdzenie to pojawia się po raz pierwszy w artykule z 1891 r. „Die Theorie der regulären graphs” . Aby udowodnić twierdzenie, podstawową ideą Petersena było „pokolorowanie” krawędzi próby lub ścieżki na przemian na czerwono i niebiesko, a następnie wykorzystanie krawędzi jednego lub obu kolorów do budowy innych ścieżek lub prób.