Teorija grafov: Osnovne definicije

Teorija grafov je veja matematike, ki se uporablja v računalništvu in programiranju, ekonomiji, logistiki in kemiji.

Kaj je graf

Grafični sistemi se pogosto uporabljajo za opisovanje strukture sistemov. Elemente v njih predstavljajo krogi, pike, kvadrati itd., Povezave med elementi pa so črte ali puščice. Hkrati ni pomembno, kako so elementi upodobljeni, niti dolžina ali oblika linij pomembna - samo kateri elementi so povezani. Graf je torej par oblike (A, M), kjer je A končni niz tock, M pa je niz robov - linij, ki povezujejo nekaj tock.

Osnovni pojmi teorije grafov

Za usmerjen graf ali graf (glejte spodnjo sliko) so robovi usmerjeni, imenovani loki in so predstavljeni s puščicami. Lok se lahko označi z urejenim parom vozlišč, ki jih povezuje - začetnim in končnim.

Pri neusmerjenem grafu (glej spodnjo sliko) so robovi predstavljeni z vrsticami brez orientacije. V skladu s tem je par tock, ki jih povezuje rob, neurejen. Obe tocki sta konca roba.

Če so tocki a in b konca roba (ali zacetka in konca loka) grafa, potem rečemo, da so tocki a in b nalezljivi na ta rob (lok), tudi rob (lok) je vpet v tocke a in b. Če sta tocki a in b konca roba, se ju (a in b) imenuje sosednja.

Najpogosteje so grafi, katerih robovi so iste vrste, usmerjeni ali ne.

Če imajo robovi isti začetek in konec, potem se imenujejo več robov in graf, v katerem so prisotni, se imenuje multigraf.

Teorija grafov uporablja tudi pojem "zanke" - rob, ki gre na isti vrh. Graf, v katerem so zanke, se imenuje pseudograf.

Najpogostejši ne-usmerjeni grafi, ki nimajo več robov in brez zank. Takšni grafi se imenujejo navadni. Nimajo več robov, zato lahko določite rob in ustrezen par tock.

Vsako tocko grafa karakterizirajo:

• Nerazvitost. To je število lokov, ki prihajajo iz njega.
• Nerazvitost. To je število lokov, ki gredo v določeno točko.

Vsota pol stopinj vnosa grafika, kot tudi vsota pol-stopenj izida, je enaka skupnemu številu lokov grafa.

V neusmerjenem grafu je za vsako tocko značilna stopnja njegove tocke. To je število robov, ki so povezani z vrhom. Skupna vsota stopenj tock grafa je število robov, pomnoženo z dvema: vsak rob bo dal prispevek, ki je enak dvema.

Vrh s stopnjo 0 se imenuje izoliran.

Viseči vrh je vrh s stopnjo 1.

Teorija grafov imenuje prazen graf, v katerem ni nobenega roba. Celoten graf je navaden graf, v katerem so vsa 2 tocka sosednja.

Uteženi grafi so grafi, na katera so takoj dodeljena vozlišča ali robovi (loki) ali obema točkama in robovom (lokom), nekatere številke. Imenujejo se uteži. Druga slika prikazuje neusmerjeni graf, katerega robovi so uteženi.

Štetje: izomorfizem

Koncept izomorfizma se uporablja v matematiki. Še posebej, teorija grafov jo definira na naslednji način: dva grafa U in V sta izomorfna, če obstaja bijekcija med množico njihovih tock v teh grafih: vsaka 2 tocki v grafu U sta povezani z robom, ce in samo ce je isti v grafu V vozlišča (ki se lahko imenujejo drugače). Spodnja slika prikazuje dva izomorfna grafa, pri katerih je med tockami, pobarvanimi v istih barvah v prvem in drugem grafu, zgoraj opisana bijection.

Poti in cikli

Pot v neusmerjenem ali usmerjenem grafu je zaporedje robov, kjer se vsak naslednji začne na vrhu, na katerem se konča prejšnji. Preprosta pot je tista, v kateri so različna vsa vozlišča, razen, morda začetna in končna, ter robovi. Cikel v grafu je pot, katere začetna in končna točka se ujemata in ki vključuje vsaj en rob. Cikel v neusmerjenem grafu je pot, ki vsebuje vsaj tri različne robove. V drugi sliki je cikel na primer pot (3, 1), (6, 3), (1, 6).

Teorija grafov v programiranju se uporablja za izdelavo graf-shem algoritmov.