ALGORITMUL INMULTIRII LATINE (KAUFMANN)

ALGORITMUL INMULTIRII LATINE (KAUFMANN)

Algoritmul inmultirii latine serveste in principal pentru determinarea drumurilor de o anumita lungime.

Fie graful G= (X,F) = (X,A) .

Pasul 1

Asociem grafului o matrice a arcelor (conexiunilor directe) care in locul cifrelor 1 din M_G contine arcele corespunzatoare, reprezentate prin varfurile care le compun. Notam aceasta matrice (numita matrice latina) cu T⁽¹⁾ = (t_ij)_{i,j = 1,n}, unde

t_ij =

Pasul 2

Formam matricea T⁽⁰⁾ = (t_{i,j = 1,n}, numita matricea destinatiilor posibile, care se obtine prin suprimarea extremitatii initiale a fiecarui arc din matricea T⁽¹⁾.

t

Pasul 3

Cu matricele T⁽¹⁾ si T⁽⁰⁾ , in aceasta ordine, se efectueaza operatia de inmultire latina (notata cu L) sau concaternare astfel :

1. Se respecta formal regula de inmultire a matricelor
2. Se fac urmatoarele conventii:

c1) daca unul din elementele participante la calcul este 0 rezultatul va fi 0.

c2) atunci cand se inmulteste    un arc din matricea T⁽¹⁾ cu un varf din matricea T⁽⁰⁾, rezultatul operatiei se consemneaza scriind consecutiv varfurile care intervin in calcul (obligatoriu cu mentinerea ordinei in care apar varfurile).

Pasul 4

Fie T⁽²⁾ = T⁽¹⁾ L T⁽⁰⁾

Introducem relatia de recurenta T^{(r + 1)} = T^(r) L T⁽⁰⁾, rN*.

Matricea T^(m), cu mN* va contine lista tuturor drumurilor de lungime m ( adica formate din m arce) in graful dat.

Exemplu

Sa se determine drumurile de lungime 2 si 3 in graful a carui matrice este:

M_G

Pasul 1

Scriem matricea T⁽¹⁾

Pasul 2

Scriem matricea destinatiilor posibile T⁽⁰⁾

Pasul 3

Calculam T⁽²⁾ = T⁽¹⁾ L T⁽⁰⁾ care ne va arata drumurile de lungime 2.

T⁽²⁾ = T⁽¹⁾ L T⁽⁰⁾    L

Pasul 4

Calculam T⁽³⁾ = T⁽²⁾ L T⁽⁰⁾ care va evidentia drumurile de lungime 3.

T⁽³⁾ = T⁽²⁾ L T⁽⁰⁾ L

Concluzie :

Ø      Graful contine 4 drumuri de lungime 2 si anume d₁ = (x₁, x₃, x₂), d₂ = (x₂, x₁, x₃),

d₃ = (x₂, x₁, x₄), d₄ = (x₃, x₂, x₁) si nu exista circuite de lungime 2.

Ø      Graful contine 4 drumuri de lungime 3 din care 3 circuite si un drum hamiltonian, si anume : d₅ = (x₁, x₃, x₂, x₁), d₆ = (x₂, x₁, x₃, x₂), d₇ = (x₃, x₂, x₁, x₃), d₈ = (x₃, x₂, x₁, x₄),

Determinarea drumurilor si circuitelor hamiltoniene in grafuri cu circuite

Definitie

Un circuit C_H = (x_i1, x_{i2, ,} x_in, x_i1) se numeste hamiltonian daca trece o data si numai o data prin fiecare varf al grafului cu exceptia varfului x_i1.

Observatie

1. O conditie necesara pentru existenta unui drum hamiltonian este ca graful sa fie complet ( orice cuplu de varfuri este legat cu cel putin un arc).
2. O conditie necesara pentru existenta cel putin a unui circuit hamiltonian este ca graful G = (X,F) sa fie tare conex (sa existe cel putin un drum intre oricare doua varfuri).

Ø      Pentru determinarea drumurilor si/sau circuitelor hamiltoniene intr-un graf cu n varfuri se calculeaza prin algoritmul inmultirii latine matricea T⁽ⁿ⁾, cu precizarea ca in matricele T^(r), r, se considera t daca secventa indicilor varfurilor t si t contine doi indici identici pentru orice k (daca in rezultatul inmultirii se repeta doua varfuri).

Ø      Existenta unui element diferit de 0 pe diagonala uneia dintre matricele T^(r) care intervin in algoritm indica atat existenta unui circuit hamiltonian cat si ordinea varfurilor.

PROBLEME:

1. Sa se determine drumurile hamiltoniene pentru graful definit de:

M_G =

2. Sa se determine drumurile hamitoniene pentru graful definit de:

M_G =

3. Fie graful G a carui matrice este:

M_G =

a)      sa se determine d_H daca exista

b)      sa se listeze drumurile de lungime 3 din G

4. Se considera graful G a carui matrice este :

M_G =

Sa se determine matricea drumurilor si apoi, folosind inmultirea latina, sa se identifice in G circuitele de lungime 4.

5. Fie graful G = (X,A), X = , F(x₁) = , F(x₂) = , F(x₃) = , F(x₄) = , F(x₅) =

a)      Sa se determine matricea drumurilor in G

b)      Sa se listeze drumurile de lungime 4 si sa se identifice, daca exista, d_H.