Trebuie să indicăm numai partiția setului de margini ale graficului într-un factor. În acest scop, indicăm vârfurile graficului și definim seturile de margini, unde fiecare dintre indici este unul din numere; Aici suma și diferența sunt luate modulo. Este ușor de observat că setul oferă partiția necesară a setului, iar suma subgrafurilor generate de seturi este factorizarea graficului.
[edit] 2-factorizarea
Dacă graficul este factorabil, atunci fiecare dintre factorii săi trebuie să fie o uniune de cicluri disjuncte (vârfuri).
Să începem să ocolim factorul de la un anumit vârf. Să mergem de-a lungul unuia dintre margini și să ajungem la vârful adiacent al acesteia. Apoi mergem de-a lungul marginilor, pe care nu am mai trecut încă. Introducem unul câte unul și ieșim diferit, deoarece gradul fiecărui vârf este egal, până când vom reveni la primul vârf. Acesta este un ciclu, deoarece la fiecare vârf am fost doar o singură dată. Dacă există noduri pe care nu le-am vizitat, atunci începem o ocolire cu oricare dintre aceste noduri. Este imposibil să ajungeți la vârfurile ciclurilor anterioare, deoarece am trecut deja de-a lungul marginilor acestor vârfuri. Aceasta înseamnă că ciclurile nu intersectează nodurile.
Rețineți că dacă factorul este conectat, atunci acesta este un ciclu Hamiltonian.
Graficul poate fi reprezentat ca o sumă de cicluri Hamiltonian.
-factorizarea graficului. Marginile marcate cu o linie punctată nu intersectează alte margini cu stivuirea corectă a graficului.
Pentru a construi cicluri Hamiltonian într-un grafic care nu se intersectează de-a lungul marginilor, noi renumerotăm mai întâi vârfurile sale. Pe un set de vârfuri definim lanțuri simple neintersectoare după cum urmează: cel de-al doilea punct al lanțului este vârful, unde toți indiciile sunt reduse la numerele modulo. Ciclul Hamiltonian poate fi obținut prin îmbinarea vârfului cu vârfurile terminale ale lanțului.
[modifică] Observații
- Factorizarea graficelor este folosită ca una dintre metodele de construire a seturilor de acoperire utilizate pentru crearea testelor pentru programe cu un număr mare de parametri.
- -factorizarea unui grafic obișnuit este colorarea de margine a graficului.
[edit] Vezi, de asemenea
[edit] Surse de informare
Articole similare
Trimiteți-le prietenilor: