Teorija grafova

Teorija grafova jedna je od pododjeljaka matematike, čija je glavna obilježja geometrijska metoda u proučavanju predmeta. Smatra se da je njegov osnivač poznati matematičar

Korištenje teorije grafova do kraja 19. stoljeća svedeno je na rješavanje zabavnih problema i nije privuklo značajnu opću pažnju. Počevši od 20. stoljeća, kada je teorija grafova je formirana kao samostalna matematičke discipline, to je naširoko koristi u područjima kao što su kibernetike, fizike, logistike, programiranje, biologije, elektronike, prometa i komunikacijskih sustava.

Osnovni pojmovi teorije grafova

Graf je osnovni. U terminologiji se može doći do takvog koncepta kao mreže identične grafikonu. Zadnje - je ne-prazna broj bodova, to jest, vrhovi i dužine, odnosno rebara, oba kraja od kojih odgovaraju određenom broju bodova. Teorija grafova ne daje određeni smisao u vrijednostima rubova i vrhova. Na primjer, gradovi i ceste koje ih povezuju, gdje su prvi vrh grafikona, a drugi - rubovi. U teoriji je veća važnost za lukove. Ako se rubovi imaju smjer, to se zove luk, ako se graf s usmjerenim rubovima, to se zove digraf.

U terminologiji teorije, ističu se i sljedeći pojmovi:

Subgraf je grafikon, a svi rubovi i vrhovi su među vrhovima i rubovima.

Povezan je grafikon koji ima lanac koji ih povezuje za dva različita vrha.

Ponderirani povezani grafikon je onaj čija je težinska funkcija dana.

Stablo je povezani grafikon bez ciklusa.

Kostur je subgraf koji je stablo.

Na slici grafikona u ravnini definirane oznake se koristi: odabrani vrh točka odgovara osnovnoj površini i da je rub između vrhova, odgovarajuće točke su spojeni segment. Ako je grafikon orijentiran, ovi segmenti zamjenjuju se strelicama.

Ali ne usporedite sliku grafikona s njom, tj. S apstraktnom strukturom, jer jedan grafikon može imati više od jednog grafičkog prikaza. Dajemo crtež na ravnini kako bismo vidjeli koji su parovi vrhova povezani rubovima i koji nisu.

Među nekim problemima teorije grafova, postoje:

1. Zadatak najkraćeg lanca (zamjena opreme, postavljanje ambulante i telefonskih stanica).
2. Problem maksimalnog protoka (naručivanje kretanja u dinamičnoj mreži, raspodjela posla, organizacija kapaciteta).
3. Zadatak premaza i pakiranja (postavljanje točaka otpreme).
4. Bojanje na grafikonima (položaj memorije na elektroničkim računalima).
5. Komunikacija mreža i grafova (stvaranje komunikacijske mreže, analiza komunikacijskih mreža).

Trenutačno je nemoguće programirati većinu problema bez poznavanja teorije grafikona. To olakšava i lakše raditi s računalom.

Programiranje koristi mnogo struktura i univerzalnih metoda za rješavanje problema, a jedna od njih je i teorija grafova. Njegova je vrijednost teško predvidjeti. Teorija grafikona u programiranju olakšava pronalaženje informacija, optimizira programe, pretvara i distribuira podatke. Kroz teoriju algoritama proizlazi mogućnost njihove uporabe u procjenama za specifične zadatke za obavljanje modifikacija algoritma, bez smanjenja stupnja pouzdanosti matematičkih konačnih verzija programa.

Važna imovina kontrolnog sustava ili modela je zbirka binarni odnosi kada upisujete radnje i podatkovne jedinice. Te su strukture jedini dijelovi programa i informacije koje pretvaraju. Dakle, grafikoni su osnova konstrukcije za programera.