graf dwudzielny

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
danielek12201220
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 24 mar 2017, o 17:23
Płeć: Mężczyzna
Lokalizacja: Kraków

graf dwudzielny

Post autor: danielek12201220 »

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) .
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 .
Mruczek
Użytkownik
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

Post autor: Mruczek »

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.
ODPOWIEDZ