Graf Mycielskiego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

W teorii grafów graf Mycielskiego lub Mycielskian nieskierowanego grafu G jest to graf μ(G) stworzony dzięki konstrukcji podanej przez Jana Mycielskiego w roku 1955, pokazującej istnienie grafu, w którym największa klika ma rozmiar ≤ 2, o bezwzględnie dużej liczbie chromatycznej.

Uogólniona wersja konstrukcji została przedstawiona przez Wensonga Lin w roku 2006.

Konstrukcja[edytuj | edytuj kod]

Niech n wierzchołków grafu G będzie oznaczonych v0, v1, ..., vn−1. Graf Mycielskiego μ(G) zawiera graf G jako izomorficzny podgraf oraz n+1 dodatkowych wierzchołków: ui odpowiadające wierzchołkom vi oraz wierzchołek w. Każdy wierzchołek ui jest połączony krawędzią z wierzchołkiem w tak, że tworzą one razem podgraf przypominający gwiazdę o n+1 wierzchołkach. Dodatkowo, dla każdej krawędzi vivj w ramach konstrukcji dodawane są krawędzie uivj oraz viuj.

Dla grafu G o n wierzchołkach i m krawędzich powstaje graf μ(G) o 2n+1 wierzchołkach i 3m+n krawędziach.

Przykłady[edytuj | edytuj kod]

Ilustracja przedstawia konstrukcję grafu Mycielskiego zastosowana dla grafu cyklicznego o 5 wierzchołkach. Powstały graf jest nazywany grafem Grötzscha, ma 11 wierzchołków i 20 krawędzi. Jest to najmniejszy graf w którym największa klika ma rozmiar ≤ 2 o liczbie chromatycznej równej 4.

Iterowane grafy Mycielskiego[edytuj | edytuj kod]

Grafy Mycielskiego M2, M3 oraz M4

Stosując konstrukcję Mycielskiego, zaczynając od grafu zerowego można otrzymać sekwencję Mi = μ(Mi-1), nazywaną czasami grafami Mycielskiego. Kilka pierwszych grafów otrzymanych w ten sposób to: graf zerowy, graf M1 z jednym wierzchołkiem i bez krawędzi, graf M2 = K2 z dwoma wierzchołkami połączonymi krawędzią, graf M3 = C5 oraz graf Grötzscha z 11 wierzchołkami i 20 krawędziami.

Ogólnie, dla grafu Mi należącego do sekwencji nie istnieje klika o rozmiarze > 2, usunięcie mniej niż i-1 wierzchołków nie powoduje utraty spójności grafu, jest on także i-kolorowalny. Mi ma 3 × 2i-2 - 1 wierzchołków (Sekwencja A083329 w OEIS). Ilość krawędzi dla grafu Mi przy początkowych wartościach i to:

0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... (Sekwencja A122695 w OEIS)

Własności[edytuj | edytuj kod]

Cykl Hamiltona w grafie M4 (graf Grötzscha)
  • Jeśli graf G ma liczbę chromatyczną równą k, to μ(G) ma liczbę chromatyczną równą k+1 (Mycielski 1955).

Dowód Niech  c : μ(G) → C  będzie minimalnym pokolorowaniem, tzn. obraz c(μ(G)) ma moc równą liczbie chromatycznej grafu Mycielskiego μ(G), czyli

| c(μ(G)) |  =  χ(μ(G)).

(zgodnie z definicją pokolorowania grafu, wierzchołki sąsiednie różnią się kolorem).

Pokażmy, że χ(μ(G)) > χ(G):  w przeciwnym wypadku wszystkie kolory c(u i) (0 ≤ i < n), a także kolor c(w), występują wśród kolorów c(v i) (0 ≤ i < n). Ale kolor c(w) nie występuje wśród c(u i). Zdefiniujmy pokolorowanie d grafu  G  jak następuje:

d(v i)  :=  c(v i)     gdy c(v i) ≠ c(w)
d(v i)  :=  c(u i)     gdy c(v i) = c(w)

dla  i = 0, ..., n-1. Pokolorowanie d, grafu G, użyło nie więcej niż χ(G) - 1 kolorów – sprzeczność. Udowodniliśmy więc, że

χ(μ(G))  >  χ(G).

Niech teraz  d : G → D  będzie minimalnym pokolorowaniem grafu G. Zdefiniujmy:

c(v i)  :=  d(v i)
c(u i)  :=  d(v i)

dla i = 0, ..., n-1. Ponadto niech kolor c(w) nie należy do D. Wtedy c jest pokolorowaniem grafu Mycielskiego, które użyło tylko jednego koloru spoza D. Udowodniliśmy więc, że

χ(μ(G))  ≤  χ(G) + 1,

co w połączeniu z poprzednią nierównością (odwrotną) kończy dowód.

  • Jeśli największa klika w grafie G  ma rozmiar ≤ 2, to taką samą własność ma graf μ(G). Co więcej, wszystkie kliki rozmiaru > 2 w grafie μ(G) są zawarte w grafie G, o ile takie kliki w ogóle istnieją. (Mycielski 1955).

(Dowód tej własności jest prosty).

  • Jeśli graf G posiada cykl Hamiltona, to graf μ(G) także go posiada (Fisher 1998).

Bibliografia[edytuj | edytuj kod]

Na podstawie angielskiej Wikipedii:

  • Chvátal, Vašek (1974). "The minimality of the Mycielski graph". Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), 243–246, Berlin: Lecture Notes in Mathematics, Vol. 406, Springer-Verlag.
  • Došlić, Tomislav (2005). "Mycielskians and matchings". Discuss. Math. Graph Theory 25 (3): 261–266.
  • Fisher, David C.; McKenna, Patricia A.; Boyer, Elizabeth D. (1998). "Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski's graphs". Discrete Applied Mathematics 84 (1–3): 93–105.
  • Lin, Wensong; Wu, Jianzhuan; Lam, Peter Che Bor; Gu, Guohua (2006). "Several parameters of generalized Mycielskians". Discrete Applied Mathematics 154 (8): 1173–1182.

Linki zewnętrzne[edytuj | edytuj kod]