Graf spójny - minimalna ilość krawędzi
-
- Użytkownik
- Posty: 36
- Rejestracja: 18 mar 2014, o 23:58
- Płeć: Mężczyzna
- Lokalizacja: Kraków (UJ)
- Podziękował: 6 razy
Graf spójny - minimalna ilość krawędzi
Mamy graf nieskierowany spójny o \(\displaystyle{ n}\) wierzchołkach. Ma on co najmniej \(\displaystyle{ n-1}\) krawędzi ( \(\displaystyle{ \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).
Graf spójny - minimalna ilość krawędzi
Niech graf \(\displaystyle{ G}\) będzie sójnym grafem o \(\displaystyle{ n}\) wierzchołkach: \(\displaystyle{ v_1 , v_2 , ...,v_n .}\) Niech dla każdego \(\displaystyle{ 1\leqslant i \leqslant n-1}\) zapis \(\displaystyle{ L_i :v_1 , v_{k_2 } , ..., v_{k_{j_i}} , v_i}\) oznacza drogę łączącą wierzchołek \(\displaystyle{ v_1}\) z wierzchołkiem \(\displaystyle{ v_i .}\) Wówczas odwzorowanie \(\displaystyle{ f: \bigcup_i \{L_i \} \to E}\) okreslone wzorem \(\displaystyle{ f(L_i ) =\overline{v_{k_{j_i}} , v_i}}\) jest różnowartościowe, skąd wynika teza.
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Graf spójny - minimalna ilość krawędzi
Bardzo dobry pomysł.pingwindyktator pisze: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).
-
- Użytkownik
- Posty: 36
- Rejestracja: 18 mar 2014, o 23:58
- Płeć: Mężczyzna
- Lokalizacja: Kraków (UJ)
- Podziękował: 6 razy
Graf spójny - minimalna ilość krawędzi
Czyli mogę pokazać, że mając \(\displaystyle{ n}\) krawędzi, największy (ze względu na ilość wierzchołków) graf spójny jaki mogę na tych krawędziach zbudować ma \(\displaystyle{ n+1}\) wierzchołków, tak? To prosta indukcja.norwimaj pisze:Bardzo dobry pomysł.pingwindyktator pisze: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).
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Graf spójny - minimalna ilość krawędzi
Żeby się nie myliło, użyłbym innej litery na liczbę krawędzi. Dowodzone twierdzenie, po drobnym przeformułowaniu, brzmi: (dla każdych \(\displaystyle{ n\in\mathbb{N}_+, k\in\mathbb{N}}\)) jeśli istnieje nieskierowany graf spójny o \(\displaystyle{ n}\) wierzchołkach i \(\displaystyle{ k}\) krawędziach, to \(\displaystyle{ 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.