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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 24 mar 2018, o 15:59 
Użytkownik

Posty: 1074
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 
 schemat doskonały grafy  kopacz22  0
 Znajdź wszystkie grafy  netsprint  1
 grafy kołowy Pn PnXCn  pawel430  0
 Grafy proste nieskierowane  Matix16  1
 Uporządkowanie liczb. Grafy.  snowjay  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl