Witam,
Bardzo proszę o pomoc z takim zadankiem.
Wykazać, iż graf \(\displaystyle{ G = (V, E)}\) jest spójny wtedy i tylko wtedy gdy dla każdego podziału zbioru \(\displaystyle{ V}\)na niepuste podzbiory \(\displaystyle{ V_{1} V _{2}}\) istnieje krawędź xy taka, że \(\displaystyle{ x \in V_{1}}\), a \(\displaystyle{ y \in V _{2}}\).
Wykazać że graf spójny.
-
Jytug
- Użytkownik
- Posty: 73
- Rejestracja: 10 gru 2012, o 12:21
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 1 raz
- Pomógł: 11 razy
Wykazać że graf spójny.
\(\displaystyle{ "\Rightarrow"}\)
Oczywiście jeśli istnieją dwa takie podzbiory, że \(\displaystyle{ V(G)=V_1 \cup V_2}\) i \(\displaystyle{ \forall_{x\in V_1, y \in V_2} ~~ xy \notin E(G)}\), to dla dowolnego wierzchołka z \(\displaystyle{ V_1}\) nie istnieje ścieżka do żadnego elementu z \(\displaystyle{ V_2}\), a więc graf jest niespójny. Sprzeczność
\(\displaystyle{ "\Leftarrow"}\)
Załóżmy, że graf jest spójny i podzielmy go na \(\displaystyle{ V_1, V_2}\). Ze spójności mamy, że dla \(\displaystyle{ x \in V_1, y \in V_2}\) istnieje ścieżka je łącząca \(\displaystyle{ x=x_1, x_2, \dots, x_k=y}\). Wtedy idziemy po tej ścieżce tak długo, aż natrafimy na krawędź pomiędzy \(\displaystyle{ V_1}\) i \(\displaystyle{ V_2}\) (w końcu to nastąpi, bo \(\displaystyle{ y=x_k \in V_2}\)
Oczywiście jeśli istnieją dwa takie podzbiory, że \(\displaystyle{ V(G)=V_1 \cup V_2}\) i \(\displaystyle{ \forall_{x\in V_1, y \in V_2} ~~ xy \notin E(G)}\), to dla dowolnego wierzchołka z \(\displaystyle{ V_1}\) nie istnieje ścieżka do żadnego elementu z \(\displaystyle{ V_2}\), a więc graf jest niespójny. Sprzeczność
\(\displaystyle{ "\Leftarrow"}\)
Załóżmy, że graf jest spójny i podzielmy go na \(\displaystyle{ V_1, V_2}\). Ze spójności mamy, że dla \(\displaystyle{ x \in V_1, y \in V_2}\) istnieje ścieżka je łącząca \(\displaystyle{ x=x_1, x_2, \dots, x_k=y}\). Wtedy idziemy po tej ścieżce tak długo, aż natrafimy na krawędź pomiędzy \(\displaystyle{ V_1}\) i \(\displaystyle{ V_2}\) (w końcu to nastąpi, bo \(\displaystyle{ y=x_k \in V_2}\)