szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Grafy spójne
PostNapisane: 8 lut 2017, o 14: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 14:55 
Gość Specjalny
Avatar użytkownika

Posty: 12727
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 16: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 08:16 
Gość Specjalny
Avatar użytkownika

Posty: 12727
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 
 drzewa spinające, grafy, rekurencja  mwmkh  1
 Maksymalne grafy planarne  Heniek1991  0
 grafy, zależności  Edi___89  0
 Dowód - grafy  matinf  10
 Grafy - Kod Prufera  rozpruwacz  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl