Teorija grafova je grana matematike koja se koristi u računalnoj znanosti i programiranju, ekonomiji, logistici i kemiji.
Često se grafički sustavi koriste za opisivanje strukture sustava. Elementi u njima su predstavljeni krugovima, točkama, kvadratima itd., A veze između elemenata su linije ili strelice. Istodobno, nije važno kako su elementi prikazani, ni duljina ili oblik crta važni - samo koji su elementi povezani. Dakle, graf je par oblika (A, M), gdje je A konačan skup vrhova, a M skup rubova - linija koje povezuju neke vrhove.
Za usmjereni graf ili graf (vidi sliku ispod), rubovi su orijentirani, nazivaju se lukovima i prikazani su strelicama. Luk se može označiti sređenim parom vrhova koje povezuje - početnim i konačnim.
Za neusmjereni graf (vidi donju sliku), rubovi su prikazani linijama bez orijentacije. Sukladno tome, par vrhova koje se rub povezuje je neuređen. Oba ova vrha su krajevi ruba.
Ako su vrhovi a i b krajevi jednog ili više rubova (ili početka i kraja luka), onda kažemo da su vrhovi a i b upadni na taj rub (luk), a rub (luk) je uvučen u vrhove a i b. Ako su vrhovi a i b krajevi ruba, onda se oni (a i b) nazivaju susjedni.
Najčešće razmatramo grafikone čiji su rubovi istog tipa - orijentirani ili ne.
Ako rubovi imaju isti početak i kraj, onda se nazivaju višestrukim rubovima, a graf u kojem su prisutni naziva se multigraf.
Teorija grafova također koristi pojam "petlje" - rub koji ide i postavlja se na isti vrh. Graf u kojem postoje petlje naziva se pseudograf.
Najčešći ne-orijentirani grafovi koji nemaju višestruke rubove i nemaju petlje. Takvi se grafikoni nazivaju obični. Oni nemaju više rubova, tako da možete identificirati rub i odgovarajući par vrhova.
Svaki vrh dijagrama karakterizira:
Zbroj polu-stupnjeva ulaza digrafa, kao i zbroj polustupnjeva ishoda, jednaki su ukupnom broju lukova grafikona.
U neusmjerenom grafu svaki je vrh karakteriziran stupnjem njegovog vrha. To je broj rubova koji su povezani s vrhom. Ukupni zbroj stupnjeva vrhova grafa je broj rubova pomnožen s dva: svaki rub će dati doprinos koji je jednak dva.
Vrh s stupnjem 0 naziva se izoliran.
Viseći vrh je vrh s stupnjem 1.
Teorija grafova naziva prazni graf u kojem nema ni jednog ruba. Kompletan graf je obični grafikon u kojem su svaka dva vrha susjedna.
Vagani grafikoni su grafovi, kojima su odmah dodijeljeni vrhovi ili rubovi (lukovi) ili oba vrha i rubovi (lukovi), neki brojevi. Nazivaju se utezi. Druga slika prikazuje neusmjereni grafikon čiji su rubovi ponderirani.
Pojam izomorfizma koristi se u matematici. Konkretno, teorija grafova definira ga na sljedeći način: dva grafikona U i V su izomorfna ako postoji bijekcija između skupova njihovih vrhova u tim grafovima: svaka dva vrha u grafikonu U povezana su s rubom ako i samo ako je isti u grafu V vrhovi (koji se mogu nazivati drugačije). Na donjoj slici prikazana su dva izomorfna grafa, u kojima se između vrhova obojenih u istim bojama u prvom i drugom grafikonu nalazi gore opisana bijekcija.
Put u neusmjerenom ili orijentiranom grafu je slijed rubova, gdje svaki sljedeći počinje na vrhu na kojem prethodni završava. Jednostavan put je onaj u kojem su svi vrhovi, isključujući, možda, početni i konačni, i rubovi različiti. Ciklus u grafu je put koji se poklapa s početnim i konačnim vrhovima i koji uključuje barem jedan rub. Ciklus u neusmjerenom grafu je putanja koja sadrži najmanje tri različita ruba. U drugoj slici, ciklus je, na primjer, put (3, 1), (6, 3), (1, 6).
Teorija grafova u programiranju koristi se za konstrukciju grafičkih shema algoritama.