Grafové algoritmy

Stupeň vrcholu V: počet hrán, vo vrchole V
Cyklus: V orientovanom grafe je cesta začínajúca a končiaca v tom istom vrchole a obsahujúca najmenej jednu hranu
Strom: je graf bez cyklov.

Reprezentácia grafov

Matica susednosti

Vzájomné súvislosti hrán a vrcholov sú popísané pomocou matice susednosti M_G.

Nech G=<V,E>;, [math]E\in \left\{ {{e}_{1}},{{e}_{2}},...,{{e}_{m}} \right\}[/math]
Matica susednosti M_G grafu G je štvorcová matica rádu m, kde

[math]{{m}_{i,j}}=\langle \begin{matrix} 1,\ \ \text{Ak}\,\text{medzi}\,\text{vrcholmi i a j existuje hrana } \\ 0,\ \text{Ak}\,\text{medzi}\,\text{vrcholmi i a j nrexistuje hrana} \\ \end{matrix}[/math]

Príklad:

Matica susednosti pre neorienotvaný graf (na prvom obrázku)

[math]{{M}_{G}}=\left( \begin{matrix} 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ \end{matrix} \right)[/math]

Matica susednosti pre orienotvaný graf (na druhom obrázku)

[math]{{M}_{G}}=\left( \begin{matrix} 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ \end{matrix} \right)[/math]

Matica susednosti M_G grafu G s ohodnotenými hranami:

Každému vrcholu je priradený zoznam jeho susedov (využitie lineárneho zoznamu).

Matica susednosti M_G grafu G je štvorcová matica rádu m, kde

[math]{{m}_{i,j}}=\langle \begin{matrix} 1,\ \ \text{Ak}\,\text{medzi}\,\text{vrcholmi i a j existuje hrana } \\ c,\ \text{Ak}\,\text{medzi}\,\text{vrcholmi i a j nrexistuje hrana} \\ \end{matrix}[/math]

Matica susednosti pre orienotvaný ohodnotený graf (na treťom obrázku)

[math]{{M}_{G}}=\left( \begin{matrix} 0 & 4 & 0 & 1 & 0 \\ 0 & 0 & 0 & 8 & 0 \\ 0 & 9 & 0 & 0 & 0 \\ 0 & 0 & 7 & 0 & 5 \\ 3 & 0 & 0 & 0 & 0 \\ \end{matrix} \right)[/math]

Implementácia matice susednosti v jazyku C

Úloha:Vytvorte maticu susednosti pre graf G. Graf G bude zadávaný nasledovne:

prvý bude počet vrcholov (pocetV) a potom počet hrán (pocetH) grafu G. Potom bude nasledovať pocetH dvojíc vrcholov + cena hrany c.

Vzorový vstup:

Analýza úlohy

Vlastnosť matice susednosti neorientovaného grafu je, že daná matica je súmerná vzhľadom na hlavnú diagonálu. Túto vlastnosť môžeme formulovať nasledovne: ak vrchol i susedí s vrcholom j, tak potom aj vrchol j susedí s vrcholom i.

Pri orientovaných grafoch takéto tvrdenie nemôžeme povedať, pretože ak existuje iba orientovaná hrana s vrcholu i do vrcholu j, tak potom neexistuje spôsob ako sa z vrcholu j dostať do vrcholu i.

Príprava dátovej štruktúry dvojrozmerné pole celých čísel (matica susednosti)

 int i,j,pocetV,pocetH,v1,v2,c;
 cin>>pocetV>>pocetH;
 int **Mg=new int*[pocetV];
    for(i=0;i<pocetV;i++)
    	Mg[i]=new int[pocetV];

// vynulovanie matice 
//Mg predstavuje pr8zdny graf.
for(i=0;i<pocetV;i++)
  for(j=0;j<pocetV;j++)
    Mg[i][j]=0;

Vytvorenie orientovaného grafu

    for(i=0;i<pocetH;i++)
    {	cin>>v1>>v2>>c;
    	Mg[v1-1][v2-1]=c;
    }

Vytvorenie neorientovaného grafu

    for(i=0;i<pocetH;i++)
    {	cin>>v1>>v2>>c;
    	Mg[v1-1][v2-1]=c;
        Mg[v2-1][v1-1]=c; 
    }

Zoznam vrcholov