szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: graf dwudzielny
PostNapisane: 24 mar 2017, o 20:54 
Użytkownik

Posty: 11
Lokalizacja: Kraków
zakladamy ze G=(X,Y,E) - graf dwudzielny oraz 1 \le |X|  \le  |Y|

wykaz ze jesli G jest spojny to Diam (G) \le  2|X|

-- 24 mar 2017, o 21:01 --

mam taki pomysl:

Niech |X|=k. Mamy ze G jest spojny , a wiec istnieje miedzy kazdymi dwoma wierzcholkami u ,v   \in  V(G) sciezka je łączaca. Wezmy sciezke zawierajaca wszystkie wierzcholki z X laczaca wierzcholki u, v \in  Y. Wtedy mamy ze dist(u,v)  \le  2k (wynika to z tego ze krawedz wychodzi z zbioru Y do X i wraca z powrotem z X do Y). A kazda inna sciezka przechodząca przez mniej niz k wierzchołkow z X jest mniejszej dlugosci niz ta powyzej. (bo wierzcholki z tego samego zbioru nie lacza sie bezposrednio same z soba) .
Góra
Mężczyzna Offline
 Tytuł: graf dwudzielny
PostNapisane: 25 mar 2017, o 14:58 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Mamy pokazać, że między dowolnymi dwoma wierzchołkami x, y istnieje ścieżka długości (liczbie krawędzi) \le 2|X|. Ty wziąłeś w dowodzie dwa wierzchołki ale z 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 X, więc ścieżka zawiera co najwyżej |X| wierzchołków z X, więc ma co najwyżej 2|X| krawędzi.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 graf dwudzielny  kamil.jack  1
 Graf dwudzielny - zadanie 2  contact  3
 graf hamiltonowski z liczba krawedzi  kamil.jack  1
 graf dwudzielny - przecięcia  humbert  1
 Graf prosty, krawędzie cięcia a cykl  Annoyer13  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl