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: 12725
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: 12725
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 
 grafy-zachłanny algorytm kolorowania  borubarek  2
 Liczba niezależności (grafy)  snowjay  0
 Sprawdzanie czy grafy są izomorficzne  Mr Krzysio  0
 Grafy; tablica n na n; n osób w kolejce; rekurencja.  kswiss  6
 Grafy 4 zadania  jemcole  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl