Grafovi - osnovni pojmovi

Graf je apstraktni matematički objekat.
Neformalno govoreći, grafovi su sastavljeni od tačaka, odnosno čvorova i linija među njima, odnosno grana.
Graf G je uređen par (V,E) gde skup čvorova obeležavamo sa V , a skup grana sa E.
Uobičajeni način da se predstave grafovi je slika u ravni.

Primer: Odrediti čvorove i grane grafova koji se nalaze na slici iznad ?

Rešenje:
1) V = {A, B} , E = { (AB) }
2) V = {A,B,C,D} , E = { (AB), (AD), (BC), (CD) }
3) V = {A,B,C,D} , E = {(AB), (AC), (AD), (BC), (BD), (CD)}

Stepen čvora U je broj grana koje su sa čvorom U incidentne. Primer: Odrediti stepene čvorova:

Rešenje: d(A) = 3, d(B) = 2, d(C) =2 , d(D) = 2, d(E) = 3.

Graf je regularan ako su svi čvorovi istog stepena. Čvor stepena nula naziva se izolovani čvor.
Multigraf je graf kod koga između dva čvora postoji više od jedne grane.

Neorjentisani graf:

Orjentisani graf (digraf) : ( grana e ima početni čvor u V a krajnji u U).

Graf G = (V,E) je podgraf grafa G1 = (V1,E1) akko V1⊆V i E1⊆E. Ako je V1=V tada se graf G1 naziva razapinjući podgraf grafa G. Razapinjući (pod)graf G1 sadrži sve čvorove koje sadrži graf G. Graf je povezan ako postoji put između bilo koja dva različita čvora.

Ako je početni čvor ujedno i krajnji, takav put se naziva kontura.

Težinski graf je graf u kome nas ne zanimaju samo čvorovi i grane već i mogućnosti stizanja iz tačke A u tačku B i to na najbolji mogući način. Najbolji način zavisi od problema koji treba rešiti, to je najkraći put, nekada najjeftiniji, najbezbedniji, put na kome se troši najmanje energije i sl. Iz tih razloga svakoj grani se dodeljuje realan broj, njegova težina, odnosno mera.