\(\displaystyle{ (V,E)}\) - drzewo \(\displaystyle{ G}\), \(\displaystyle{ (V_1,E_1), (V_2,E_2), (V_3,E_3),}\) spójne podgrafy \(\displaystyle{ G}\). Pokazać, że jeśli \(\displaystyle{ \bigwedge (1 \le i, j \le 3) V_i \cap V_j \neq \emptyset}\) to \(\displaystyle{ V_1 \cap V_2 \cap V_3 \neq \emptyset}\).
Próbowałam to robić jakoś tak, że biorę dowolny wierzchołek \(\displaystyle{ x}\) z \(\displaystyle{ V_1 \cap V_2}\). Istnieje droga między x i dowolnym wierzchołkiem z \(\displaystyle{ V_1}\) oraz między \(\displaystyle{ x}\) i dowolnym wierzchołkiem z \(\displaystyle{ V_2}\), bo grafy te są spójne.
Biorę dowolny wierzchołek \(\displaystyle{ y}\) z \(\displaystyle{ V_2 \cap V_3}\). Istnieje droga między \(\displaystyle{ x}\) i \(\displaystyle{ y}\), bo oba należą do \(\displaystyle{ V_2}\). Jest tylko jedna taka drogą, bo inaczej powstałby cykl.
Biorę dowolny wierzchołek \(\displaystyle{ z}\) z \(\displaystyle{ V_1 \cap V_3}\). Istnieje droga między \(\displaystyle{ x}\) i \(\displaystyle{ z}\), bo oba należą do \(\displaystyle{ V_1}\). Jest tylko jedna taka drogą, bo inaczej powstałby cykl.
Te drogi muszą mieć część wspólną, bo nie ma cykli, czyli \(\displaystyle{ V_1 \cap V_2 \cap V_3 \neq \emptyset}\).
Nie wiem, jak tę końcówkę do końca uzasadnić. I proszę o pomoc, czy ogólnie ten dowód ma mniej więcej sens.
drzewa, część wspólna spójnych podgrafów
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
drzewa, część wspólna spójnych podgrafów
Załóżmy nie wprost, że ten przekrój jest pusty
Usuńmy z G \(\displaystyle{ V_1\cap V_2}\), wtedy każda spójna składowa tego co pozostanie zawiera wierzchołki z co najwyżej jednego ze zbiorów \(\displaystyle{ V_1, V_2}\) (to wymaga uzasadnienia). No, a \(\displaystyle{ V_3}\) musi być zawarty w pewnej takiej składowej (bo kroi się pusto z wyrzuconym \(\displaystyle{ V_1\cap V_2}\)). Sprzeczność.
Usuńmy z G \(\displaystyle{ V_1\cap V_2}\), wtedy każda spójna składowa tego co pozostanie zawiera wierzchołki z co najwyżej jednego ze zbiorów \(\displaystyle{ V_1, V_2}\) (to wymaga uzasadnienia). No, a \(\displaystyle{ V_3}\) musi być zawarty w pewnej takiej składowej (bo kroi się pusto z wyrzuconym \(\displaystyle{ V_1\cap V_2}\)). Sprzeczność.
-
- Użytkownik
- Posty: 209
- Rejestracja: 13 lip 2012, o 14:32
- Płeć: Kobieta
- Lokalizacja: Pcim
- Podziękował: 107 razy
drzewa, część wspólna spójnych podgrafów
Dziękuję.
Jakby jeszcze ktoś mógł powiedzieć, czy mój pomysł też był dobry, czy zły, to byłoby super.
Jakby jeszcze ktoś mógł powiedzieć, czy mój pomysł też był dobry, czy zły, to byłoby super.
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
drzewa, część wspólna spójnych podgrafów
Te drogi o których piszesz mają część wspólną: jest w niej \(\displaystyle{ x}\). Ale dlaczego z tego ma coś wynikać o niepustości: \(\displaystyle{ V_1\cap V_2 \cap V_3}\)?
-
- Użytkownik
- Posty: 209
- Rejestracja: 13 lip 2012, o 14:32
- Płeć: Kobieta
- Lokalizacja: Pcim
- Podziękował: 107 razy
drzewa, część wspólna spójnych podgrafów
Próbowałam jakoś zapisać to, że jak mam już to przecięcie \(\displaystyle{ V_1 \cap V_2}\), to \(\displaystyle{ V_3}\) można przeciąć z oboma tymi zbiorami tylko w tym zbiorze \(\displaystyle{ V_1 \cap V_2}\), inaczej jakby dodać krawędzie oddzielnie do tych zbiorów, to powstałby cykl.
Ale trochę mi nie wyszło
Ale trochę mi nie wyszło