1II GRAFURI TARE CONEXEDRUMURI HAMILTONIENEDISTANTE MINIMEALGORITMIMATRICEALIDacanotiuneadeconexitateintr-ungraforientatestedefinitacuajutorulconceptuluidelant,notiuneadetareconexitate se va defini cu ajutorul conceptului de drum.Definitia 1Un graf G = (V,U)se numeste tare conexdacaareproprietateacapentruoricaredouavarfuridistinctex,y exista un drum de la x la y si un drum de la y la x.Altfel zis, oricare doua varfuri din graful orientat sa seafle pe un circuit.Matriceadrumurilorunuigraftareconexaretoateelementele egale cu unu.Definitia2SenumestecomponentatareconexaaunuigraforientatG=(V,U),unsubgrafG'=(V',U')cuproprietatea ca este tare conex simaximal in raport cu aceastaproprietate, adica zV\V' subgraful luiGgeneratdeV'{z}nu mai este tare conex.Fie R o relatie binara definita pe multimea V a grafuluiorientatG=(V,U),astfel:xRydacax=ysauexistaundrum2delaxlaysiundrumdelaylax.Aceastarelatieesteorelatie de echivalenta (Exercitiu!).ClaseledeechivalentacorespunzatoarerelatieiRsuntcomponentele tare conexe ale lui G.Exemplul 1Sa consideram urmatorulgraforientat Gcare nu este tare conex.246 135Fig.1Componentele tare conexe sunt: C1={1,2,3,4};C2={5};C3={6}.Propozitia1FieC1siC2douacomponentetareconexe distincte si varfurile x,y din C1,x',y' din C2. Daca existaun drumdx,x', atunci nu va mai exista un drum dy',y.3Demonstratie:Sapresupunemcaarexistaundrumdy',yingraf.Atunci,conformipotezei,vorexistadrumuriledx,x',y'sidy,'y,x.Prinurmare,varfurilexsiy's-argasipeuncircuit (contradictie!).Descrierea unui algoritm matriceal pentru identificareacomponentelor tare conexePentrudeterminareacomponentelortareconexeintr-ungraforientatG=(V,U),sepoateutilizamatriceadrumurilorasociatagrafului.DacamatriceaDaretoateelementelede pe diagonala principala egale cu 1,atuncitoatevarfurileluiGseaflaincircuite.SanotamcuS(xj)multimeavarfurilor lui G care sunt extremitati finale aleunor drumuricare pleaca dinxj,iarcuP(xj)multimeatuturorvarfurilordinG care sunt extremitati initiale ale unor drumuri care sosesc invarful xj.SeobservacamultimeaS(xj)constadinacelevarfurixkcuproprietatead[xj,xk]=1,adicavarfurilecorespunzatoarecoloanelordinmatriceaDcarecontinelementeegalecuunupeliniaj.Analog,multimeaP(xj)constadinacelevarfurixkcu proprietatea ca d[xk,xj] = 1, adicavarfurilecorespunzatoareliniilor din D care contin elemente egale cu unu pe coloana j.Componentatareconexacorespunzatoarevarfuluixjva fi(S(xj)P(xj)) {xj}.4Matrice latine. Drumuri hamiltonieneA.KaufmannsiJ.Malgrangeauintrodusincalcululoperationalconceptuldematricelatina.Matricelelatineparticipalarelatiadedefinireaunuigraf.Secventedevarfurialeunuigraforientatpotficaracterizatedeanumiteproprietati.Definitia3VarfurileunuigraforientatcareauaceeasiproprietatePsicaresesuccedintr-oanumitaordinecompatibila cu ordinea din grafsenumestesecventa.Operatiacesepoaterealizacusecventele,careauaceeasi proprietate P, este concatenarea.Princoncatenareaadouasecvente,cuaceeasiproprietateP, n mj j j i i ix x x s x x x s ,..., , , ,..., ,2 1 2 12 1 ,seobtinesecventa n mj j j i i ix x x x x x s s ,..., , , ,..., , *3 2 2 12 1 ,dacaau loc urmatoarele doua conditii:1) 1j ix xm2) s1*s2 are proprietateaP.Dacaunadinceledouaconditiinu este indeplinita,atunci se va consideras1*s2 = .Conventii:. * ; * ; * s sExemplul 2Se considera urmatorul graf orientat:51 2 53 4 Fig. 2ProprietateaPconstainfaptulcavarfuriledinsecvente se afla pe drumuri elementare.Fie secventele:s1= 2 5 3s2= 2 1 4s3= 3 2 1 4s4=3 1 4.Se observa ca:s1*s2=(nu are loc conditia 1)s1*s3=(drumul (2 5 3 2 1 4) nu este elementar)s1*s4= (2 5 3 1 4).Concatenarea este o operatie asociativa, dar nu este6comutativa.Tranzitiiledingrafsevordispunesubformaunuitablou (matrice latina).A(0)1 2 3 4 51 1,4 1,52 2,1 2,53 3,1 3,24 4,1 4,2 4,35 5,3Vom construimatricea A(1) pornindde lamatriceaA(0)luandsecventelefaraprimulelementallortinandcontdedefinitia concatenarii.A(1)1 2 3 4 51 4 52 1 53 1 24 1 2 35 3Concatenareacelor doua tablouri se realizeaza similar7produsuluiadouamatriceprintehnica"linie-coloana",astfel:A(2)1 2 3 4 51 - 142143153 2- 253 214 2153 321- 314 315325 4 421431432- 4154255 531 532 -Exempludecalcul:Linia1dinA(0)"inmultita"cucoloana1dinA(1)vaconducelasecventa141careesteuncircuit de lungime 2 si nu ne intereseaza de aceea am trecut (-).In rest se obtin numai secvente vide ( ).La acest pas, se vorobtinetoatedrumurileelementarede lungime 2.Incontinuare,sevaefectuaoperatiaintreA(2)siA(1)pentruaobtineA(3)cevaindicadrumurileelementaredelungime 3.8A(3)1 2 3 4 51- 14321532 14252 2531 - 21432153 3 3142 -3214 3215 44321 41534253 - 4215431543255 5321 5314 -Drumurile elementare de lungime 4, le vomintalnicaelemente in tabloul A(4).Pentru a calcula pe A(4) vomoperacutablourileA(3)siA(1).A(4)1 2 3 4 51 - 14253 143252 -25314 3 - 314254 42531 41532 42153 - 4321555314253214 -9A(5)1 2 3 4 51 - 2- 3 - 4 -5 -IntabloulA(5)artrebuisaseidentificedrumurileelementaredelungime5.Seobservacanuexistadrumurielementare de lungime 5.Prin urmare,exista drumuri hamiltoniene in graf (veziA(4)).Reluaticalculelesiidentificaticircuitulhamiltoniandin graful considerat.Algoritmi pentru calculul distantelor minimeFieG=(V,U)ungraforientatsi:UR+ofunctiecareasociazafiecaruiarcdinGunnumarrealnenegativnumitlungimeasa.Incazuldefata,prinlungimeaunuidrumdinGseintelegesumalungimilorarcelorsale,iardistantaminimadintredouavarfurioarecarealeluiGconstainlungimeadrumurilorscurtecareaucaextremitatiacestevarfuri.10Algoritmul lui Roy-FloydFieG=(V,U)ungraforientatcuV={x1,x2,,xn},etichetat. Vom defini matricea distantelor directe ale lui Gcafiind matricea A(nxn) unde:' U x x dacaj i dacaU x x daca xj i aj ij i j) , (0) , ( )) , ((x] , [i(1 i,j n)FieA*(nxn)matriceadistantelorminimedintrevarfurile grafului orientat G care se defineste astfel: 'altfelj i aj i,*minj i daca 0] , [(1i,j n) undemini,jreprezintaminimuldintrelungimiledrumurilorcuextremitatile i, j.RolulacestuialgoritmestedeagasimatriceadistantelorminimeA*porninddelamatriceadistantelordirecte A.for k=1 , nfor i =1 , nif (ik) for j = 1 , n if (ji jk)a[i,j] = min (a[i,j] , a[i,k]+a[k,j] )11Ciclurilefor(i),for(j),vorrecalculaelementelecuindicidiferitiintreeialeuneisubmatricecun-1liniisin-1coloane,deciestenecesarunnumarde(n-1)2(n-1)=(n-1)*(n-2)operatiideadunare,respectivcomparatii.Intregulalgoritm(incluzandfor(k))vanecesitaunnumarden(n-1)(n-2)operatiideadunaresitotatateacomparatii,adicaO(n3 ).Observatie:Algoritmulrespectivsepoatetratasiinlimbaj operatorial .Tk(A(k-1))=A(k) (k=1,n) unde,' + ) , 1 ( , 0), , ()}, , ( ) , ( ), , ( min{) , () 1 () 1 ( ) 1 ( ) 1 () (n j i j i dacak j sau k i daca j i Ak j i j k A k i A j i Aj i Akk k kkAsadar,laaplicareaoperatoruluiTk,liniasicoloanakdinmatriceaA(k)ramannemodificate,adicaidenticecuceledin matricea A(k-1).ElementeledepediagonalaprincipalaamatriceiAsunt egale cu zero.Acestalgoritm,putinmodificat,poateserviladeterminareadrumurilordelungimeminimadintrevarfurilegrafului orientat G.VomdefiniomatriceD(nxn)alecareielementereprezinta submultimi de varfuri ale lui G.Initializarea matricei D va fi de forma urmatoare:12'