zakladamy ze \(\displaystyle{ G=(X,Y,E)}\) - graf dwudzielny oraz \(\displaystyle{ 1 \le |X| \le |Y|}\)
wykaz ze jesli \(\displaystyle{ G}\) jest spojny to \(\displaystyle{ Diam (G) \le 2|X|}\)
-- 24 mar 2017, o 21:01 --
mam taki pomysl:
Niech \(\displaystyle{ |X|=k}\). Mamy ze \(\displaystyle{ G}\) jest spojny , a wiec istnieje miedzy kazdymi dwoma wierzcholkami \(\displaystyle{ u ,v \in V(G)}\) sciezka je łączaca. Wezmy sciezke zawierajaca wszystkie wierzcholki z \(\displaystyle{ X}\) laczaca wierzcholki \(\displaystyle{ u, v \in Y}\). Wtedy mamy ze \(\displaystyle{ dist(u,v) \le 2k}\) (wynika to z tego ze krawedz wychodzi z zbioru \(\displaystyle{ Y}\) do \(\displaystyle{ X}\) i wraca z powrotem z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\)). A kazda inna sciezka przechodząca przez mniej niz \(\displaystyle{ k}\) wierzchołkow z \(\displaystyle{ X}\) jest mniejszej dlugosci niz ta powyzej. (bo wierzcholki z tego samego zbioru nie lacza sie bezposrednio same z soba) .
graf dwudzielny
-
- Użytkownik
- Posty: 8
- Rejestracja: 24 mar 2017, o 17:23
- Płeć: Mężczyzna
- Lokalizacja: Kraków
graf dwudzielny
Ostatnio zmieniony 25 mar 2017, o 14:19 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
graf dwudzielny
Mamy pokazać, że między dowolnymi dwoma wierzchołkami \(\displaystyle{ x, y}\) istnieje ścieżka długości (liczbie krawędzi) \(\displaystyle{ \le 2|X|}\). Ty wziąłeś w dowodzie dwa wierzchołki ale z \(\displaystyle{ Y}\). Trzeba to rozszerzyć na dowolne pary wierzchołków w analogiczny sposób. Przyjmujemy, że na naszej ścieżce wierzchołki nie powtarzają się (bez cykli, aby miała jak najkrótszą długość). To znaczy, że na ścieżce dla dowolnego wierzchołka są co najwyżej dwie krawędzie kończące się w nim. Każda krawędź ma jeden koniec w wierzchołku z \(\displaystyle{ X}\), więc ścieżka zawiera co najwyżej \(\displaystyle{ |X|}\) wierzchołków z \(\displaystyle{ X}\), więc ma co najwyżej \(\displaystyle{ 2|X|}\) krawędzi.