Teorija grafov

Teorija grafov je eden od podpodročij matematike, katerega glavna značilnost je geometrijska metoda pri preučevanju predmetov. Ustanovitelj tega je znani matematik L. Euler.

Uporaba teorije grafov do konca 19. stoletja se je zmanjšala na reševanje zabavnih problemov in ni pritegnila pomembne splošne pozornosti. Od 20. stoletja, ko se je teorija grafov razvila v samostojno matematično disciplino, je na področjih znanosti našla široko uporabo kot kibernetika, fizika, logistika, programiranje, biologija, elektronika, transport in komunikacijski sistemi.

Osnovni pojmi teorije grafov

Graf je osnovni. V terminologiji se lahko tak koncept zgodi kot omrežje, ki je enako grafu. Slednje je ne-prazno število točk, to pomeni, tocke in segmente, to je robove, katerih oba konca ustrezata danemu številu točk. Teorija grafov nima dokončnega pomena pri vrednostih robov in tock. Na primer, mesta in ceste, ki jih povezujejo, kjer so prvi vrhovi grafa, in drugi - robovi. Večji pomen v teoriji dajejo luknjam. Če rob ima smer, potem ima ime loka, če je graf z orientiranimi robovi, se imenuje digraph.

V terminologiji teorije izstopajo tudi naslednji koncepti:

Podgraf je graf, katerega robovi in tocki so med vrati in robovi.

Povezani graf je tisti, ki ima verigo, ki ju povezuje za dve različni točki.

Uteženi povezani graf je tisti, katerega funkcija teže je podana.

Drevo je povezani graf brez ciklov.

Skelet je podgraf, ki je drevo.

Ko je graf na ravnini narisan, se uporabi določena oznaka: izbrana verteza ustreza točki na najpreprostejši površini in če je med vrhnjimi robovi, se ustreznim točkam poveže segment. Če je grafikon usmerjen, se ti segmenti nadomestijo s puščicami.

Ampak ne primerjajte slike grafa z njim, to je z abstraktno strukturo, saj lahko enemu grafu dobimo več kot eno grafično predstavitev. Na risbi je podana risba, da bi videli, kateri pari vrhov so povezani z robovi in ki niso.

Med nekaterimi problemi teorije grafov so:

1. Naloga najkrajše verige (zamenjava opreme, namestitev reševalnih vozil in telefonskih postaj).
2. Problem največjega pretoka (naročanje prometa v dinamičnem omrežju, porazdelitev dela, organizacija zmogljivosti).
3. Naloga premazov in embalaže (namestitev odpremnih točk).
4. Barvanje v grafih (postavitev pomnilnika na elektronske računalnike).
5. Komunikacija omrežij in grafov (oblikovanje komunikacijskega omrežja, analiza komunikacijskih omrežij).

Trenutno je nemogoče programirati večino težav, ne da bi poznal teorijo grafov. To olajša in lažje dela z računalnikom.

Programiranje uporablja veliko struktur in univerzalnih metod za reševanje problemov, ena od njih pa je teorija grafov. Njena vrednost je težko preceniti. Teorija grafov v programiranju olajša iskanje informacij, optimizacijo programov, pretvarjanje in distribucijo podatkov. Zahvaljujoč algoritmom teorije jih je mogoče uporabiti in ovrednotiti pri reševanju specifičnih problemov, spremeniti algoritem brez zmanjšanja stopnje matematične gotovosti končne različice programa.

Pomembna lastnost nadzornega sistema ali modela je niz binarnih odnosov pri zbiranju dejanj in podatkovnih enot. Te strukture so edini deli programov in informacije, ki jih pretvarjajo. Zato so grafi osnova za konstrukcijo za programerja.