Dopasowanie tęczy

W dyscyplinie matematycznej, jaką jest teoria grafów , dopasowanie tęczy na wykresie z kolorami krawędzi jest dopasowaniem , w którym wszystkie krawędzie mają różne kolory.

Definicja

Biorąc pod uwagę graf krawędziowy $G = (V, E)$ , tęcza pasująca do $M$ w $G$ jest zbiorem parami niesąsiadujących krawędzi, to znaczy żadne dwie krawędzie nie mają wspólnego wierzchołka, tak że wszystkie krawędzie w zestawie mają odrębne kolory.

Maksymalne dopasowanie tęczy to dopasowanie tęczy, które zawiera największą możliwą liczbę krawędzi.

Historia

U góry po lewej kwadrat łaciński , u dołu po lewej względna właściwa kolorystyka

n

- krawędzi . W prawym górnym rogu łaciński przekrój poprzeczny , aw prawym dolnym rogu względna pasująca tęcza .

Dopasowania tęczowe są szczególnie interesujące ze względu na ich związek z przekrojami kwadratów łacińskich .

Oznaczmy przez $K n, n$ pełny graf dwudzielny na $n + n$ wierzchołkach. Każde właściwe $n$ - krawędziowe kolorowanie K $rzędu n, n$ odpowiada kwadratowi łacińskiemu $n$ . Dopasowanie tęczowe odpowiada zatem poprzecznemu kwadratowi łacińskiemu, co oznacza wybór $n$ pozycji, po jednej w każdym rzędzie i każdej kolumnie, zawierających różne wpisy.

Ten związek między przekrojami kwadratów łacińskich i dopasowaniami tęczowymi w $K n, n$ zainspirował dodatkowe zainteresowanie badaniem dopasowań tęczowych w grafach bez trójkątów .

Istnienie, gdy każda krawędź ma jeden kolor

Kolorowanie krawędzi nazywamy właściwym , jeśli każda krawędź ma jeden kolor, a dwie krawędzie tego samego koloru nie mają wspólnego wierzchołka.

Właściwe zabarwienie krawędzi nie gwarantuje istnienia idealnego dopasowania tęczy. Rozważmy na przykład graf $K 2,2$ : kompletny graf dwudzielny na wierzchołkach 2+2. Załóżmy, że krawędzie $(x 1, y 1)$ i $(x 2, y 2)$ są koloru zielonego, a krawędzie $(x 1, y 2)$ i $(x 2, y 1)$ są koloru niebieskiego. Jest to prawidłowa kolorystyka, ale są tylko dwa idealne połączenia, a każde z nich jest zabarwione jednym kolorem. Rodzi to pytanie: kiedy istnieje gwarancja dopasowania dużej tęczy?

Granice zależne tylko od liczby wierzchołków

Wiele badań na ten temat zostało opublikowanych przy użyciu terminologii łacińskich przekrojów w kwadratach łacińskich . Przetłumaczone na tęczową terminologię:

$Kn W, n$ 1967 roku HJ Ryser wysunął przypuszczenie, że gdy $n$ jest nieparzyste , każde właściwe kolorowanie krawędzi ma tęczowe dopasowanie rozmiaru $n$ .
W 1975 roku SK Stein i Brualdi wysunęli hipotezę, że gdy $n$ jest parzyste , każde właściwe kolorowanie krawędzi $K n, n$ ma tęczowe dopasowanie rozmiaru $n - 1$ . (wiadomo, że tęczowe dopasowanie rozmiaru $n$ nie musi w tym przypadku istnieć).

Bardziej ogólne przypuszczenie Steina jest takie, że dopasowanie tęczy o rozmiarze $n - 1$ istnieje nie tylko dla prawidłowego pokolorowania krawędzi, ale dla każdego pokolorowania, w którym każdy kolor pojawia się dokładnie na $n$ krawędziach.

Udowodniono kilka słabszych wersji tych przypuszczeń:

Każde właściwe kolorowanie krawędzi $K n, n$ ma tęczowe dopasowanie rozmiaru $2 n /3$ .
Każde właściwe kolorowanie krawędzi $K n, n$ ma tęczowe dopasowanie rozmiaru ${\ displaystyle n- {\ sqrt {n}}.}$
Każde właściwe kolorowanie krawędzi $K n, n$ ma tęczowe dopasowanie rozmiaru $n - 11 log 22 (n)$ .

Granice w zależności od stopnia minimalnego

Wang zapytał, czy istnieje funkcja $f (d)$ taka, że każdy odpowiednio pokolorowany krawędziowo wykres $G$ o minimalnym stopniu $d$ i co najmniej $f (d)$ wierzchołkach musi mieć tęczowe dopasowanie rozmiaru $d$ . Oczywiście potrzebne są co najmniej $2 d$ wierzchołki, ale ile jest wystarczających?

Diemunsch i in. odpowiedział twierdząco na to pytanie i wykazał, że przy odpowiednio pokolorowanym krawędziami grafie $G$ o minimalnym stopniu $d$ i rzędzie co najmniej $f (d) = 98δ/23$ , istnieje tęczowe dopasowanie rozmiaru $d$ w $G$ .
Ta granica została później poprawiona do $f (d) = 4 d - 3$ przez Andrasa Gyarfasa i Gabora N. Sarkozy'ego. Pokazują również, że każdy graf z co najmniej $2 d$ wierzchołkami ma tęczowe dopasowanie o rozmiarze co najmniej $d - 2 d 2/3$ . Są to najbardziej znane szacunki do tej pory.

Istnienie, gdy ta sama krawędź może mieć różne kolory

Załóżmy, że każda krawędź może mieć kilka różnych kolorów, podczas gdy dwie krawędzie tego samego koloru nadal nie mogą mieć wspólnego wierzchołka. Innymi słowy, każdy kolor jest dopasowany . Ile kolorów jest potrzebnych, aby zagwarantować istnienie dopasowania tęczy?

W pełnych grafach dwudzielnych

Drisko przestudiował to pytanie, posługując się terminologią łacińskich prostokątów . Udowodnił, że dla dowolnego $n \leq k$ , w pełnym grafie dwudzielnym $Kn ma, k$ , każda rodzina $2 n - 1$ dopasowań (=kolorów) o rozmiarze $n$ idealne dopasowanie tęczowe (o rozmiarze $n$ ). Zastosował to twierdzenie do pytań dotyczących działań grupowych i zbiorów różnic .

Drisko pokazał również, że może być konieczne $2 n - 1$ dopasowań: rozważmy rodzinę $2 n - 2$ dopasowań, z których $n - 1$ to ${ (x 1, y 1), (x 2, y 2), ..., (x n, y n)}$ a pozostałe $n - 1$ to ${(x 1, y 2), (x 2, y 3), \dots, (x n, y 1) }.$ Wtedy największe dopasowanie tęczy ma rozmiar $n - 1$ (np. weź jedną krawędź z każdego z pierwszych $n - 1$ dopasowań).

Alon wykazał, że twierdzenie Drisko implikuje starszy wynik w addytywnej teorii liczb .

Ogólnie grafy dwudzielne

Aharoni i Berger uogólnili twierdzenie Drisko na dowolny graf dwudzielny, a mianowicie: każda rodzina $2 n - 1$ dopasowań o rozmiarze $n$ na grafie dwudzielnym ma tęczowe dopasowanie o rozmiarze $n$ .

Aharoni, Kotlar i Ziv wykazali, że ekstremalny przykład Drisko jest wyjątkowy w każdym grafie dwudzielnym.

Ogólnie wykresy

Ogólnie rzecz biorąc, wykresy $2 n - 1$ dopasowań nie są już wystarczające. Kiedy $n$ jest parzyste, można dodać do przykładu Drisko dopasowanie ${ (x 1, x 2), (y 1, y 2), (x 2, x 3), (y 2, y 3), \dots }$ i otrzymać rodzina $2 n - 1$ dopasowań bez żadnych tęczowych dopasowań.

Aharoni, Berger, Chudnovsky, Howard i Seymour udowodnili, że na ogólnym wykresie $3 n - 2$ dopasowania (=kolory) są zawsze wystarczające. Nie wiadomo, czy jest to ciasne: obecnie najlepsza dolna granica dla parzystego $n$ to $2 n$ , a dla nieparzystego $n$ to $2 n - 1$ .

Tęczowe dopasowania ułamkowe

Dopasowanie ułamkowe to zestaw krawędzi z nieujemną wagą przypisaną każdej krawędzi, tak że suma wag przylegających do każdego wierzchołka wynosi co najwyżej 1. Rozmiar dopasowania ułamkowego to suma wag wszystkich krawędzi. Jest to uogólnienie dopasowania i może być użyte do uogólnienia zarówno kolorów, jak i dopasowania tęczy:

Zamiast wymagać, aby każdy kolor był dopasowany do rozmiaru $n$ , wymaganie jest osłabione: każdy „kolor” może być dowolnym zestawem krawędzi, ale powinien dopuszczać ułamkowe dopasowanie rozmiaru co najmniej $n$ .
Zamiast szukać dopasowania tęczowego, szukamy dopasowania ułamkowego tęczy — dopasowania ułamkowego, w którym każda krawędź o dodatniej wadze ma inny kolor.

Wiadomo, że w grafie dwudzielnym maksymalny rozmiar dopasowania ułamkowego jest równy maksymalnemu rozmiarowi dopasowania. Dlatego twierdzenie Aharoniego i Bergera jest równoważne następującemu. Niech $n$ będzie dowolną dodatnią liczbą całkowitą. Biorąc pod uwagę dowolną rodzinę $2 n - 1$ dopasowań ułamkowych (= kolorów) o rozmiarze $n$ na grafie dwudzielnym, istnieje tęczowe dopasowanie ułamkowe o rozmiarze $n$ .

Aharoni, Holzman i Jiang rozszerzają to twierdzenie na dowolne wykresy w następujący sposób. Niech $n$ będzie dowolną dodatnią liczbą całkowitą lub pół-całkowitą. Każda rodzina $2 n$ dopasowań ułamkowych (=kolorów) o rozmiarze co najmniej $n$ na dowolnym grafie ma tęczowe dopasowanie ułamkowe o rozmiarze $n$ . 2 $. n$ jest najmniejszym możliwym dopasowaniem ułamkowym na dowolnych wykresach: przypadek ekstremalny jest konstruowany przy użyciu cyklu o nieparzystej długości

Częściowy dowód

W przypadku doskonałych dopasowań ułamkowych oba powyższe twierdzenia można wyprowadzić z kolorowego twierdzenia Caratheodory'ego .

Dla każdej krawędzi $e$ w $E$ niech $1 e$ będzie wektorem o rozmiarze $| V |$ , gdzie dla każdego wierzchołka $v$ w $V$ , element $v$ w $1 e$ jest równy 1, jeśli $e$ sąsiaduje z $v$ , a 0 w przeciwnym razie (więc każdy wektor $1 e$ ma 2 jedynki i $| V |$ -2 zera). Każde dopasowanie ułamkowe odpowiada kombinacji stożkowej krawędzi, w których każdy element ma co najwyżej 1. Kombinacja stożkowa, w której każdy element ma dokładnie 1, odpowiada doskonałemu dopasowaniu ułamkowemu. Innymi słowy, zbiór $F$ krawędzi dopuszcza doskonałe dopasowanie ułamkowe wtedy i tylko wtedy, gdy $1 v$ (wektor $| V |$ jedynek) jest zawarty w stożkowej otoczce wektorów $1 e$ dla $e$ w $F$ .

Rozważmy graf z $2 n$ wierzchołkami i załóżmy, że istnieje $2 n$ podzbiorów krawędzi, z których każdy dopuszcza idealne dopasowanie ułamkowe (o rozmiarze $n$ ). Oznacza to, że wektor $1 v$ znajduje się w otoczce stożkowej każdego z tych $n$ podzbiorów. Zgodnie z kolorowym twierdzeniem Caratheodory'ego istnieje wybór $2 n$ krawędzi, po jednej z każdego podzbioru, których stożkowy kadłub zawiera $1 v$ . Odpowiada to doskonałemu dopasowaniu ułamkowemu tęczy. Ekspresja $2 n$ to wymiar wektorów $1 e$ - każdy wektor ma $2 n$ elementów.

Załóżmy teraz, że graf jest dwudzielny. W grafie dwudzielnym istnieje ograniczenie dotyczące wektorów $1 e$ : suma elementów odpowiadających każdej części grafu musi wynosić 1. Zatem wektory $1 e$ żyją w $(2 n - 1)$ -wymiarowej przestrzeni. Dlatego ten sam argument, co powyżej, obowiązuje, gdy istnieją tylko $2 n - 1$ podzbiory krawędzi.

Dopasowywanie tęczy w hipergrafach

Hipergraf r-jednolity r to zbiór hipergrafów, z których każdy zawiera dokładnie $wierzchołków$ (tak więc hipergraf 2-jednolity jest po prostu grafem bez pętli własnych). Aharoni, Holzman i Jiang rozszerzają swoje twierdzenie na takie hipergrafy w następujący sposób. Niech $n$ będzie dowolną dodatnią liczbą wymierną. Każda rodzina $⌈ r \cdot n ⌉$ dopasowań ułamkowych (= kolorów) o rozmiarze co najmniej $n$ w $r$ -jednolitym hipergrafie ma tęczowe dopasowanie ułamkowe o rozmiarze $n$ . ⌈ $r \cdot _n ⌉$ jest najmniejszą możliwą liczbą, gdy $n$ jest liczbą całkowitą.

Hipergraf r-częściowy to hipergraf $r$ -jednolity, w którym wierzchołki są podzielone na $r$ zbiorów rozłącznych, a każda hipergraf zawiera dokładnie jeden wierzchołek z każdego zbioru (tak więc hipergraf dwuczęściowy jest grafem po prostu dwudzielnym). Niech $n$ będzie dowolną dodatnią liczbą całkowitą. Każda rodzina $rn - r + 1$ dopasowań ułamkowych (=kolorów) o rozmiarze co najmniej $n$ w hipergrafie $r$ -częściowym ma tęczowe dopasowanie ułamkowe o rozmiarze $n$ . rn $- r_+ 1$ jest najmniejszym możliwym: skrajnym przypadkiem jest sytuacja, gdy $n = r - 1$ jest potęgą pierwszą , a wszystkie kolory są krawędziami ściętej rzutowej płaszczyzny rzędu $n$ . Tak więc każdy kolor ma $n 2 = rn - r + 1$ krawędzi i ułamkowe dopasowanie rozmiaru $n$ , ale każde ułamkowe dopasowanie tego rozmiaru wymaga wszystkich $rn - r + 1$ krawędzi.

Częściowy dowód

W przypadku doskonałych dopasowań ułamkowych oba powyższe twierdzenia można wyprowadzić z twierdzenia o barwnej karateodorii z poprzedniej sekcji. Dla ogólnego $r$ -jednostajnego (dopuszczającego idealne dopasowanie rozmiaru $n$ ), wektory $1 e$ żyją w $(rn)$ -wymiarowej przestrzeni. Dla $r$ -jednolitego $r$ -częściowego, ograniczenia $r$ -częściowości implikują, że wektory $1 e$ żyją w a $(rn - r + 1)$ -przestrzeń wymiarowa.

Notatki

Powyższe wyniki dotyczą tylko tęczowych dopasowań ułamkowych . W przeciwieństwie do tego przypadek tęczowych całkowych w $r$ -jednolitych hipergrafach jest znacznie mniej zrozumiały. Liczba wymaganych dopasowań dla tęczowego dopasowania rozmiaru $n$ rośnie co najmniej wykładniczo wraz z $n$ .

Obliczenie

Garey i Johnson wykazali, że obliczenie maksymalnego dopasowania tęczy jest NP-zupełne nawet dla grafów dwudzielnych z kolorowymi krawędziami .

Aplikacje

Tęczowe dopasowania zostały zastosowane do rozwiązywania problemów z pakowaniem .

Zobacz też