szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 15 mar 2018, o 20:47 
Użytkownik

Posty: 1
Lokalizacja: Gdańsk
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.
Góra
Mężczyzna Offline
PostNapisane: 24 mar 2018, o 15:59 
Użytkownik

Posty: 1087
Lokalizacja: Lublin/Warszawa
Wiesz co to jest izomorfizm grafów? https://pl.wikipedia.org/wiki/Izomorfizm_graf%C3%B3w
Graf pełny o 5 wierzchołkach ma 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 5 krawędzi. Po prostu narysuj wszystkie nieizomorficzne grafy o 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 5 wierzchołkach wierzchołek może mieć maksymalny stopień 4. W dopełnieniu grafu o maks. stopniu 4 zawsze wierzchołek o stopniu 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ę.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Trudne(?) grafy  rzexnik  2
 Grafy, funkcja tworzaca  miglanc  1
 Grafy, osoby znające tę samą liczbę osób w grupie  anilahcim  1
 Grafy i drzewa  d4nny  5
 Grafy z liczbami pierwszymi oraz funkcje  GypsyHatter  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl