Dany jest graf dwudzielny \(\displaystyle{ G = \left( X,Y;E\right)}\) taki, że \(\displaystyle{ 1 \le \left| X\right| \le \left| Y\right|}\)
Udowodnij, że jeśli \(\displaystyle{ \delta\left( G\right) \ge \frac{\left| Y\right| + 1}{2}}\) to graf \(\displaystyle{ G}\) jest spójny.
Jak to udowodnić? Od czego zacząć?
Dowód z grafem dwudzielnym
-
arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Dowód z grafem dwudzielnym
Załóż nie wprost, że graf nie jest spójny , i wtedy biorąc pod uwagę stopień najmniejszy pewnego wierzchołka, oraz warunek zadania dojdziesz łatwo do sprzeczności...
-
Dreeze
- Użytkownik
- Posty: 37
- Rejestracja: 8 maja 2017, o 19:00
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 14 razy
Re: Dowód z grafem dwudzielnym
Spójrzmy na graf \(\displaystyle{ G}\) z Twojego zadania.
Stopień minimalny tego grafu, wynosi: \(\displaystyle{ \frac{|Y| + 1}{2}}\).
Czyli każdy wierzchołek ma stopień większy od połowy rzędu zbioru \(\displaystyle{ Y}\).
Pokażemy, że dla dowolnych dwóch wierzchołków z tego grafu, istnieje ścieżka, która je łączy.
Wybierzmy dowolne dwa wierzchołki \(\displaystyle{ u,v \in V(G)}\).
Jeżeli \(\displaystyle{ u,v}\) należą do tego samego zbioru - \(\displaystyle{ X}\) lub \(\displaystyle{ Y}\), to sprawa jest oczywista.
Przypuśćmy, że \(\displaystyle{ u,v \in X}\), krawędzie obydwu tych wierzchołków prowadzą do zbioru \(\displaystyle{ Y}\) oraz ich stopnie są większe od połowy rzędu zbioru \(\displaystyle{ Y}\), wobec czego \(\displaystyle{ u}\) i \(\displaystyle{ v}\) mają wspólnego sąsiada. (zasada szufladkowa Dirichleta)
Analogicznie, gdy \(\displaystyle{ u,v \in Y}\) (wiemy, że rząd \(\displaystyle{ X}\) jest nie większy od rzędu \(\displaystyle{ Y}\)).
Przypuśćmy teraz, bez straty ogólności, że \(\displaystyle{ u \in X, v \in Y}\). Wybierzmy wierzchołek \(\displaystyle{ w\in X}\) taki, że \(\displaystyle{ wv \in E(G)}\) - na pewno taki istnieje.
Prowadząc podobne rozumowanie, jak w poprzednim przypadku - istnieje ścieżka między \(\displaystyle{ w}\) oraz \(\displaystyle{ u}\), a zatem, skoro \(\displaystyle{ w}\) i \(\displaystyle{ v}\) są połączone krawędzią, to musi też istnieć ścieżka między \(\displaystyle{ u}\) i \(\displaystyle{ v}\).
Pokazaliśmy więc, że dla dowolnej pary wierzchołków istnieje ścieżka, która je łączy. Czyli że graf \(\displaystyle{ G}\) jest grafem spójnym.
Stopień minimalny tego grafu, wynosi: \(\displaystyle{ \frac{|Y| + 1}{2}}\).
Czyli każdy wierzchołek ma stopień większy od połowy rzędu zbioru \(\displaystyle{ Y}\).
Pokażemy, że dla dowolnych dwóch wierzchołków z tego grafu, istnieje ścieżka, która je łączy.
Wybierzmy dowolne dwa wierzchołki \(\displaystyle{ u,v \in V(G)}\).
Jeżeli \(\displaystyle{ u,v}\) należą do tego samego zbioru - \(\displaystyle{ X}\) lub \(\displaystyle{ Y}\), to sprawa jest oczywista.
Przypuśćmy, że \(\displaystyle{ u,v \in X}\), krawędzie obydwu tych wierzchołków prowadzą do zbioru \(\displaystyle{ Y}\) oraz ich stopnie są większe od połowy rzędu zbioru \(\displaystyle{ Y}\), wobec czego \(\displaystyle{ u}\) i \(\displaystyle{ v}\) mają wspólnego sąsiada. (zasada szufladkowa Dirichleta)
Analogicznie, gdy \(\displaystyle{ u,v \in Y}\) (wiemy, że rząd \(\displaystyle{ X}\) jest nie większy od rzędu \(\displaystyle{ Y}\)).
Przypuśćmy teraz, bez straty ogólności, że \(\displaystyle{ u \in X, v \in Y}\). Wybierzmy wierzchołek \(\displaystyle{ w\in X}\) taki, że \(\displaystyle{ wv \in E(G)}\) - na pewno taki istnieje.
Prowadząc podobne rozumowanie, jak w poprzednim przypadku - istnieje ścieżka między \(\displaystyle{ w}\) oraz \(\displaystyle{ u}\), a zatem, skoro \(\displaystyle{ w}\) i \(\displaystyle{ v}\) są połączone krawędzią, to musi też istnieć ścieżka między \(\displaystyle{ u}\) i \(\displaystyle{ v}\).
Pokazaliśmy więc, że dla dowolnej pary wierzchołków istnieje ścieżka, która je łączy. Czyli że graf \(\displaystyle{ G}\) jest grafem spójnym.