MOBILE (TGAMSM) MASTER MODELAREA ȘI SIMULAREA SISTEMELOR MECANICE MOBILE Șl.dr.ing. Ileana DUGĂEȘESCU Algoritm pentru calculul drumuril ordintr… [609091]

TEORIA GRAFURILOR CU APLICATII
IN MODELAREA STRUCTURILOR
MOBILE (TGAMSM) MASTER MODELAREA ȘI SIMULAREA SISTEMELOR MECANICE MOBILE
Șl.dr.ing. Ileana DUGĂEȘESCU

Algoritm pentru calculul drumuril ordintr -ungraf orientat cuunnumar finit denoduri
•Se construieste matricea booleana a adiacentelor directe corespunzatoare grafului , notata cu A -înaceasta se
găsesc toate drumurile de lungime 1.
•Fiedouănoduri xisixjoarecare dingraf.Existen țaunui drum delungime 2întreelepresupune existen țaunui
nod xk,dingraf,cuproprietatea căexist ăarcele(xi,xk)și(xi,xk).Severific ădacăelementul depepozitia (i,j)
dinmatricea A2este egal cu1.
•Existen țaunui drum delungime 3delaxilaxjpresupune existen țaunui nod xkastfel încâtsăexiste undrum
delungime 2delaxilaxksiunarcdelaxklaxj,care esteechivalent cuaverifica daca exista vreun indice k
astfel incat elementul kalliniei idinmatricea A2sielementul kalcoloanei jdin Asunt ambele egale cu1
sau,maisimplu ,daca elementul (i,j)dinA3este 1.
Adunarea booleană Înmulțirea booleană

EXEMPLU
Se consider ă graful orientat din figura alăturată.
Se elaborează matricea de adiacență (MA).

Matricea MA are forma:
Se calculează
Se calculează
Înacest cazs-auobținut două valori
egale cu1,deci există două drumuri
delungime 2.Un drum de la 1la 3–1-2-3;
Un drum de la 1la 4–1-3-4;
Înacest caz s-aobținut ovaloare
egală cu1,deci există undrum de
lungime 3.Un drum de la 1la 4–1-2-3-4;

Senumește drum (path)delanodul xlanodul y,osecvență denoduri n1,n2,…,njîncare nodurile
succesive sunt conectate prinarce aparținând grafului .
Unciclu (buclă )esteundrum simplu delungime celpuțin 1,care începe șisesfârșește înacelași nod.
Ciclul senumește elementar dacă nuconține demaimulte oriacelași vârf (exceptând extremitățile sale) .Un lanț esteelementar dacă el nu conține de maimulte oriacelași vârf.
Un lanț estesimplu dacă el nu conține de maimulte oriaceeași muchie .
Se numește ciclu un lanțsimplu pentru care extremitatea inițială coincide cu extremitatea finală . Se numește lungime a unui lanțnumărul de muchii conținute .

Graf neorientatMulțimea vârfurilor: V= {1,2,3,4,5}
Mulțimea muchiilor : M= {[1,2],[1,3],[1,5],[2,3],[3,4],[4,5]}
Lanț neelementar (trece de două ori prin vârful 1): 1,2,3,1,5 –lungime 4;
Lanț elementar (trece o singură dată prin vârfuri): 1,2,3,4 –lungime 3;Lanț neelementar (trece de două ori prin vârful 1): 1,2,3,1,5,4 –lungime 5;
Nu este lanț: 1,2,3,5.
Ciclu elementar: [1,2,3,1];
Ciclu elementar: [1,2,3,4,5,1];
Ciclu elementar: [1,3,4,5,1];
Ciclu neelementar: [1,2,3,1,5,4,3,1];În cadrul unuilanț muchiile se pot repeta , darîncadrul unui ciclu eletrebuie
săfie distincte .෍𝑔𝑟𝑎𝑑=3+2+3+2+2=12

Graf neorientatMatricea de adiacen ță
1.Este o matrice simetric ăfață de diagonala principală;
2. Elementele de pediagonala principal ăsunt egale cu 0;
3. Suma elementelor peliniesaucoloan ăeste egalăcu
gradul nodului ;
4. Daca toate elementele sunt egale cu 1 mai putin cele
de pediagonala principală atunci graful este complet .Propriet ățilematricei de adiacență :
Lista vecinilor
Gradul unui nod este egal cu numărul muchiilor adiacente nodului .
Construim matricea de adiacen țășisuma de ‘1’ de pefiecare linie este egal cu gradul
nodului ide pelinia i.
Un graf fără vârfuri izolate este eulerian dacă șinumai dacă este conex șigradele tuturor vârfurilor sunt numere
pare.

Reprezentarea prin corespondență
Graf neorientat
•Într-un graf simplu există cel puțin două vârfuri (noduri) cu același grad. 1 și3;
2, 4 și5.
•Suma gradelor vârfurilor (nodurilor) reprezintă dublul muchiilor. mc=6;෍𝑔𝑟𝑎𝑑=3+2+3+2+2=12
•În orice graf numărul vârfurilor (nodurilor) de grad impar este par. Vârfurile (nodurile) cu grad impar sunt 1 și3.

•Numărul de muchii într-un graf complet = n*(n–1)/2 ;
•Numărul grafurilor neorientate cu nvârfuri este 2 n(n-1)/2 ;
•Numărul grafurilor parțialepeste un graf cu mmuchii este 2 m.
•Un graf neorientat cu n vârfuri , încare gradul oricărui vârf este mai mare sauegal cu n/2 este hamiltonian .
•Num ărultotal de grafuri cu nnoduri este
•Num ărulminim demuchii pecare trebuie săleaibăungraf neorientat cunnoduri ,casănuexiste noduri
izolate este:

ALGORITMUL ÎNMULȚIRII LATINE. ALGORITMUL KAUFMANN
Să se determine drumurile de lungime 2 și3 a grafului din figura de mai jos.
Matricea de adiacen ță
Se scrie matricea legăturilor posibile
Graf neorientatV1 V2
V5
V4
V3

M2 M1v M1=M1v
x
Se calculează

S-au obținut 12 drumuri de lungime 2 șianume:
D(1)=(v1,v2,v3) D(2)=(v1,v3,v4) D(3)=(v1,v5,v4) D(4)=(v1,v2,v5) D(5)=(v2,v5,v1) D(6)=(v2,v3,v4)
D(7)=(v2,v5,v4) D(8)=(v3,v4,v5) D(9)=(v4,v5,v1) D(10)=(v5,v1,v2) D(11)=(v5,v1,v3) D(12)=(v5,v4,v3)

Se calculează
x

S-au obținut 11 drumuri de lungime 2 șianume:
D1=(v1,v5,v4,v3) D2=(v1,v2,v3,v4) D3=(v1,v2,v5,v4) D4=(v1,v3,v4,v5) D5=(v2,v5,v1,v3)
D6=(v2,v5,v4,v3) D7=(v3,v4,v5,v1) D8=(v4,v5,v1,v2) D9=(v4,v5,v1,v3) D10=(v5,v1,v2,v3) D11=(v5,v1,v3,v4)

BIBLIOGRAFIE
[1]Comănescu , Adr., Comănescu , D., Dugăeșescu I., Boureci , A., Bazele modelării mecanismelor , Editura Politehnica Press, București , 2010;
[2] Cornelia Ivasc , Mona Pruna , Bazele informaticii ( Grafuri sielemente de combinatorica ). Manual pentru licee /clasele de informatica clasa a X, Editura
Petrion , Bucuresti , 1995
[3] Daniela Oprescu , Liana Bejan Ienulescu,Viorica Patrascu , Manual Informatica clasa a XI, Editura Niculescu , anul 2000
[4] Manolescu , N.I., Teoria mecanismelor sia mașinilor (Note de curs), 4 volume, Litografia Institutului de CaiFerate , București , 1955 -1956
[5]Milosescu Mariana, Manual Informatica clasa a XI, Editura Didactică și Pedagogică, București, anul 2008
[6]Pelecudi , Chr., Precizia mecanismelor, Editura Academiei Republicii Socialiste Romania, 1975,
[7] Pelecudi , Chr., Bazele analizei mecanismelor , Editura Academiei Republicii Socialiste Romania,1967
[8]Tudor Sorin, Manual Informatica clasa a XI, Editura L&S Infomat , Bucuresti ,anul 2000
[9]Tudor Sorin, Tehnici de programare, Manual Informatica clasa a X, Editura L&S Infomat , Bucuresti ,anul 1996
[10] Vlad Hutanu si Tudor Sorin, Manual Informatica clasa a XI, Editura L&S Soft, Bucuresti ,anul 2002
[11] http://www.cursuri.flexform.ro
[12] http://www.seap.usv.ro/~valeriul/lupu/GRAFURI_NEORIENTATE.pdf
[13] http://webspace.ulbsibiu.ro/adrian.florea/html/Planificari/Planificare_Grafuri.pdf
[14] campion.edu.ro/arhiva/www/arhiva_2009/ seds/17/index.htm