szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 15 paź 2015, o 22:46 
Użytkownik

Posty: 36
Lokalizacja: Kraków (UJ)
Mamy graf nieskierowany spójny o n wierzchołkach. Ma on co najmniej n-1 krawędzi ( \Leftarrow spójność). Jak to udowodnić? Indukcja po ilości wierzchołków chyba nie wchodzi w grę (albo tak mi się wydaję), myślałem nad indukcją ze względu na ilość krawędzi (troche naokoło, ale z tego wprost wynika teza po drobnych przekształceniach).
Góra
PostNapisane: 16 paź 2015, o 07:02 
Użytkownik
Niech graf G będzie sójnym grafem o n wierzchołkach: v_1 , v_2 , ...,v_n . Niech dla każdego 1\leqslant i \leqslant n-1 zapis L_i :v_1 , v_{k_2 } , ..., v_{k_{j_i}} , v_i oznacza drogę łączącą wierzchołek v_1 z wierzchołkiem v_i . Wówczas odwzorowanie f: \bigcup_i \{L_i \} \to E okreslone wzorem f(L_i ) =\overline{v_{k_{j_i}} , v_i} jest różnowartościowe, skąd wynika teza.
Góra
Mężczyzna Offline
PostNapisane: 16 paź 2015, o 20:14 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
pingwindyktator napisał(a):
myślałem nad indukcją ze względu na ilość krawędzi (troche naokoło, ale z tego wprost wynika teza po drobnych przekształceniach).

Bardzo dobry pomysł.
Góra
Mężczyzna Offline
PostNapisane: 18 paź 2015, o 15:13 
Użytkownik

Posty: 36
Lokalizacja: Kraków (UJ)
norwimaj napisał(a):
pingwindyktator napisał(a):
myślałem nad indukcją ze względu na ilość krawędzi (troche naokoło, ale z tego wprost wynika teza po drobnych przekształceniach).

Bardzo dobry pomysł.


Czyli mogę pokazać, że mając n krawędzi, największy (ze względu na ilość wierzchołków) graf spójny jaki mogę na tych krawędziach zbudować ma n+1 wierzchołków, tak? To prosta indukcja.
Góra
Mężczyzna Offline
PostNapisane: 18 paź 2015, o 16:55 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Żeby się nie myliło, użyłbym innej litery na liczbę krawędzi. Dowodzone twierdzenie, po drobnym przeformułowaniu, brzmi: (dla każdych n\in\mathbb{N}_+, k\in\mathbb{N}) jeśli istnieje nieskierowany graf spójny o n wierzchołkach i k krawędziach, to k \ge n-1. W kroku indukcyjnym mamy pewien graf spójny i usuwamy z niego jedną krawędź. Wtedy albo nadal będziemy mieli graf spójny, albo dostaniemy graf o dwóch spójnych składowych. Stosujemy założenie indukcyjne dla całego grafu lub dla składowych, itd.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 kolorowanie grafu - graf planarny 3-kolorowalny  Algorytmistrz  2
 Ilosć ciągów niemalejących  matematyka464  1
 Wykaż, że... graf spójny - wierzchołki - jednakowe stopnie  gabilu  1
 Ilość pięcioliterowych słów z liter słowa Pascal.  Nati071188  1
 Spójny graf prosty - wymiar  niunian  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl