Grafuri cu legături speciale

CERINTA:

In functie de un graf alcatuit din statii si sectii de cale ferata constituiti cel putin 5 drumuri elementare utilizand metoda studiata la seminar.

REZOLVARE:

Fiind data o retea de comunicatii exista anumite probabilitati determinate experimental ca elementele ei (noduri si arce) sa functioneze normal.

Graful in functie de care se constitue matricea C12 este urmatorul:

Prima matrice M1 este:

1 2 3 4 5

1 - 1a2 1b3 1g4

2 2a1 - 2h3 2e4

3 3b1 3h2 - 3f4 3c5

4 4g1 4e2 4f3 - 4d5

5 5c3 5d4 -

A doua matrice M2 este :

1 2 3 4 5

1 - 1b3h2

1g4e2 1g4f3 1b3f4 1g4d5

1b3c5

2 2h3b1

2e4g1 - 2e4f3 2h3f4 2h3c5

2e4d5

3 3f4g1 3f4e2 - 3b1g4

3h2e4

3c5d4 3f4d5

4 4f3b1 4f3h2 4g1b3

4e2h3

4d5c3 - 4f3c5

5 5c3b1

5d4g1 5c3h2

5d4e2 5d4f3 5c3f4 -

A treia matrice M3 este:

1 2 3 4 5

1 - 1g4f3h2

1b3f4e2 1g4d5c3 1b3c5d4 1g4f3c5

1b3f4c5

2 2h3f4g1

2e4f3b1 - 2e4d5c3 2h3c5d4 2h3f4d5

2e4f3c5

3 2c5d4g1 3c5d4e2 - 3b1g4d5

4 4d5c3b1 4d5c3h2 - 4g1b3c5

4e2h3c5

5 5d4f3b1

5c3f4g1 5d4f3h2

5c3f4e2 5d4g1b3

5d4e2h3 5c3b1g4

5c3h2e4 -

A patra matrice M4 este:

1 2 3 4 5

1 - 1g4d5c3h2

1b3c5d4e2

2 2h3c5d4g1

2e4d5c3b1 -

3 -

4 -

5 -

Completand cele 4 matrici am descoperit urmatoarele 7 drumuri:

D1= 1a2

D2= 1b3h2

D3= 1g4e2

D4= 1g4f3h2

D5= 1b3f4e2

D6= 1g4d5c3h2

D7= 1b3c5d4e2

Ca urmare matricea C12 va avea 7 linii si 13 coloane.

1 2 3 4 5 a b c d e f g h

l1 l2 l3 l4 l5 l6 l7 l8 l9 l10 l11 l12 l13

d1 1 1 0 0 0 1 0 0 0 0 0 0 0

d2 1 1 1 0 0 0 1 0 0 0 0 0 1

d3 1 1 0 1 0 0 0 0 0 1 0 1 0

d4 1 1 1 1 0 0 0 0 0 0 1 1 1

d5 1 1 1 1 0 0 1 0 0 1 1 0 0

d6 1 1 1 1 1 0 0 1 1 0 0 1 1

d7 1 1 1 1 1 0 1 1 1 1 0 0 0