Faktoryzacja grafów

Nie mylić z wykresem czynnikowym .
1-faktoryzacja wykresu Desarguesa : każda klasa kolorów jest 1-czynnikiem.
Wykres Petersena można podzielić na 1-czynnikowy (czerwony) i 2-czynnikowy (niebieski). Jednak wykres nie jest 1-czynnikowy.

W teorii grafów czynnikiem grafu G jest podgraf rozpinający , tj. podgraf, który ma ten sam zestaw wierzchołków co G. Współczynnik k na grafu jest obejmującym k - regularnym podgrafem, a rozkład czynniki k dzieli krawędzie grafu na rozłączne współczynniki k . O grafie G mówi się, że jest k -czynnikowy, jeśli dopuszcza k -faktoryzację. W szczególności 1-czynnik jest idealnym dopasowaniem , a 1-faktoryzacja wykresu k - regularnego to kolorowanie krawędzi za pomocą k kolorów. Współczynnik 2 to zbiór cykli obejmujący wszystkie wierzchołki grafu.

1-faktoryzacja

Jeśli graf jest 1-czynnikowy (tj. ma 1-czynnikowy), to musi być grafem regularnym . Jednak nie wszystkie regularne wykresy są 1-czynnikowe. Wykres k -regularny jest 1-czynnikowy, jeśli ma indeks chromatyczny k ; przykłady takich wykresów obejmują:

Jednak istnieją również grafy k -regularne, które mają indeks chromatyczny k + 1, a wykresy te nie są 1-czynnikowe; przykłady takich wykresów obejmują:

  • Dowolny graf regularny z nieparzystą liczbą węzłów.
  • Wykres Petersena .

Kompletne wykresy

1-faktoryzacja K 8 , w której każdy 1-czynnik składa się z krawędzi od środka do wierzchołka siedmiokąta wraz ze wszystkimi możliwymi prostopadłymi krawędziami

Rozkład na czynniki 1 kompletnego wykresu odpowiada parom w turnieju kołowym . Rozkład na czynniki 1 grafów pełnych jest szczególnym przypadkiem twierdzenia Baranyai dotyczącego rozkładu grafów pełnych na czynniki 1 .

Jedna metoda konstruowania rozkładu na czynniki 1 pełnego wykresu na parzystej liczbie wierzchołków polega na umieszczeniu wszystkich wierzchołków oprócz jednego na okręgu, tworząc regularny wielokąt , z pozostałym wierzchołkiem w środku koła. Przy takim układzie wierzchołków jednym ze sposobów konstruowania współczynnika 1 grafu jest wybranie krawędzi e od środka do pojedynczego wierzchołka wielokąta wraz ze wszystkimi możliwymi krawędziami leżącymi na liniach prostopadłych do e . Czynniki 1, które można skonstruować w ten sposób, tworzą 1-faktoryzację wykresu.

Liczba odrębnych 1-czynników K 2 , K 4 , K 6 , K 8 , ... wynosi 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... OEIS : A00043 8 .

Przypuszczenie 1-faktoryzacji

Niech G będzie grafem k -regularnym o 2 n węzłach. Jeśli k jest wystarczająco duże, wiadomo, że G musi być 1-czynnikowe:

  • Jeśli k = 2 n − 1, to G jest pełnym wykresem K 2 n , a więc 1-czynnikowym (patrz wyżej ).
  • Jeśli k = 2 n − 2, to G można skonstruować usuwając idealne dopasowanie z K 2 n . Ponownie, G jest 1-czynnikowe.
  • Chetwynd i Hilton (1985) pokazują, że jeśli k ≥ 12n/7, to G jest 1-czynnikiem.

Hipoteza 1-faktoryzacji jest długoletnią hipotezą , która stwierdza, że ​​​​k ≈ n jest wystarczające. Mówiąc dokładniej, przypuszczenie jest następujące:

  • Jeśli n jest nieparzyste i k ≥ n , to G jest 1-czynnikiem. Jeśli n jest parzyste i k ≥ n - 1, to G jest 1-czynnikowe.

Hipoteza przepełnienia implikuje hipotezę 1-faktoryzacji.

Doskonała 1-faktoryzacja

Idealna para z 1-faktoryzacji to para 1-czynników, których suma indukuje cykl Hamiltona .

Doskonały rozkład na czynniki 1 (P1F) wykresu to rozkład na czynniki 1, którego właściwość polega na tym, że każda para współczynników 1 jest parą doskonałą. Doskonałego 1-czynnika nie należy mylić z idealnym dopasowaniem (zwanym również 1-czynnikiem).

W 1964 roku Anton Kotzig wysunął przypuszczenie, że każdy kompletny graf K 2 n , gdzie n ≥ 2 ma doskonały rozkład na czynniki 1. Jak dotąd wiadomo, że następujące wykresy mają idealny rozkład na czynniki 1:

  • nieskończona rodzina pełnych grafów K 2 p , gdzie p jest nieparzystą liczbą pierwszą (niezależnie od Andersona i Nakamury),
  • nieskończona rodzina pełnych grafów K p + 1 , gdzie p jest nieparzystą liczbą pierwszą,
  • i sporadyczne wyniki dodatkowe, w tym K 2 n gdzie 2 n ∈ {16, 28, 36, 40, 50, 126, 170, 244, 344, 730, 1332, 1370, 1850, 2198, 3126, 6860, 12168, 16808, 29792}. Niektóre nowsze wyniki są zebrane tutaj .

Jeśli pełny graf K n + 1 ma doskonały rozkład na czynniki 1, to pełny graf dwudzielny K n , n również ma doskonały rozkład na czynniki 1.

2-faktoryzacja

Jeśli wykres jest 2-czynnikowy, to musi być 2 k -regularny dla pewnej liczby całkowitej k . Julius Petersen wykazał w 1891 r., że ten warunek konieczny jest również wystarczający: każdy graf regularny 2 k jest dwuczynnikowy.

Jeśli połączony graf jest 2 k -regularny i ma parzystą liczbę krawędzi, można go również rozłożyć na współczynnik k , wybierając każdy z dwóch czynników jako naprzemienny podzbiór krawędzi trasy Eulera . Dotyczy to tylko połączonych grafów; rozłączone kontrprzykłady obejmują rozłączne związki nieparzystych cykli lub kopii K 2 k +1 .

Problem Oberwolfacha dotyczy istnienia dwuczynnikowości grafów pełnych na podgrafy izomorficzne. Pyta, dla których podgrafów jest to możliwe. Jest to znane, gdy podgraf jest spójny (w takim przypadku jest to cykl Hamiltona , a tym szczególnym przypadkiem jest problem rozkładu Hamiltona ), ale przypadek ogólny pozostaje nierozwiązany.

Bibliografia

Dalsza lektura

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Graph_factorization&oldid=1139318466 ”