Un graf G se numeşte graf bipartit dacă există două mulţimi nevide de noduri A si B care au proprietatea: A ∩ B= Ø iar A U B=X şi orice muchie din mulţimea U are o extremitate în mulţimea A şi o altă extremitate în mulţimea B.
Un graf bipartit se numeşte graf bipartit complet dacă pentru oricare nod X care aparţine mulţimii A şi orice nod Y care aparţine mulţimii B există o muchie care le leagă.
Un graf care conţine un ciclu Hamiltonian se numeşte graf Hamiltonian.
Un ciclu se numeşte eulerian,ciclul elementar ce conţine toate muchiile grafului.
Se numeşte graf eulerian,graful care conţine un ciclu eulerian.
TEOREME
1) Un graf cu mai mult de 2 noduri este Hamiltonian dacă graful fiecărui nod este mai mare sau egal decât n/2.
2) Un graf ce nu conţine vârfuri izolate este eulerian dacă şi numai dacă este conex iar gradele tuturor noduriilor sunt numere pare.
3) Numărul de cicluri hamiltoniene dintr-un graf complet cu n noduri este (n-1)!/2.
Niciun comentariu:
Trimiteți un comentariu