Te u zagrebu fakultet organizacije I informatike

6 

 

zabavi  rukovali,  onda  se  radi  o  neusmjerenom  grafu,  jer,  zaista,  ako  se  osoba  A  rukovala  s 

osobom  B  onda  vrijedi  i  obrnuto,  zbog  čega  je  ta  veza  simetrična.  Ako  pak  veza  predstavlja 

činjenicu da li osoba Apoznaje osobu B, onda će se raditi o usmjerenom grafu jer ovakva vrsta 

povezanosti  nije  nužno  simetrična.  I  zaista,  ako  osoba  A  zna  za  osobu  B  nije  nužan  slučaj  da 

osoba B zna za osobu A.  

 

3.2.  Tipovi grafova 

 

3.2.1  Neusmjereni graf 

 

Kod ovakvog grafa bridovi nemaju orijentacije, što znači da nisu zadani ureĎenim parom 

čvorova koje spajaju, već samo skupom dvaju čvorova {v

i

, v

j

}. 

 

3.2.2  Usmjereni graf 

 

Usmjereni  graf  ili  digraf  je  ureĎeni  par  D=(V,A)  gdje  ve  predstavlja  skup  čvorova,  a 

ureĎene parove iz skupa čvorova koje nazivamo usmjerenim bridovima. Brid a = (x,y) smatra se 

usmjerenim  od  x  do  y;  y  je  direktni  sljedbenik  x,  a  x  je  direktni  prethodnik  y.  Brid  koji 

označavamo s (y,x) nazivano invertirani brid (x,y). Jednostavan prikaz usmjerenog grafa koji se 

sastoji od tri vrha i tri usmjerene veze možemo vidjeti na slici 3.2. 

 

. 

 

Slika 3.2 Usmjereni graf 

 

 

---

7 

 

 

3.2.3 

Miješani graf

 

 

Miješani  graf  je  graf  u  kojem  su  neki  bridovi  usmjereni,  a  neki  ne,  a  piše  se  kao 

usmjerena trojka  G=(V,E, A) gdje je V skup čvorova, E predstavlja skup neusmjerenih bridova, 

dok A predstavlja skup ureĎenih parova iz skupa čvorova, odnosno usmjerene bridove. 

 

3.2.4  Multigraf 

 

Petlje (refleksivne veze) su bridovi, usmjereni ili neusmjereni, kojima je početni i završna 

točka  isti  čvor.  One  mogu,  ali  i  ne  moraju  biti  dozvoljene  ovisno  o  primjeni.  Izraz  multigraf 

označava da je riječ o grafu u čijem su prikazu dozvoljeni  višestruki bridovi, te slučaj kada su 

dozvoljene i petlje. 

 

3.2.5  Jednostavni graf 

 

Ako  nije  naznačeno  drukčije,  kada  se  spomene  graf  pretpostavlja  se  da  je  riječ  o 

jednostavnom  grafu.  To  je  neusmjereni  graf  u  kojem  nema  petlji  i  nema  više  od  jedne  veze 

izmeĎu  dva  čvora.  Kod  jednostavnog  para  svaki  je  brid  zadan  parom  različitih  čvorova.  Kod 

ovakvih  grafova  s  n  čvorova,  svaki  čvor  ima  broj  veza  manji  od  n.  Slikom  3.3.  prikazujemo 

jedan jednostavan graf s tri vrha.  

 

 

Slika 3.3 Jednostavan graf (ujedno i neusmjereni graf)

 

 

---

8 

 

3.2.6 

Težinski grafovi

 

 

Postoje  slučajevi  kada  je  potrebno  pojedinom  bridu  dodijeliti  odreĎenu  (brojčanu) 

vrijednost.  One  mogu  predstavljati,  na  primjer,  cijene,  udaljenosti,  kapacitete  ili  slično.  Tada 

govorimo težinskim grafovima. Težina grafa je suma vrijednosti dana svakom pojedinom bridu. 

 

3.3. 

Susjedni čvorovi i bridovi

 

 

 

Čvorovi  v

i

  i  v

j

  su  susjedni  ako  su  povezani  zajedničkim  bridom,  a  bridovi  e

i

  i  e

j

  su, 

analogno  tome,  susjedni  ako  imaju  zajedničku  krajnju  točku  odnosno  zajednički  čvor.  Na 

temelju susjednih čvorova i bridova izraĎujemo matricu incidencije [Biggs, 1993., str. 7]. 

 

3.4.  Matrica incidencije 

 

 

Neka je graf G definiran skupom čvorova {v

1

, v

2

,...,v

n

} i skupom bridova {e

1

, e

2

,...,e

m

}. 

Za svaki i, j (1 ≤ i ≤ n, i 1 ≤ j ≤ n) definiramo: 

 

a

ij

 = 

 

1, ?????????????????? ?????????????????????????????????????????? ???????????????????????? ????????????????????????đ?????? ??????????????????ℎ

0, ?????????????????? ???????????????????????? ???????????? ??????????????????????????????????????????

  

 

Matrica A = [a

ij

] predstavlja matricu incidencije grafa G [Barabási, 2012., str. 30].

 

 

Računalni  programi  koriste  matrice  incidencije  za  pohranu  informacija  o  susjednim 

čvorovima i bridovima te na temelju toga crtaju zadani graf. Matrice usmjerenih i neusmjerenih 

mreža  ponešto  se  razlikuju,  kao  što  to  vidimo  u  dolje  navedenom  primjeru.  Kada  govorimo  o 

matrici susjednosti za usmjerene mreže potrebno je napomenuti da: 

A

ij

= iznosi 1 kada postoji veza koja kreće od čvora j prema čvoru i; 

A

ij

 = iznosi 0 ako čvorovi i i j nisu povezani jedan s drugim. 

Matrica  incidencije  za  neusmjerene  mreže  ima  dvostruko  definirane  veze.  Na  primjer, 

veza  izmeĎu  čvora  v

1

  i  čvora  v

2

  prikazan  je  kao  A

12

  i  jednak  je  1,  a  isto  vrijedi  i  za  A

21

  koji 

takoĎer označava vezu izmeĎu čvorova v

1

 i v

2

 i iznosi 1 [Barabási, 2012., str. 31]. 

Prema  tome,  matrice  incidencije  za  usmjerene  grafove  biti  će  simetrične.  Ipak,  kada  je 

riječ o matricama susjednosti za usmjerene grafove, to neće biti slučaj, kao što vidimo na slici 

3.4. 

---