Teorija grafova: Osnovne definicije

28. 5. 2019.

Teorija grafova je grana matematike koja se koristi u računalnoj znanosti i programiranju, ekonomiji, logistici i kemiji.

Što je graf

Č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.

Osnovni pojmovi teorije grafova

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. teorija grafova

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. osnovni pojmovi teorije grafova

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:

  • Pola ishod. To je broj lukova koji izlaze iz njega.
  • Indegree. To je broj lukova koji ulaze u zadani vrh.

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.

Brojevi: izomorfizam

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. teorija grafova u programiranju

Putevi i ciklusi

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.

Pročitajte prethodno

Što je denaturacija proteina