Matricea ponderilor

 

Fie G=(V, E) un graf neorientat, unde V are n elemente (n noduri) si E are m elemente (m  muchii). Atasam fiecarei muchii o pondere (sau cost) ci,j. Spre exemplu, ne putem  imagina nodurile unui graf ca fiind niste repere pe o harta si  costurile distante intre repere adiacente.

Matricea ponderilor asociata grafului este o matrice simetrica cu nxn elemente

 

Astfel:  p= (pi j) n x n cu:

 

 


                            0, daca i=j

p[i,j]=           ci,j,  daca [i,j]ÎE

                            ¥  altfel

                                       

                                               

0 2  ¥ 5 ¥

2 0 6 ¥ ¥

¥ 6 0 1 8

5 ¥ 1 0 ¥

¥ ¥ 8 ¥ 0

 

Datele care se vor citi pentru generarea matricii ponderilor sunt:

 

Numarul de noduri, numarul de muchii si m triplete de forma extremitati muchie si cost asociat:

 

5

5

1 2 2

1 4 5

2 3 6

3 4 1

3 5 8

 

Problema:

Sa se genereze matricea ponderilor pentru un graf citit (n noduri, m muchii si m triplete).

Indicatii:

-         pentru infinit se va folosi o valoare mai mare decat oricare dintre valorile posibile pentru costuri. De obicei intervalul de valori pentru costuri este precizat.

-         Initial se incarca in matrice infinit apoi se suprascrie matricea pentru fiecare triplet citit:
Ex: cin>>x>>y>>cost

                 p[x][y]=p[y][x]=cost

 

Problema 2:

 

Intr-o localitate exista n repere (sub forma de siruri de caractere). Intre cele n repere exista m drumuri directe pentru care se cunosc distantele.

a)      sa se construiasa un graf asociat acestei harti (matricea ponderilor)

b)      fie o succesiune de k repere. Sa se determine daca succesiunea respeciva este un lant in in graf. In caz afirmativ se va determina lungime, alfel se va afisa un mesaj

c)      sa se determine daca se poate ajunge de la reperul 1 la reperul 2

d)      cate zone izolate exista pe harta (nr de componente conexe)

 

ex:

Date de intrare

Date de iesire

7

farmacie magazin dispensar biserica scoala lac gradina

6

farmacie magazin 10

magazin biserica  20

biserica dispensar  30

dispensar magazin 10

dispensar scoala  20

lac gradina  40

 

0 10 pinf pinf pinf pinf pinf

10 0 10 20 pinf pinf pinf

pinf 10 0 30 20 pinf pinf

pinf 20 30 0 pinf pinf pinf

pinf pinf 20 pinf 0 pinf pinf

pinf pinf pinf pinf pinf 0 40

pinf pinf pinf pinf pinf 40 0

Farmacie, magazin, biserica, dispensar, scoala

Da! Lungimea: 80

dispensar, lac

Nu se poate ajunge de la dispensar la lac

 

Exista doua zone izolate pe harta