szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 29 maja 2012, o 14:35 
Użytkownik

Posty: 33
Znajdź wszystkie grafy o 6 wierzchołkach, których nie da się narysować na płaszczyźnie bez przecinania
się krawędzi (nie są planarne).

Czy odpowiedzią jest 11? Skorzystałem z twierdzenia Kuratowskiego: Graf K_{3,3} oraz 10 grafów rozszerzonych powstałych z grafu K_{5}(tyle ma krawędzi, w każdą z nich można wstawić wierzchołek)
Góra
Mężczyzna Offline
PostNapisane: 29 maja 2012, o 19:31 
Użytkownik

Posty: 1272
Lokalizacja: Warszawa
zgadza się, odpowiedź to 11
Góra
Mężczyzna Offline
PostNapisane: 1 cze 2012, o 19:44 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
1) Czy izomorficzne grafy utożsamiamy, czy nie? Jeśli tak, to do tej pory podałeś dwa grafy. Jeśli nie utożsamiamy i jest ustalony sześcioelementowy zbiór wierzchołków, to podałeś \binom63+6\cdot10 przykładów.

2) Po dodaniu wierzchołka na jednej z krawędzi można jeszcze dodawać krawędzie. Moim zdaniem mamy już 5 grafów z dokładnością do izomorfizmu.

3) Jeśli nie jest powiedziane, że graf ma być spójny, to mamy kolejny, szósty przykład: K_5 + izolowany wierzchołek.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Grafy, które nie są izomorficzne  damian18833  3
 Wypisz wszystkie elementy zbioru  sebool12  9
 Znaleźć wszystkie liczby całkowite x takie, że  Pietrzak93  0
 Grafy-program sage  asqq  0
 Grafy cykliczne, macierze sąsiedztwa.  rra  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl