Teorija grafov

Teorija grafov je eden od podpodročij matematike, katerega glavna značilnost je geometrijska metoda pri preučevanju predmetov. Njegova ustanoviteljica se šteje za 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 določenega smisla v 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 ima rob smer, ima ime loka, če je graf z orientiranimi robovi, se imenuje digraph.

V terminološki terminologiji 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 povezan graf, brez ciklov.

Skelet je podgraf, ki je drevo.

Ko je grafa narisana na ravnini, 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. Navede se risba na ravnini, da bi videli, kateri pari črt je povezan z robovi in ​​ki niso.

Med nekaterimi problemi teorije grafov obstajajo:

1. Naloga najkrajše verige (zamenjava opreme, namestitev reševalnih vozil in telefonskih postaj).
2. Problem največjega pretoka (naročanje gibanja v dinamičnem omrežju, porazdelitev dela, organizacija zmogljivosti).
3. Naloga premazov in embalaže (namestitev odpremnih točk).
4. Barvanje v grafih (namestitev 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 olajša delo 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 omogoča preprosto 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 zbirka binarni odnosi pri vnosu dejanj in podatkovnih enot. Te strukture so edini deli programov in informacije, ki jih pretvarjajo. Zato so grafi osnova konstrukcije za programerja.