Stránky: 1
Zadání příkladu:
Průměr grafu je vzdálenost dvou nejvzdálenějších vrcholů v grafu. Dokažte nebo vyvra?e, že následujícím postupem získáme průměr libovolného stromu T. Vezmeme libovolný vrchol v "náležící" T a najdeme k němu nejvzdálenější vrchol w. Poté nalezneme k vrcholu w nejvzdálenější vrchol u. Pak diametr stromu T je roven vzdálenosti mezi vrcholy w a u.
Návod: Vytvořte ze stromu T kořenový strom s kořenem v centru c. Větví kořenového stromu T rozumíme každou komponentu grafu T-c. Délka větve je délka cesty z vrcholu c do nejvzdálenějšího vrcholu větve. Ukažte, že cesta z libovolného vrcholu v "náležící" V(T) do nejvzdálenějšího vrcholu ve stromu T vede přes centrum c.
Díky za nějakou radu
Offline
Stromy jsou trochu popisovane zde: http://matematika.havrlant.net/forum/vi … hp?id=1050
Neni to muj obor, tudiz nevim zda Ti to odpovi, jen si pamatuji ze se tady neco o stromech resilo ;)
Offline
jo díky. Už jsem tu ten příklad našel (http://matematika.havrlant.net/forum/vi … php?id=974), takže se omlouvám za můj spam.
Offline
Stránky: 1