!!! Na uvedených souradnicích cache
nehledejte !!!
TEORIE GRAFU
Obecne
Teorie grafu je veda,
která zkoumá vlastnosti struktur zvaných grafy. Ty jsou
tvoreny vrcholy, které jsou vzájemne spojené hranami.
Znázornuje se obvykle jako množina bodu spojených carami.
Pomocí grafu lze reprezentovat struktury a úlohy z
nejruznejších oboru. Struktura grafu muže být rozšírena o
ohodnocení hran (také oznacováno jako váha; muže reprezentovat
délku, náklady na presun, pruchodnost apod.) nebo vrcholu.
Výsledkem je model reálné síte. Takové modely se používají pro
analýzu dopravy nebo pocítacových sítí (jako napr.
internetu).
Nekteré z úloh, které reší Teorie grafu jsou napríklad: hledání
nejvetšího úplného podgrafu – tzv. problém kliky, hledání nejvetší
nezávislé množiny,
problém obchodního cestujícího,
problém ctyr barev nebo hledání
minimální kostry grafu.
Leonhard Euler
Tradicne se za
zakladatele teorie grafu považuje Leonhard Euler, který roku
1736 prokázal nerešitelnost známé úlohy o sedmi mostech v
Königsbergu (více o tomto problému
zde). Cílem bylo vyjít z libovolného místa,
projít po každém moste práve jednou a vrátit se zpet do
výchozího místa. To by znamenalo, že je v takovém grafu Euleruv
cyklus. Je ale prokázané, že takový to cyklus lze vytvorit pouze
v prípade, že každý uzel je spojen s ostatními uzly sudým poctem
hran (uzavrený Euleruv tah).
Príklad nápadne pripomíná velice známý hlavolam Jak nakreslit
domecek jedním tahem. V tomto príklade se vyskytuje tzv. otevrený
Euleruv tah. Tento tah zarucí, že pokud v grafu existují presne dve
místa, z nichž vychází lichý pocet spojnic, lze tento graf
nakreslit jedním tahem, pricemž zacneme v jednom z techto dvou míst
a ve druhém skoncíme.
Leonhard Paul Euler je považován za nejlepšího matematika 18.
století a za jednoho v nejlepších matematiku vubec. Asi nejznámejší
pojem, který Euler zavedl, je Eulerovo císlo (znaceno písmenem
"e"), které je též oznacováno jako základ prirozených logaritmu.
Zde najdete úplný výcet pojmu pojmenovaných
po Leonhardu Eulerovi.
Problém obchodního
cestujícího
Problém obchodního cestujícího (Traveling Salesman Problem) je
obtížný diskrétní optimalizacní problém, matematicky vyjadrující a
zobecnující úlohu nalezení nejkratší možné cesty procházející všemi
zadanými body na mape. Tato úloha patrí mezi tzv. NP-úplné úlohy,
tzn. v obecném prípade není známo ani jak nalézt presné rešení v
rozumném case a dokonce ani zda vubec muže existovat algoritmus,
který takové rešení najde v case úmerném nejaké mocnine poctu uzlu.
Clayuv matematický institut (CMI) v Cambridgi v Massachusetts
vypsal odmenu 1 milion dolaru za vyrešení této hádanky.
Príklad je jednoduše pochopitelný. Jedná se o jediný ze sedmi
matematických príkladu soucasnosti, kde matematik Keith Devlin
uvádí, že má šanci i laik s dobrým nápadem. Možná je potreba nová
myšlenka a typ pocítace fungující na úplne jiném principu než dnes.
Odmena je vypsána za samotné vyrešení i za dokázání, že príklad
zjednodušit nelze a žádný jednodušší zpusob, jak velké množství
kombinací proverit, neexistuje. V tomto prípade by došlo k obrovské
úspore energie a casu mozku, které by se již problémem nemusely
zabývat. zdroj:
idnes.cz
Optimální spojení
míst
V úlohách tohoto typu hledáme minimální (respektive maximální)
kostru grafu, tj. kostrou grafu, v níž bude soucet ohodnocení
vybraných hran minimální (respektive maximální). První optimální
algoritmy pro hledání minimální kostry grafu sestavili v 60. letech
20. století J.B.Kruskal a R.C. Prim.
Úloha:
Cacher Vilík se rozhodl založit nocní cache. Vyrazil tedy do lesa,
oznacil si stromy, na které umístí svetélka a jejich rozmístení a
vzdálenosti zakreslil do plánku, který vidíte na obrázku. Potrebuje
ke každému stromu natáhnout kabel, kterým povede proud. Protože je
ale student a snaží se ušetrit co nejvíc penez za použitý kabel,
poprosil svou kamarádku Máju, která se ve škole ucila Teorii grafu,
aby mu pomohla tento problém vyrešit a najít tak minimální kostru
grafu. Mája ješte stacila Vilíkovi poslat následující SMSku: Kup
490m kabelu, stací použít Kruskaluv, Boruvkuv nebo Jarníkuv
algoritmus a je to snadné ;). Pak ale náhle zmizela. Pomužete
Vilíkovi urcit, kudy povede kabel?
Zadání pro nalezení souradnic:
Až sestavíte kostru grafu, použité hrany vypište a setritte
vzestupne (císla, která jsou napsaná u jednotlivých hran, seradte
od nejmenšího k nejvetšímu) a ve stejném smeru priradte císlum
písmena abecedy (nejnižšímu císlu priradíte písmeno A, nejvyššímu
písmeno CH).
Cache se nachází na následujících
souradnicích:
N
49°21.(G*10+A/5)
E 014°51.(D+E+2*F-C+B/2)