szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 29 maja 2012, o 15: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)
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
PostNapisane: 29 maja 2012, o 20:31 
Użytkownik

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

Posty: 5101
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 
 Wykaż,że graf planarny o n wierzchołkach ma  zuzka_kotek  1
 Grafy spójne  Grzech903  3
 Narysowac 4 grafy (Hamiltonowskie Eulerowskie)  devonsix  2
 Graf spójny o 4 wierzchołkach i 4 krawędziach  tonyhouk  2
 Wyznacz wszystkie liczby trzycyfrowe  prox91  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl