szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Grafy spójne
PostNapisane: 8 lut 2017, o 13:46 
Użytkownik

Posty: 3
Lokalizacja: Polska
mam takie zadanie i szczerze nie wiem jak je ugryźć:(

Ze zbioru niespójnych grafów o n wierzchołkach wybierzmy taki graf G, który ma
najwieksza liczbe krawedzi. Pokazac, ze G ma dokładnie dwie składowe spójne.

Dzięki za każdą pomoc!
Góra
Mężczyzna Offline
 Tytuł: Grafy spójne
PostNapisane: 8 lut 2017, o 13:55 
Gość Specjalny
Avatar użytkownika

Posty: 12735
Lokalizacja: Kraków
Idea:

Gdyby graf miał N>2 składowe, to można dorysować N-2 krawędzie, wszystkie wychodzące z jednego wierzchołka jednej składowej i łączące dowolny wierzchołek w każdej z N-2 pozostałych składowych. Tak otrzymany graf nadal jest niespójny, ale ma więcej krawędzi niż wyjściowy.
Góra
Mężczyzna Offline
 Tytuł: Grafy spójne
PostNapisane: 8 lut 2017, o 15:15 
Użytkownik

Posty: 3
Lokalizacja: Polska
Dzięki pomogło to może za ciosem zadam kolejne pytanie . Mam takie zadanie:

Niech G bedzie grafem majacym 5 wierzchołków , z których jeden ma stopien 2. Pokazac,
ze G jest planarny.

Czy dobrze mysilę ze skoro K5 to jest on nie planarny z twierdzenia Kuratowskiego?
Góra
Mężczyzna Offline
 Tytuł: Grafy spójne
PostNapisane: 9 lut 2017, o 07:16 
Gość Specjalny
Avatar użytkownika

Posty: 12735
Lokalizacja: Kraków
Raczej nie jest on K_5. Poza tym piszesz, że nie jest planarny, a masz przecież pokazać, że jest...

Skoro jest wierzchołek stopnia 2, graf jest różny od K_5, więc jest planarny, na mocy tw. Kuratowskiego.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Policzyć grafy według typów izomorfizmów  jakubjo  0
 Grafy k-krytyczny  qwas1234  1
 Grafy, funkcja tworzaca  miglanc  1
 Dowód Grafy 2-spójne  adri  0
 Funkcja tworząca, wzór jawny, grafy. mod  Crave  7
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl