Grafy samodopełniające się

[driller12]

Witam.
Muszę narysować wszystkie grafy samodopełniające się o 5 wierzchołkach i nie mam pojęcia jak się do tego zabrać. Wiem tyle co z definicji, czyli ze graf samodopełniajacy się to graf izomorficzny do swojego dopełnienia, oraz wiem, że ma połowę krawędzi grafu pełnego. Ale jakoś tego nie rozumiem, nie wiem jak przenieść to na papier. Byłbym wdzięczny za pomoc jak zacząć, jak to zrozumieć oraz jak dużo jest takich grafów.
Pozdrawiam serdecznie.

[Mruczek]

Wiesz co to jest izomorfizm grafów?

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Izomorfizm_graf%C3%B3w

Graf pełny o \(\displaystyle{ 5}\) wierzchołkach ma \(\displaystyle{ 10}\) krawędzi, a ponieważ w samodopełniającym się dopełnienie ma tyle krawędzi co początkowy graf to znaczy że mają po \(\displaystyle{ 5}\) krawędzi. Po prostu narysuj wszystkie nieizomorficzne grafy o \(\displaystyle{ 5}\) krawędziach i potem sprawdź czy są izomorficzne do swojego dopełnienia.
Możesz skorzystać ze znanego i prostego w dowodzie twierdzenia, że zawsze przynajmniej jeden z grafów: graf i graf będący jego dopełnieniem jest spójny. To znaczy, że rysując grafy możesz ograniczyć się do grafów spójnych. Dopełnienie tego niespójnego zawsze będzie spójne, czyli nie będą izomorficzne.
Grafy możesz rysować np. tak że zakładasz jaki jest maksymalny stopień w grafie i rysujesz wszystkie takie itd. W grafie o \(\displaystyle{ 5}\) wierzchołkach wierzchołek może mieć maksymalny stopień \(\displaystyle{ 4}\). W dopełnieniu grafu o maks. stopniu \(\displaystyle{ 4}\) zawsze wierzchołek o stopniu \(\displaystyle{ 4}\) będzie izolowany, czyli dopełnienie nie będzie spójne - takie grafy możemy odrzucać.
Mi wyszło, że są dwa takie grafy samodopełniające się.