1. diel - Úvod do teórie grafov

Čože ?? Matematika ??

Počkajte, som programátor, toto nepotrebujem.

.<>

Chápem, že nudněji asi článok začínať nemôže. Skúsim vás však presvedčiť, že matematika je nielen celkom rozumný štandard, ale aj veľmi praktická zručnosť. Prečo zrovna grafy? Grafy sú totiž veľmi mocný nástroj, ako vyjadrovať nejaké vzťahy, ukladať dáta či prehľadávať stavový priestor. Na začiatok aspoň niektoré príklady využitia grafov:

• Hľadanie najkratšej cesty
• Usporiadanie adresárov v Linuxe
• Určovanie maximálneho objemu dát, ktorý pretečie sietí
• Farbenie politickej mapy sveta
• Ukladanie objektov do stromovej štruktúry
• a ďalšie ...

Graf

Čo je to vlastne graf? Ak máte v hlave lineárne a kvadratické funkcie, tak na ne (pre tentokrát samozrejme) zabudnite. Naše grafy vyzerajú úplne inak.

Definícia

Definícia pre normálnych ľudí: Majme nejaký graf, ktorý je tvorený pomocou bodiek a čiar. Bodky sú vrcholy grafu a čiary sú jeho hrany. Hrana musí byť zakončená vrcholom z každej strany, inak to nie je hrana.

Ak máte radi matematiku, definície vyššie vo formálnejšom štýle by bola: Majme graf G = (V, E), kde (V, E) je usporiadaná dvojica prvkov takých, že V je množina vrcholov grafu G a E je množina hrán, ktoré spájajú vrcholy z V.

Ak nie ste oboznámení s matematickým postupom, tak len drobná vysvetlivka. Táto definícia v podstate hovorí, že graf je pre nás dôležitý skrze to, že poznáme vrcholy a hrany. Všimnime si, že je (väčšinou) jedno, ako tento graf nakreslíme. To je veľmi dôležité, v počítači nemusíme mať súradnice bodov či nič podobné, stačí nám mať uložený zoznam vrcholov a hrán.

Dva grafy nižšie sú v podstate identické (tzv. Izomorfné). Keď sa pozorne pozriete, graf má päť vrcholov az každého vedú dve hrany. Přeskládáním prvého dostanete druhý:

Čo môže byť vo vrcholoch a čo v hranách? To je na vás, grafy slúži vám, nie vy im.

Príklad č.1 - Rybičky

Ste riaditeľom obrovské firmy na dodávanie rybičiek v republike. Máte v počítači mapu najväčších miest. Medzi nimi povedú hrany, značiaci vaše logistické cesty. Každý vrchol (mesto) bude obsahovať počet obyvateľov, počet podnikov a veľkosť skladovacieho priestoru. Každá hrana obsahuje informácie o dĺžke cesty, pravdepodobnosti zápchy a mená vodičov, ktorí tieto cesty jazdia.

Príklad č.2 - Úradník

Ste vládny úradník a chcete si naplánovať dodanie všetkých hlasovacích lístkov čo najefektívnejšie. Vzhľadom na možné problémy s korupciou všetky lístkami tlačíte pri sebe v kancelárii. Prídu si ich vyzdvihnúť ozbrojené sily, ktoré ich budú prevážať na menšie a menšie úrady, až sa dostanú na obvodné políciu, ktorá je zanesie do schránky. Máte teda orientovaný graf, kde v hranách môžete uložiť informáciu o maximálnom množstve lístkov, ktoré sa zmestí do auta a počet vojakov strážiace konvoj. Vo vrcholoch môžu byť otváracej doby jednotlivých úradov a počet úradníkov.

Typy grafov

Teraz keď vieme, čo je to graf, pozrieme sa na najdôležitejšie typy grafov.

Cesta

Cesta je postupnosť vrcholov a hrán, kde existuje iba jeden spôsob, ako sa dostať z vrcholu V do vrcholu U:

Čiže je to vždy cik-cak dvojica vrchol, hrana, vrchol, hrana ... Je to veľmi jednoduchá štruktúra, nič moc k videniu, pohnite!

Kružnice

Kružnice už je oveľa zaujímavejšie. Môžeme ju definovať ako cestu, ktorej koncové vrcholy spojíme do jedného:

Tak napríklad si nakreslite trojuholník. To je nádherná kružnice. Vyjdete z vrcholu raz hranou a vrátite sa druhou. Samozrejme väčšinou máme v grafe väčšej kružnice, ale to na kráse tohto matematického vtipy nič nemení.

Strom

Strom je absolútne kľúčové štruktúra, ktorej sa budeme venovať podrobnejšie. Môžeme ho zadefinovať ako súvislý graf bez kružníc čiže graf, kde medzi každými dvoma vrcholmi existuje cesta. Je to tiež graf, kde existuje jeden koreň (anglicky root), ktorý nemá žiadneho predka a môže obsahovať potomkov. Posledný vrchol, ktorý nemá žiadneho potomka, sa označuje pojmom list (anglicky leaf).

Napríklad štruktúra adresárov na Linuxe má presne takýto model. Máme koreň /, z ktorého potom vychádzajú adresára bin/, etc/, tmp/ a ďalšie ...

To vyzerá napr. Takto:

Tu uvádzam strom vývoja jazykov z latinčiny. O dôvod navyše učiť sa stromy. A latinčinu

Strom má však oveľa viac využitie. Je to dobrá dátová štruktúra. Druhov stromov je naozaj celá rada a všetky spĺňajú jeho definícii + niečo naviac. B-stromy, B + -stromy, červeno-čierne stromy, binárne stromy, haldy atď ...

No a to je k stromu všeobecne všetko. Prekvapení? Tie najjednoduchšie nápady môžu byť aj elegantné i geniálny.

Úplný graf

Úplný graf na n vrcholoch je graf, v ktorom je každý vrchol prepojený so všetkými ostatnými.

napr .:

Podgraf

Podgraf grafu G je opäť graf, ktorý získame odobratím hrán alebo vrcholov. Prázdna množina, tj. Graf s 0 vrcholmi je podgraf ľubovoľného grafu.

Bipartitný grafy

Párny graf Gn,m je graf, ktorý môžeme rozdeliť na dve časti. Každá z týchto častí obsahuje len hrany do druhej, tj. Neexistuje hrana, ktorá by spájala dva vrcholy v jednej časti (partie).

Ďalšie delenie

Grafy môžeme deliť aj nasledujúcimi spôsobmi.

Orientovaný vs. neorientovaný graf

Orientovaný graf je graf, kde máme pridanou informáciu o tom, odkiaľ kam hrana vedie. Predstavte si mesto. Ak urobíte graf ulíc pre chodcov, tak určite bude graf neorientovaný. Chodec si môže ísť tam aj späť, ako sa mu zapáči. Ak urobíte graf ulíc pre vodičov áut, v meste je iste veľa jednosmeriek, a dokonca aj cesty je v podstate jednosmerná.

Spojitý vs. prerušovaný

Ako názov napovedá, jedná sa o to, či z každého vrcholu existuje cesta do iného. Ak áno, graf je spojitý. Spojité grafy sa dobre ukladajú do počítača, s prerušovaným je už o máličko väčšiu réžia.

Reprezentácia grafov

Teraz, keď už máme nejakú predstavu, ako graf vyzerá a čo robí, ponúka sa posledná otázka, ako ho uložiť do núl a jednotiek v počítači. Na to nie je jednoznačná odpoveď. Záleží na type grafu a čo s nimi chcete robiť. Ukážeme si dve najčastejšie reprezentácie grafu. Odporúčam sa pozrieť do priložených zdrojových kódov, kde priamo ukazujem konkrétne typy grafov a ich reprezentáciu.

Matice súslednosti

Pre Neorientované grafy budeme mať symetrickú maticu, kde Aij = 1 ak Vi susedí s Vj a 0 ak nie. Pre orientované grafy to bude nesymetrické. To, že susedí Vi s Vj neznamená, že susedí Vj s Vi. Teda to, že viete, ako sa dostať z X do Y po jednosmerke neznamená, že to viete aj naspäť.

Reprezentácie v poli

Jednoduché typy grafov, napr. Binárne stromy, tj. Kde každý uzol má práve 2 potomkov okrem listov, sa dajú efektívne uložiť v obyčajnom poli. Viete, že vrchol na pozícii i má potomkov na pozíciu 2i + 1 a 2i + 2. Tu máme príklad binárneho stromu, konkrétne haldy. Halda je dátová štruktúra, kde predok stromu je vždy menší ako potomok (koreň je minimum).

To je pre začiatok všetko. Samozrejme to nie je vyčerpávajúci popis všetkých možností. Hlavné je si uvedomiť jedno. Grafy nám dávajú nástroj, ako skladať dáta k sebe, nie povinnosť je trhať kamkoľvek môžeme. Striedmosť je hlavný cností programátora. Tak nech vám stromčeky kvitnú