Delta 8/2024

Ile jest grafów?

Adam Gregosiewicz

matematyka kombinatoryka rachunek prawdopodobieństwa teoria grafów teoria mnogości

Errata do wersji w druku: Na dole strony 4 pojawia się zdanie „Jeśli takich permutacji jest dokładnie $n!,$ to o grafie $G$ mówimy, że jest asymetryczny” , które powinno brzmieć: „Jeśli tylko permutacja identycznościowa prowadzi do grafu izomorficznego z grafem $G$ , to mówimy, że jest on asymetryczny”,

Dużo. A nawet nieskończenie wiele! Taka odpowiedź nie jest zbyt ciekawa, więc spróbujmy zadać pytanie bardziej konkretne. Może: ile jest grafów o $n$ wierzchołkach? W tym przypadku odpowiedź nie jest być może zupełnie oczywista, ale ciągle mało interesująca. Różnych par wierzchołków jest tyle samo co wszystkich dwuelementowych podzbiorów zbioru $n$ -elementowego, czyli $(\binom{n}{2})$ . Ponieważ każda taka para może być lub nie być połączona krawędzią, więc grafów jest $2^{(\binom{n}{2})}$ . Mamy jednak świadomość, że pewne z tych grafów są w zasadzie identyczne – różnią się tylko etykietami, które nadaliśmy wierzchołkom. Na przykład dla $n = 4$ grafy

mają inne zbiory krawędzi, ale tak naprawdę są jednakowe. Wystarczy bowiem w pierwszym grafie zmienić numerację wierzchołków: $v_{1} \to v_{2}$ , $v_{2} \to v_{3}$ , $v_{3} \to v_{4}$ , $v_{4} \to v_{1}$ . Takich grafów nie chcemy zliczać osobno.

Powinniśmy w jakiś sposób utożsamić grafy, które różnią się wyłącznie nazwami wierzchołków. Powiemy, że dwa grafy $G = (V, E)$ i $G^{'} = (V^{'}, E^{'})$ są izomorficzne, jeżeli istnieje taka bijekcja $f : V \to V^{'}$ , że $v w \in E wtedy i tylko wtedy, gdy f (v) f (w) \in E^{'}$ dla dowolnych $v, w \in V$ . Intuicyjnie, dwa grafy są izomorficzne wtedy i tylko wtedy, gdy da się je narysować w ten sam sposób.

Możemy teraz zapytać:

Ile jest nieizomorficznych grafów o $n$ wierzchołkach?

Dla $n = 1$ taki graf jest tylko jeden i nie ma żadnych krawędzi:

W przypadku $n = 2$ istnieją dwa różne grafy: i a dla $n = 3$ cztery:

Trochę trudniej wyznaczyć wszystkie nieizomorficzne grafy zbudowane na czterech wierzchołkach, ale po paru minutach znajdziemy je wszystkie:

Oznaczając liczbę nieizomorficznych grafów o $n$ wierzchołkach przez $G_{n}$ , sprawdziliśmy, że $G_{1} = 1$ , $G_{2} = 2$ , $G_{3} = 4$ oraz $G_{4} = 11$ . Dla większych wartości $n$ znalezienie $G_{n}$ staje się coraz trudniejsze, nawet przy pomocy metod komputerowych. Powodem jest to, że nie znamy żadnego szybkiego (działającego w czasie wielomianowym) algorytmu, który sprawdzałby, czy dwa zadane grafy są izomorficzne.

Możemy jednak stosunkowo łatwo oszacować liczbę $G_{n}$ . Ograniczeniem górnym jest oczywiście $2^{(\binom{n}{2})}$ , ale domyślamy się, że nie jest to wartość optymalna. Spróbujmy znaleźć sensowne ograniczenie dolne. Zastanówmy się, ile grafów może być izomorficznych z danym grafem $G .$ Z każdym takim izomorficznym grafem związana jest dowodząca izomorficzności permutacja wierzchołków $G,$ więc grafów izomorficznych z $G$ jest co najwyżej tyle, ile permutacji jego wierzchołków, czyli $n! .$ ( Jeśli tylko permutacja identycznościowa prowadzi do grafu izomorficznego z grafem $G$ , to mówimy, że jest on asymetryczny – wtedy każde przeetykietowanie jego wierzchołków daje w efekcie inny graf). Skoro wszystkich grafów jest $2^{(\binom{n}{2})},$ to z dokładnością do izomorfizmu jest ich co najmniej $2^{(\binom{n}{2})} / n! .$ Ostatecznie $\frac{2^{(\binom{n}{2})}}{n!} \leq G_{n} \leq 2^{(\binom{n}{2})} .$

Zwróćmy uwagę, że gdyby wszystkie grafy były asymetryczne, to nierówność z lewej strony stałaby się równością. Wiemy, że tak nie jest, bo dla każdego $n$ istnieją grafy o $n$ wierzchołkach, które nie są asymetryczne (na przykład grafy pełne, czyli kliki), Jeżeli jednak wyznaczymy, przy pomocy komputera, wartość $G_{n}$ dla małych $n$ , to okaże się, że uzyskane dolne oszacowanie wcale nie jest takie złe.

W trzecim wierszu podaliśmy wartości $2^{(\binom{n}{2})} / n!$ zaokrąglone w górę. Dużym zaskoczeniem wydaje się fakt, że to oszacowanie jest coraz lepsze wraz ze wzrostem $n$ i asymptotycznie okazuje się optymalne. Mówi o tym piękne i głębokie twierdzenie udowodnione przez Paula Erdősa, Alfréda Rényiego i George’a Pólyę. Wykazali oni, że prawie wszystkie grafy są asymetryczne, to znaczy przy $n$ dążącym do nieskończoności stosunek liczby grafów asymetrycznych o $n$ wierzchołkach do liczby wszystkich grafów o $n$ wierzchołkach dąży do jednego, co implikuje poniższe twierdzenie.

Twierdzenie 1 (Erdős-Rényi-Pólya, 1963 r.). Mamy $lim_{n \to + \infty} \frac{G_{n}}{2^{(\binom{n}{2})} / n!} = 1.$

Na tym moglibyśmy właściwie zakończyć, ale prawdziwy skarb ciągle na nas czeka. Przejdźmy bowiem do grafów o przeliczalnej liczbie wierzchołków. Oczywiście nieizomorficznych grafów tego typu jest nieskończenie wiele, ale nas interesuje raczej to, jaką frakcję stanowią one w zbiorze wszystkich grafów. Aby to pytanie uściślić, wprowadźmy pojęcie grafu losowego.

Niech $V = {v_{i} : i \in N}$ będzie ustalonym zbiorem wierzchołków. Ustawiamy w ciąg rodzinę wszystkich podzbiorów dwuelementowych ${v_{i}, v_{j}}$ , $i \neq j$ zbioru $V$ i dla każdego z nich rzucamy symetryczną monetą. Jeżeli wypadł orzeł, to do zbioru krawędzi $E$ dodajemy krawędź $v_{i} v_{j}$ . Tak skonstruowany graf $G = (V, E)$ będziemy nazywać grafem losowym. Możemy teraz pytać, jakie jest prawdopodobieństwo, że taki graf ma pewną żądaną cechę.

Wprowadźmy następującą własność:

Dla dowolnych skończonych i rozłącznych i skończonych zbiorów wierzchołków $U, W \subset V$ istnieje wierzchołek $v \in V$ , który sąsiaduje ze wszystkimi wierzchołkami z $U$ oraz z żadnym wierzchołkiem z $V$ .

Lemat 1. Prawdopodobieństwo, że graf losowy ma własność $(△)$ jest równe $1$ .

Sprawdzimy, że dopełnienie rozważanego zdarzenia ma prawdopodobieństwo równe $0$ . Ponieważ różnych par $(U, W)$ utworzonych z rozłącznych i skończonych zbiorów $U$ i $W$ jest przeliczalnie wiele, wystarczy, że wykażemy tezę dla dowolnie wybranej pary. Przyjmijmy, że zbiory $U$ i $W$ mają łącznie $n$ wierzchołków. To, czy wierzchołek $v \in V$ ma cechę opisaną w $(△)$ , jest zdeterminowane przez wzajemną relację między $v$ a wierzchołkami w $U \cup W$ . Ponieważ krawędzie losujemy niezależnie, to prawdopodobieństwo tego, że wierzchołek $v$ nie ma żądanej własności, jest równe $1 - 2^{- n}$ . Oznaczając przez $A_{k}$ zdarzenie: $żaden z wierzchołków v_{1}, \dots, v_{k} nie spełnia (△),$ widzimy, ponownie wykorzystując niezależność, że jego prawdopodobieństwo jest równe $(1 - 2^{- n})^{k}$ . To implikuje $lim_{k \to + \infty} P (A_{k}) = 0$ i kończy dowód lematu, gdyż własność $(△)$ zachodzi wtedy i tylko wtedy, gdy zachodzi dopełnienie zdarzenia $lim_{k \to + \infty} A_{k} = ⋃_{k = 1}^{+ \infty} A_{k}$ .

Sam lemat nie robi może wielkiego wrażenia, ale wynika z niego bezpośrednio, że istnieje tylko jeden nieskończony graf losowy!

Twierdzenie 2 (Erdős-Rényi, 1963 r.). Dwa nieskończone grafy losowe są izomorficzne z prawdopodobieństwem $1$ .

Proof. Niech $G = (V, E)$ i $G^{'} = (V^{'}, E^{'})$ będą nieskończonymi grafami losowymi. Wykorzystując technikę tam i z powrotem, zbudujemy izomorfizm $f$ między nimi.

Przyjmijmy, że $V = {v_{1}, v_{2}, \dots}$ i $V^{'} = {w_{1}, w_{2}, \dots}$ , i połóżmy $f (v_{1}) = w_{1}$ . Rozważmy wierzchołek $w_{2}$ i znajdźmy w grafie $G$ wierzchołek $v_{i}$ o tej własności, że $v_{1} v_{i} \in E$ wtedy i tylko wtedy, gdy $w_{1} w_{2} \in E^{'}$ . Niech $f (v_{i}) = w_{2}$ . Przejdźmy do wierzchołka $v_{2}$ (lub $v_{3}$ , w razie gdyby $v_{i} = v_{2}$ ), i znajdźmy w grafie $G^{'}$ wierzchołek $w_{j}$ , który jest w tej samej relacji do $w_{1}$ i $w_{2}$ co $v_{2}$ do $v_{1}$ i $v_{i}$ – chcemy, aby grafy złożone z wierzchołków ${v_{1}, v_{i}, v_{2}}$ i ${w_{1}, w_{2}, w_{j}}$ były izomorficzne. Definiujemy $f (v_{2}) = w_{j}$ .

Powtarzamy opisaną procedurę w nieskończoność. W kroku o numerze nieparzystym (tam) znajdujemy pierwszy wierzchołek w zbiorze $V$ , powiedzmy $v_{n}$ , na którym funkcja $f$ nie została jeszcze określona. Podzielmy zbiór wierzchołków, na których funkcja $f$ jest już określona, na dwie części: niech $U$ zawiera sąsiadów $v_{n}$ , a $W$ resztę. Połóżmy $U^{'} = f (U)$ i $W^{'} = f (W)$ . Zbiory $U^{'}$ i $W^{'}$ są skończone i rozłączne, bo takie też są zbiory $U$ i $W$ . Z lematu wiemy, że istnieje w grafie $G^{'}$ wierzchołek, który sąsiaduje ze wszystkimi wierzchołkami z $U^{'}$ i żadnym wierzchołkiem z $W^{'}$ . Wybierzmy taki wierzchołek o najmniejszym indeksie, powiedzmy $w_{m}$ , i zdefiniujmy $f (v_{n}) = w_{m}$ .

Analogicznie postępujemy w kroku o numerze parzystym (z powrotem). Niech $w_{n}$ będzie pierwszym wierzchołkiem w zbiorze $V^{'}$ , który nie jest wartością funkcji $f$ . Aktualny zbiór wartości funkcji $f$ dzielimy na sąsiadów $U^{'}$ wierzchołka $w_{n}$ i resztę $W^{'}$ . Następnie znajdujemy w grafie $G$ odpowiednik $v_{m}$ wierzchołka $w_{n}$ , który sąsiaduje ze wszystkimi wierzchołkami z $f^{- 1} (U^{'})$ i nie sąsiaduje z żadnym wierzchołkiem z $f^{- 1} (W^{'})$ . Przyjmujemy $f (v_{m}) = w_{n}$ .

Bezpośrednio z konstrukcji funkcji $f$ widać, że jest ona bijekcją między zbiorami wierzchołków $G$ i $G^{'}$ i zadaje poszukiwany izomorfizm. ◻

Erdős i Rényi pokazali, że w pewnym sensie istnieje tylko jeden nieskończony graf losowy – jest to graf określony przez warunek $(△)$ . Nie wskazali jednak żadnego konkretnego egzemplarza. Pierwszy przykład został skonstruowany przez Richarda Rado w 1964 roku. Graf Rado jest niezwykle urokliwy. Zbiorem wierzchołków jest $V = N$ , a $m, n \in V$ , $m < n$ są połączone krawędzią wtedy i tylko wtedy, gdy w zapisie dwójkowym liczby $n$ na $m$ -tym miejscu od prawej strony występuje $1$ . Dla przykładu wierzchołki 4 i 10 są połączone krawędzią, ponieważ zapis dwójkowy liczby 10, czyli $(1010)_{2},$ ma na 4. miejscu od prawej strony jedynkę. Uzasadnijmy, że tak skonstruowany graf ma własność $(△)$ . Niech $U, W \subset V$ będą skończone i rozłączne. Dodając w razie potrzeby nowy wierzchołek do $U$ , możemy przyjąć, że $max U > max W$ . Wystarczy teraz zauważyć, że $v = \sum_{u \in U} 2^{u - 1}$ ma własność opisaną w $(△)$ .

Przez graf rozumiemy parę uporządkowaną $(V, E)$ , w której $V$ jest ustalonym zbiorem wierzchołków, a $E$ zbiorem krawędzi traktowanym jako pewien podzbiór zbioru ${{v, w} : v, w \in V, v \neq w}$ . Krawędź ${v, w}$ będziemy dla uproszczenia oznaczać jako $v w$ .

W rozważanym przykładzie ten izomorfizm już znaleźliśmy: $f (v_{1}) = v_{2}$ , $f (v_{2}) = v_{3}$ , $f (v_{3}) = v_{4}$ , $f (v_{4}) = v_{1}$ .

Problem izomorficzności grafów należy do klasy NP (dla danej funkcji $f$ łatwo sprawdzić, czy jest ona izomorfizmem), ale nie wiadomo, czy jest NP-zupełny ani czy należy on do klasy P. Wprowadzenie do klas złożoności Czytelnik znajdzie w artykule W. Czerwińskiego Dlaczego problem P = NP jest tak trudny? $(Δ_{17}^{3})$ .

Erdős i Rényi wykazali, iż prawdopodobieństwo zdarzenia, że losowo wybrany graf o $n$ wierzchołkach jest asymetryczny, dąży do jedności przy $n \to + \infty$ , a Pólya znalazł asymptotykę $G_{n}$ .

Należy mieć świadomość, że konstrukcja przestrzeni probabilistycznej wymaga uwagi. Możemy utożsamić grafy losowe z ciągami zero-jedynkowymi i traktować je jak liczby rzeczywiste z przedziału $[0, 1]$ . Pytanie o to, czy graf losowy ma żądaną własność, sprowadzamy w ten sposób do pytania o miarę Lebesgue’a podzbiorów odcinka jednostkowego. Pozwolę sobie jednak pominąć mniej istotne szczegóły techniczne.

Jeżeli przeliczalnie wiele zdarzeń ma prawdopodobieństwo $0$ , to ich suma również.

Dla pełnej ścisłości powinniśmy się w tym miejscu powołać na ciągłość miary prawdopodobieństwa $P$ .

Taki wierzchołek istnieje z prawdopodobieństwem $1$ na mocy lematu.

Podkreślamy, że $U \cup W$ zawiera tylko te wierzchołki, na których $f$ została już zdefiniowana.