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!
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
 Tytuł: Grafy spójne
PostNapisane: 8 lut 2017, o 14:55 
Administrator
Avatar użytkownika

Posty: 12708
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 
Administrator
Avatar użytkownika

Posty: 12708
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 
 Kolorowanie grafów - 3-krytyczne grafy  flashion  0
 cykle hamiltona - grafy dwudzielne-problem nadal aktualny  mateuss  0
 Grafy proste i macierz przejścia  fizyk_akrobata  1
 Czy grafy mozna tak narysowac??  grangu  0
 Grafy-stopnie wierzchołów  Anonymous  5
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl