Algoritmi za rad sa grafovima, izračunavanje nekih karakteristika grafa

Osnovni pojmovi

Stepen čvora

Stepen   d( v )   čvora v je broj grana susednih čvoru v (broj grana koje direktno povezuju čvor v sa nekim drugim čvorom).

U usmerenom grafu razlikuju se ulazni stepen (broj grana čiji kraj je čvor v) i izlazni stepen (broj grana za koje je čvor v početak).
slika4
Slika 4

Na slici 4, stepen čvorova je:
 
čvor  stepen ulazni stepen izlazni stepen
1 2 0  2
2 3 2 1
3 3 2 1
4 2 1 1

Bipartitivni graf

Bipartitivni graf je graf čiji se čvorovi mogu podeliti na dva disjunktna podskupa tako da u grafu postoje samo grane između čvorova iz različitih podskupova.
Na primer, slika 5 prikazuje bipartitivni graf sa skupom čvorova koga čine dva disjunktna podskupa {1, 2} i {3, 4, 5}, gde svaka grana grafa povezuju čvorove iz različitih podskupova.
slika5
Slika5

Put

Put od v1 do vk je niz čvorova v1, v2, . . . ,vk povezanih granama (v1, v2), (v2, v3), . . . , (vk-1, vk )
Obično se i ove grane smatraju delom puta. Put je prost, ako se svaki čvor pojavljuje u njemu samo jednom.

Čvor je u dostižan iz čvora v ako postoji put (usmeren/neusmeren) od v do u. Po definiciji, čvor u je dostižan iz u.
 

v3, e1, v1, e2, v4, e5, v2, e6, v5, e3, v1, e2, v4 ( grana e2 se pojavila dva puta)
slika6
Slika 6
 

1, c, 3, f, 4, e, 2, d, 3 ( čvor 3 se pojavio dva puta)
slika7
Slika 7

Ciklus

Ciklus je put čiji se prvi i poslednji čvor poklapaju. Ciklus je prost, ako, sem prvog i poslednjeg čvora se niti jedan drugi čvor ne pojavljuje u putu dva puta.
Prema slici 8 ciklusi su reprezentovani nizom čvorova slika
Slika 8

Stablo ili drvo

je povezani graf koji (u svom neusmerenom obliku) ne sadrži cikluse.
stablo
Stablo

Hamiltonov ciklus ili Hamiltonov put

je prosti ciklus ili put u kom se svaki čvor grafa pojavljuje tačno jednom.
Na primer: na slici 9 (slici 3) niz čvorova A, B, C, D, E, A specificira Hamiltonov ciklus.
slika9
Slika 9

Ojlerov ciklus

je ciklus koji svaku granu grafa sadrži tačno jednom.

Ojlerov graf je povezan graf čiji čvorovi imaju paran stepen.

Graf na slici 10 sadrži Ojlerov ciklus predstavljen nizom čvorova 1, 2, 3, 5, 4, 1, 3, 4, 2, 5, 1.
slika10
Slika 10

Podgraf

Graf H=(U,F) je podgraf grafa G=(V,E) ako je skup U podskup skupa V i ako je skup F podskup skupa E.

Graf H sa slike 12 je podgraf grafa G prikazanog na slici 11.
slika11
Slika 11
slika12
Slika 12

Indukovani podgraf

  Graf G=(V,E) ima indukovani podgraf H=(U,F) ako H je podgraf grafa G tako da U je podskup od V i skup grana F sadrži sve grane skupa E tako da oba čvora grane su iz skupa čvorova U. Graf sa slike 14a ima kao indukovani podgraf graf sa slike 14b.

images/slikaa
Slika 14 a
images/slikab
Slika 14 b

Zadaci koji se odnose na grafove

1. Implementirati algoritam koji ce za graf G=(V,E) kreirati listu topološki uređenih čvorova grafa. Graf je zadat matricom povezanosti (npr. a[i][j]=1, ako postoji grana (i,j), inace a[i][j]=0) tako da ispise cvorove u redosledu obilaska.

Problem topološkog sortiranja je problem formiranja rasporeda čvorova u grafu G tako da ako se svi čvorovi grafa numerišu brojevima
od 1 do n=|V|, onda ako čvor v je numerisan sa k svi čvorovi do kojih postoji usmeren put iz v imaju numeraciju veću od k.

U glavi 6.4 knjige je prikazan algoritam za topološko sortiranje acikličkog usmerenog graga G.

  Algoritam TOPSORT(G)

 ulaz: G

izlaz: v.Num (numeracija cvora v u toploskom redosledu)

  {

        pomocu DFS obilaska stabla naci ulazni stepen svakog cvora, tj. v.InDeg

      Broj=0;  /*tekuci redni broj*/

      for(i=1; i<=n; i++)    if (v[i].InDeg==0) staviti v[i] u listu;

      while (lista nije prazna)
        {

            uzmi cvor v sa liste;

            Broj++;     v.Num=Broj;

            for svaka grana (v,w)
                { w.InDeg--;
                  if (w.InDeg==0)  stavi w u listu;
                }

        }

 }

 Algoitam toploškog sortiranja je složenosti O( |E| + |V| ), tj. linearne složenosti kod grafova.


#include <stdio.h>
#define MAX 10  /*maksimalan broj cvorova*/

void topSortPoseti(int x, int a[][MAX], int n, int m[], int lista[], int *k);
/*obilazak grafa sa n cvorova zadatog matricom a pocev od neposecenog cvora x;
pri obilasku u nizu markiranih cvorova m vrednost clana m[x] ce postati 1, kad se poseti cvor x.
Kada se za cvor x zavrsi poseta svih nemarkiranih susednih cvorova, 
cvor x se dodaje u niz lista na poziciju *k */

void topsort(int a[][MAX], int n, int lista[]); 
/*DFS obilazak grafa G sa na cvorova zadatog matricom povezanosti a;
 formiranje topoloskog redosleda cvorova u nizu lista*/

void ucitaj_matricu(int a[][MAX], int n); //ucitavanje grana grafa sa stdin
void trampa(int a[], int i, int j); //trampa clana a[i], a[j]

main()
{int a[MAX][MAX];
 int n; //broj cvorova grafa
 int lista[MAX];

  scanf("%d", &n);
  ucitaj_matricu(a,n);
  topsort(a, n, lista);
}

void topSortPoseti(int x, int a[][MAX], int n, int m[])
{
   int y; //cvor koji je u grafu potencijalni sused cvora x 

  m[x]=1;   //markira se cvor x kao posecen
 
//ako postoji susedni cvor y koji nije markiran(m[y]=0), rekurzivno se poziva topSortPoseti za y
for (y=0; y<n; y++)
  if( m[y]==0 && a[x][y]==1) topSortPoseti(y, a, n, m, x, &k);
 lista[*k]=x; //ubacuje se cvor u topoloski uredjenu listu na kraj
k++; //priprema za prihvat sledeceg clana liste
}

void topsort(int  a[][MAX], int n, int lista[])
{
   int x, m[MAX],k; 
   /*cvor grafa x, 
     niz markiranih (posecenih) cvorova m, 
     k je index clanova topoloski uredjene liste cvorova */
     
  k=0;
  for (x=0; x<n; x++) m[x]=0; //na pocetku su svi cvorovi neposeceni
 
  for (x=0; x<n; x++) 
    if (m[x]==0) topSortPoseti(x, a, n, m, lista, &k); //ako x nije posecen, pokrenuti topSortPoseti iz x

//kako smo cvorove dodavali u f-ji topSortPoseti na kraj lista, a ne na pocetak niza lista, mora se niz lista obrnuti
for(x=0; x<n/2; x++) trampa(lista, x, n-x-a);  //trampe se prvi i poslednji, drugi i pretposlednji,...

}

void ucitaj_matricu(int a[][MAX], int n)
{
  int i, j;
  for (i=0; i< n; i++)
  for(j=0; j<n; j++) a[i][j]=0;

  while (scanf("(%d,%d)", &i, &j) != EOF) a[i][j]=1;
}

void trampa(int a[], int i, j)
{
  int pom=a[i]; a[i]=a[j]; a[j]=pom;
}

2.  Zadat je aciklički usmeren graf G=(V,E).  Konstruisati algoritam linearne složenosti koji utvrđuje da li u G postoji neki prost put koji sadrži sve čvorove grafa.

  REŠENJE:

      Put je prost, ako se svaki čvor pojavljuje u njemu samo jednom.

Hamiltonov put je prosti put u kom se svaki čvor grafa pojavljuje tačno jednom.

 U ovom zadataku zahtev je da se konstruiše algoritam za pronalazak Hamiltonovog puta u grafu G.

  Ideja je da se konstruiše topološki redosled čvorova grafa G, a potom se proveri da li postoji put tako što se proveri da li susedni čvorovi u topološkom redosledu jesu putno povezani. Ukoliko su povezani, onda Hamiltonov put čine topološki uređeni čvorovi.

U glavi 6.4 knjige je prikazan algoritam za topološko sortiranje acikličkog usmerenog graga G.

 Algoritam toploškog sortiranja je složenosti O( |E| + |V| ), tj. linearne složenosti kod grafova.

3. Neka G=(V,E) je neusmeren povezan graf koji ima k čvorova i svi su neparnog stepena. Dokazati da broj k je paran.

     Neka d(1), d(2), ..., d(k) su stepeni čvorova. Kako su oni neparni brojevi, možemo ih predstaviti kao d(i)=2*xi +1, gde xi su celi brojevi
Otuda zbir stepena svih k čvorova DEG=d(1) + d(2) + ... + d(k) = 2*(x1 + x2 + xk ) + k (*)

LEMA: DEG je paran broj.
  Dokaz leme: Neka broj grana grafa |E|=s. Tada DEG=2*s, jer svaka grana sadrži tačno dva čvora i pri računanju zbira stepena svih čvorova (DEG) svaka grana se broji tačno dva puta, te je DEG dva puta veći od ukupnog broja grana.

Dakle, prema (*) i prema lemi važi:

    DEG=DEG
   2*(x1 + x2 + xk ) + k  = 2*s
   k =  2*(s- (x1 + x2 + xk )  )  

Odavde zaključujemo da k je paran broj.

4.Granama grafa G=( {1,2,3,4}, E) su pridružene težine kao u tabeli:
 
grana težina
(1,2) 2
(1,3) 8
(2,3) 3
(2,4) 4
(3,4) 7
(4,1) 5

Odrediti sve najkraće puteve (all shortest paths) između čvorova ovog grafa.

REŠENJE: Matrica Wi se formira prema algoritmu izloženom i knjizi u odeljku 6.7

   Algoritam SviNajkraciPutevi (W)

     { for (m=0; m<|V|; m++)

        for(x=0; x<|V|; x++)

          for(y=0;y<|V|; y++)

                if ( W[x,m] +W[m,y] <W[x,y])   W[x,y]= W[x,m] +W[m,y] ; /*nadjen je kraci put od x do y od predjasnje postavljene duzine*/

}
 

W 0 1 2 3 4
1 0 2 8 beskonačno
2 beskonačno 0 3 4
3 beskonačno beskonačno 0 7
4 5 beskonačno beskonačno 0

W 1 1 2 3 4
1 0 2 8 beskonačno
2 beskonačno 0 3 4
3 beskonačno beskonačno 0 7
4 5 7 13 0

     7=5+2                13=5+8

 

W 2 1 2 3 4
1 0 2 5 6
2 beskonačno 0 3 4
3 beskonačno beskonačno 0 7
4 5 7 10 0

5=2+3    6=2+4    10=5+5

W 3 1 2 3 4
1 0 2 5 6
2 beskonačno 0 3 4
3 beskonačno beskonačno 0 7
4 5 7 10 0

W 4 1 2 3 4
1 0 2 5 6
2 9 0 3 4
3 12 14 0 7
4 5 7 10 0

 

9=4+5   12=7+5  14=7+7

 

5. Zadat je težinski graf iz prethodnog zadatka sa nenegativnim težinama grana.  Naći središte grafa.

REŠENJE:Središte grafa je čvor v takav da ima najamanju ekscentričnost. Ekscentričnost čvora v je maksimum najkraćih rastojanja od svih čvorova grafa G do čvora v, tj.
ecc(v) = max { W[ i, v] | za svaki čvor i  }

    Koraci:
  1. primenom algoritma Svi_najkraci_putevi se nadje matrica W najkracih rastojanja izmedju svih parova cvorova
  2. nadju se maksimumi po kolonama matrice W
  3. nadje se vrednost minimuma ovih maksimuma i proglasiti za srediste grafa onaj cvor kojem odgovara ta vrednost
U konkretnom slučaju grafa iz prethodnog zadatka je pronadjena matrica W u četvrtoj iteraciji:
 
W 4 = W 1 2 3 4
1 0 2 5 6
2 9 0 3 4
3 12 14 0 7
4 5 7 10 0
Odavde se zaključuje da središte grafa je čvor 4, zato što on ima najmanju ekscentričnost (čija vrednost jeste 7).
 

6. Zadat je težinski graf G=(V,E) sa nenegativnim težinama grana. Za zadata dva čvora i,j skupa V pronaći put minimalne dužine (a ne samo težinu tog puta).

REŠENJE:

BSO, indeksiramo vrste i kolone od 1..n umesto od 0 do n-1.
Izmena algoritma Svi_Najkr_putevi (glava 6.7 knjige) , tako da se formira matrica prethodnika P gde element P[i,j] pamti čvor koji je neposredni prethodnik čvora  j  na najkraćem putu od čvora i.

Jasno je da:
1. P[i,j]=0 ako je i==j ili ako W[i,j]=beskonacno
2. P[i,j]=i ako i !=j i ako w[i,j] < beskonacno
 

Dakle, najpre se algortmom Svi_najkraci_putevi u tri for ciklusa ažurira polazna matrica težina W, tako da na kraju čuva samo najkraće težine (rastojanja) između dva čvora. Tokom ažuriranja matrice W, vrši se i formiranje matrice čvorova P, tako što:

    ako je u k iteracija spoljašnjeg for ciklusa od svih puteva medju čvorovima i,j koji prolaze kroz međučvorove 1,2,..k nađen trenutno najkraći put, onda:
  1. ako se čvor k ne nalazi na tom putu, onda su svi medjučvorovi iz skupa {1,2,..,k-1}, pa je to ista ocena najkraćeg puta dobijena iz prethodne (k-1).ve iteracije sa istim prethodnikom P[i,j]
  2. ako se čvor k nalazi na tom putu od i do j, onda ovaj put može da se podeli na puteve od i do k, i na put od k do j. Put izmedju čvorova i, k prolazi kroz medjučvorove 1..k-1 i on je deo najkraćeg puta od i do j u k-toj iteraciji, pa je kao u dokazu sa predavanja to i najkraci put od i do k. Slično se pookazuje da je put od k do j najkraći put od k do j  koji prolazi kroz čvorove 1..k-1.
    Dakle, kako je drugi segment puta zajednički, onda prethodnik u k-toj iteraciji P[i,j] čvora j na najkracem putu je istovetan kao i prethodnik P[k,j] iz (k-1)-ve iteracije
    Prema tome, najkraći put od čvora i do čvora j kroz čvorove 1..k se dobija kao manji od najkraćeg puta između i,j kroz medjučvorove 1,..., k-1 i zbira najkraćeg puta između čvorova i,k i puta izmedju k,j kroz čvorove 1..k-1 sto i jeste u jezgru najugnjezdenijeg for ciklusa.

Potom se od dobijene matrice P rekonstruiše najkraći put u proceduri putanja. 

Algoritam Svi_najkraci_putevi (W)
Ulaz:W(matrica tezina)
Izlaz: W(matrica duzina najkracih puteva), P(matrica prethodecih cvorova na najkracim putevima)
{
for (k=1; k<=n; k++)
  for (i=1; i<=n; i++)
   for (j=1; j<=n; j++)
     if (  W[i,j]>W[i,k]+W[k,j]  ) 
       {  P[i,j]=P[k,j];
          W[i,j]=W[i,k] + W[k,j]
      }
}
/*iz matrice P rekonstruisemo najkraci put izmedju dva zadata cvora  i,j */
Algoritam PUTANJA(i,j)
{
     if (i==j) 
       stampati (i);  /*povratak*/ 
     else
        if  (P[i,j]==0) stampati "(Nema puta izmedju i, j)";
        else       
               {PUTANJA(i, P[i,j] );
               stampati (j);
               }
}


Na primer, neka rezultujuća matrica P (po grafu iz zadatka 30 i 31) izgleda:
0 1 2 2
4 0 2 2
4 4 0 3
4 1 2 0

Tad je:
prvi poziv npr. Putanja (1,4)
kako P[1,4] !=0, drugi poziv je Putanja (1,2), jer P[1,4]=2
kako P[1,2] !=0, drugi poziv je Putanja (1,1), jer P[1,2]=1
kako 1==1, stampa se 1
dalje, štampa se 2
dalje, štampa se 4
DAKLE, najkraći put izmedju čvorova 1 i 4 jeste dužine 6 (po zadatku 30), a ima putanju (((1),2),4)

7. Zadat je težinski usmeren graf G=(V,E) sa nenegativnim težinama grana. Konstruisati algoritam za određivanje ciklusa minimalne težine u G.

REŠENJE:

  Iskoristićemo rešenje prethodnog zadatka. Naime, ciklus je put koji počinje i završava se u istom čvoru. Algoritam za nalaženje svih najkraćih puteva iz prethodnog zadatka se može iskoristiti za nalaženje najkraćeg ciklusa, tj. puta od čvorova i  do čvora j preko čvorova 1, 2,...,k (najkraći k-put),  redom za k=1,2,...,|V|.

 Jer, nakon izvršenja algoritma za nalaženje svih najkraćih puteva iz prethodnog zadatka, težina (dužina, cena, ...) najkraćeg ciklusa je jednaka vrednosti najmanjeg elementa na dijagonali matrice W, tj. W[k,k] za k=1,2,...,n,  gde n=|V|.

Ako je potrebno naći ne samo težinu najkraćeg ciklusa, već i sam put, onda se kao u prethodnom zadataku formira matrica prethodnika P gde element P[i,j] čuva čvor koji je neposredni prethodnik čvora j na najkraćem putu od cvora i.

BSO, indeksiramo vrste i kolone od 1 do n i pretpostavimo da ako dva cvora nisu vezani granom, njihova duzina puta je neki INT_MAX

Algoritam Najkraci_ciklus (W)
Ulaz:W(matrica tezina)
Izlaz: W(matrica duzina najkracih puteva), P(matrica prethodecih cvorova na najkracim putevima), 
       min (duzina najkraceg ciklusa)
{
for (k=1; k<=n; k++)
  for (i=1; i<=n; i++)
   for (j=1; j<=n; j++)

     if (  W[i,j]>W[i,k]+W[k,j]  ) 
       {  P[i,j]=P[k,j];
          W[i,j]=W[i,k] + W[k,j]
      }

min=W[1,1]; k=1;
for(i=1;i<=n;i++) if (W[i,i]<min) {min=W[i,i]; k=i;}
PUTANJA(k, P[k,k]);
 
}
/*iz matrice P rekonstruisemo najkraci put izmedju dva zadata cvora  i,j */
Algoritam PUTANJA(i,j)
{
     if (i==j) 
       stampati (i);  /*povratak*/ 
     else
        if  (P[i,j]==0) stampati "(Nema puta izmedju i, j)";
        else       
               {PUTANJA(i, P[i,j] );
               stampati (j);
               }
}

8.   Zadat je težinski usmeren graf G=(V,E) u kom neke grane imaju negativnu težinu. Konstruisati efikasan algoritam za utvrđivanje da li graf sadrži ciklus negativne težine u G (dovoljno je dati rezultat u obliku odgovora DA/NE).

REŠENJE:

   Primenimo ponovo algoritam Svi_Najkr_putevi (glava 6.7 knjige), ali ga modifikujmo tako da algoritam vrati odgovor DA kada naidje na dijagonalni element matrice koji je negativan.

   BSO, indeksiramo vrste i kolone od 0..n-1 umesto od 1 do n

Algoritam Negativan_ciklus (W)
Ulaz:W(matrica tezina)
Izlaz: DA/NE u slucaju da ima/nema negativnog ciklusa

{


for (k=0; k<n; k++)
  for (i=0; i<n; i++)
   for (j=0; j<n; j++)

     if (  W[i,j]>W[i,k]+W[k,j]  ) 
          W[i,j]=W[i,k] + W[k,j]
      

for(i=0;i<n;i++) if (W[i,i]<0) return DA;
return NE;
 
}
9. Zadat je težinski graf G=(V,E) čije grane mogu imati i negativne težine. Naći najkraća rastojanja od polaznog čvora grafa G do svih ostalih (bez smanjenja opštosti obeležimo taj čvor sa 1).

graf sa nenegativnim tezinama

REŠENJE:

  Koristimo Dijkstrin algoritam za nalaženje težina najkraćih puteva od zadatog čvora 1 do ostalih čvorova u grafu (glava 6.5 u knjizi) tako što ga modifikujemo da radi i nad težinski grafom G=(V,E) čije grane mogu imati i negativne težine.

 

Algoritam Dijkstra_negativni(G,W)


ulaz: G=(V,E) (tezinski graf sa negativnim tezinama), W(matrica tezina, indeksirana po i=1..|V| ) )
izlaz:D (niz  gde d[i] je najkrace rastojanje od polaznog cvora 1 do cvora i, gde i=1..|V| )
         T(niz gde t[i]  je cvor koji je prethodnik cvora i na najkracem putu od  cvora 1 )

{
     for (i=2; i <= n; i++)
     {
          d[i]=w[1,i];
          if (w[1,i] != beskonacno)  t[i]=1;
          else t[i]=0;
     }           
     for (k=1; k<=n-1; k++) 
         for svaka grana (u,v) 
             if (d[u] +w[u,v] < d[v])  
              {
                   d[v]=d[u]+w[u,v];
                    t[v]=u;
               }
    for svaka grana (u,v) 
       if (d[u] +w[u,v] < d[v])  return false;
return true;
}
Na vremensku složenost algoritma utiču dva for ciklusa gde se za k=1..n-1 ažurira za svaka granu nizove D,T (ako je potrebno), te je onda složenost O( n |E| ). 


10. Dat je usmereni graf G=(V,E) sa skupom čvorova V={1,2,3,4,5,6,7,8,9}
i skupom grana E sa težinama kao na slici. Odrediti težine najkraćih
puteva od čvora 1 do ostalih čvorova u grafu.




REŠENJE Koristimo Dijkstrin 
algoritam za nalaženje težina najkraćih puteva od zadatog čvora 1 do ostalih 
čvorova u grafu (glava 6.5 u knjizi).

 
Algoritam Najkr_putevi (G,v)

ulaz: G=(V,E) (tezinski usmeren graf), v (polazni cvor)

izlaz: za svaki cvor w je sa w.SP oznacena tezina najkraceg puta od v do w





(* uz pretpostavku da su sve tezine grana grafa nenegativne *)

begin

    for svi cvorovi w do

         w.oznaka=false;

         w.SP=*; (* za sada tezina je beskonacna *)





    v.SP=0;

    while postoji neoznacen cvor do

        neka w je neoznacen cvor sa najmanjom vrednoscu w.SP

        w.oznaka=true;

        for sve grane (w,z)  takve da z je neoznacen do

             if w.SP + tezina(w,z) < z.SP then  z.SP=w.SP + tezina(w,z);





end
Prikaz postupka i rešenje je naveden u tabeli .

Najpre se popuni 1. red tabele tako da se unesu vrednosti 
težina grana sa slike grafa.

    Potom se izabere najmanja težina te vrste. Konkretno to je 
ovde vrednost 2  čvora 8.

Potom se označi čvor 8 i formira 2. red tabele u kom se menjaju 
težine onih puteva koje bivaju kraće ako se u njih uključi čvor 8.

I tako redom sve dok postoji neoznačen čvor.





označeni

čvor w 

(najmanje SP)		

2

3

4

5

6

7

8

9





1

-

15

14

10

11

6

*

2

*






1,8

8

11

14

10

11

5

10

2

7






1,6,8

6

11

14

10

9

5

9

2

7






1,6,8,9

9

10

14

10

9

5

9

2

7






1,5,6,8,9

5

10

14

10

9

5

9

2

7






1,,5,6,7,8,9

7

10

14

10
9

5

9

2

7






1,2,5,6,7,8,9

2

10

12

10

9

5

9

2

7





1,2,4,5,6,7,8,9

4

10

12

10

9

5

9

2

7





1,2,3,4,5,6,7,8,9

3

10

12

10

9

5

9

2

7






11. 
Neka e je grana maksimalne težine u nekom ciklusu grafa G=(V,E).
Dokazati da postoji MCST grafa G'=(V, 
E\{e}) koje je istovremeno i MCST grafa G.
 

 REŠENJE:

PODSEĆANJE:
Prema glavi 6.6 
knjige Algoritmika MCST (minimum-cost spanning tree) je minimalno 
povezujuće stablo, tj. povezujuće stablo čija suma težina (cena) grana je 
minimalna.
 U knjizi je prikazan algoritam za konstrukciju MCST koji 
nalikuje Dijkstra algoritmu za nalaženje najkraćih puteva od zadatog čvora 
grafa. Složenost algoritma je O( (|E|+|V|)  log |V|)


Neka T je MCST zadatog grafa G koje sadrži  granu 
e=(x,y) najveće težine u nekom ciklusu C. Ako se 
ukloni grana e, onda iz stabla T nastaju stabla T1, T2, tako da je na 
primer čvor x u T1, čvor y u T2. 

Neka P je put od x  do y  koji nastaje kada se iz cilusa C ukloni grana e. 
Na tom putu postoji grana e1 koja povezuje stabla T1 i T2, tj. grana čiji jedan 
kraj mora biti u T1, a drugi kraj u T2. Težina grane e1 jednaka je težini grane 
e (jer ako bi težina grane e1 bila manja od težine grane e, onda bi povezujuće 
stablo T bez grane e koje sadrzi 
granu e1 imalo manju cenu od stabla T). 

   Dakle, stablo (T\{e}) 
 sa granom {e1} je 
MCST, ali ne sadrzi granu e.
12. Neka je  G=(V,E) 
neusmeren težinski graf i neka T=(V,F) je podgraf koji se 
sastoji od svih grana na najkraćim putevima od čvora x iz V. 
Ako se težine grana G povećaju za jednu istu konstantu w, da li T ostaje 
i dalje stablo najkraćih puteva od x.

REŠENJE:  
Odgovor je NE.

Na primer, neka u grafu T sa 
korenom x i čvorovima x, y, z (trougao XYZ)

      grana (x,y) ima 
težinu 2

      grana (x,z) ima težinu 5

      grana (y,z) ima težinu 2

To znači da primenom Dijkstra 
algoritma nad G smo imali da u odnosu na granu  (x,z) kraći put od x do z 
preko čvora y ima težinu 4=2+2

Neka je w=5. Dakle, sada u grafu T sa korenom x

      
grana (x,y) ima težinu 7

      grana (x,z) ima težinu 10

      grana (y,z) ima težinu 7

To znači da put od x do z preko 
čvora y ima težinu 14=7+7, ali od njega je kraća 
 grana (x,z) sa težinom 10



 13.  
Dat je bipartitivni graf G čiji su
čvorovi a, b, c, d, e, f, g
odnosno 1, 2, 3, 4, 5, 6, 7 i
čiji skup grana je 

{(a,1), (a,2), (a,5), (b,1), (b,2), (b,6), (c,1), (c,2), (c,3), (c,7),  (d,1), (d,2), (e,1), (e,4), (f,5), 
(g,6)}. 
Odrediti optimalno bipartitivno uparivanje. 

PODSEĆANJE:


Za zadati neusmeren graf G, uparivanje je skup 
disjunktnih grana (grana bez zajedničkih čvorova). 

 Čvor koji ne pripada niti jednoj grani uparivanja zove se 
neuparen čvor.

 Savršeno uparivanje je uparivanje u kom su svi čvorovi upareni.

 Optimalno uparivanje je uparivanje sa maksimalnim brojem grana. Ovaj 
zadatak se bavi jednim tipom optimalnog uparivanja.


Ako 
G=(V,E,U) jeste bipartitivni graf u kome V, U su disjunktni skupovi čvorova, E 
je skup grana koje povezuje neke čvorove iz V sa nekim čvorovima iz U. 


                          

Teorema o alternirajućem putu:

Bipartitivno uparivanje S jeste optimalno 
<=     > u  grafu G 
ne   postoje alternirajući putevi za   njega.


Alternirajuci put X za dato uparivanje S jeste put od neuparenog
čvora v iz V do neuparenog
čvora u iz U, pri
čemu su grane puta X naizmenično u E\S, odnosno u S.

Tj. prva grana (v,x) puta X ne pripada S, jer v je neuparen, druga grana (x,y) pripada S i
tako dalje do grane (z,u) puta X koja ne pripada S.


Teorema o alternirajućem putu određuje korake algoritma za 
pronalazak optimalnog bipartitivnog 
uparivanja. Naime, ma koje uparivanje 
koje nije optimalno ima alternirajući put, a alternirajući put proizvodi 
povećano uparivanje.  Dakle, na početku algoritma 
pronadje se uparivanje S dodavanjem grana dokle god je to moguće. Potom se 
pronadje alternirajući put za uparivanje S, a na osnovu njega se vrši 
povećavanje uparivanj sve dok nedobijemo novo uparivanje S za koje nema 
alternirajućih puteva. Dobijeno uparivanje je tada optimalno.
  



                          



Dakle, neka je uparivanje M={(a,1),  (b,2),  (c,3),  (e,4), (f,5), (g,6)}.

Na slici je prikazano da zbog pronalaska alternirajuceg puta u G, usmeravamo 
grane G tako da one koje su u M budu udesno, a one koje nisu orjentisane su 
ulevo. Neupareni su čvorovi 7, d i pokušavamo da nadjemo put od 
7 do d. Ali takav put ne postoji, jer od 7 se može samo do čvora c, a od njega 
dalje samo do čvora 3, ali ne i čvora d. Dakle, M je optimalno uparivanje.

 

  Može se do uparivanja M doći i ako se kao polazno 
uparivanje uspostavi uparivanje N={(a,5),  (b,2),  (c,3),  (e,4), 
(g,6)}, jer bi se uočio alternirajući put f, 5, a.


14.
Dat je bipartitivni graf G čiji su
čvorovi a, b, c, d, e, f, odnosno 1, 2, 3, 4, 5, 6 i
čiji skup grana je 

{(a,1), (b,1), (b,2), (b,3), (c,4), (d,3), (d,6), (e,4), (f,5), (f,6)}. 

Odrediti optimalno bipartitivno uparivanje. 

REŠENJE:
 

Za zadati neusmeren graf G, uparivanje je skup 
disjunktnih grana (grana bez zajedničkih čvorova). 

 Čvor koji ne pripada niti jednoj grani uparivanja zove se 
neuparen čvor.

 Savršeno uparivanje je uparivanje u kom su svi čvorovi upareni.

 Optimalno uparivanje je uparivanje sa maksimalnim brojem grana. Ovaj 
zadatak se bavi jednim tipom optimalnog uparivanja.


                          

 

             

Ako 
G=(V,E,U) jeste bipartitivni graf u kome V, U su disjunktni skupovi čvorova, E 
je skup grana koje povezuje neke čvorove iz V sa nekim čvorovima iz U. 


                          
Na primer, slika 5 prikazuje bipartitivni graf sa skupom čvorova
koga čine dva disjunktna podskupa {1, 2} i {3, 4, 5}, gde svaka grana grafa
povezuju čvorove iz različitih podskupova.

slika5

Slika5 Optimalno bipartitivno 
uparivanje M je uparivanje sa maksimalnim brojem grana u bipartitivnom grafu. 


optimalno bipartitivno uparivanje




Neka je uparivanje S={ a-1, b-3, c-4, 
d-6}.

 Može se uočiti da postoji alternirajući put za ovo 
uparivanje i to je put a-1-b-3-d-6-f. Kako postoji alternirajući put=>ovo uparivanje u G  nije 
optimalno. 

 Granu b-3 i dodamo  nove grane b-2, f-6. Novo uparivanje S={ 
a-1, b-2, c-4, d-3, f-6}.  
Novo uparivanje nema aternirajućih puteva (jer bi  tačno jedan  takav  
bio  e-4-c-5, ali on   ne može da se realizuje u G)=> uparivanje
S jeste optimalno.    (broj grana u uparivanju je pet  i
jeste optimalno ,  jer  postoji  tačno po jedna grana za
čvor c, odnosno e i to do čvora 4)