Cicluri fundamentale
O reprezentare compactă a spațiului își pune bazele. Dacă vom scrie toate ciclurile simple ale unui grafic, în majoritatea cazurilor acest lucru nu va fi baza sa, deoarece unele dintre aceste cicluri pot fi sume ale altora (a se vedea exemplul din Figura 7.1). Construiți o bază de spațiu constând în cicluri simple, după cum urmează. Alegeți un cadru în grafic. Permiteți să fie toate marginile graficului care nu aparțin. Dacă adăugați la margine, atunci în graficul rezultat se formează un singur ciclu (simplu). Astfel, obținem o familie de cicluri, se numesc cicluri fundamentale relative la schelet.
Teorema 2. Setul tuturor ciclurilor fundamentale cu privire la orice schelet al unui grafic formează baza spațiului ciclurilor acestui grafic.
Dovada. Reparăm un cadru și luăm în considerare ciclurile fundamentale relative la acest schelet. În fiecare din aceste cicluri există o margine aparținând ciclului dat și care nu aparține niciunui altul. Prin urmare, atunci când acest ciclu este adăugat la alte cicluri fundamentale, această margine nu este "distrusă" - va fi prezentă în graficul sumar. În consecință, suma diferitelor cicluri fundamentale nu va fi niciodată un grafic gol, adică ciclurile fundamentale sunt independente liniar.
Acum arătăm că fiecare quasiciclic al unui grafic este o sumă de cicluri fundamentale. Într-adevăr, să fie un quasiciclic. Lăsați să fie toate marginile care nu aparțin. Luați în considerare graficul. Fiecare dintre margini, are loc exact în doi termeni ai acestei sume - în și în. În consecință, toate aceste margini vor fi distruse atunci când sunt adăugate. Toate celelalte margini prezente în sumele grafice aparțin. Prin urmare, subgraful graficului. Deoarece toți termenii sunt cvasi-cicluri. atunci este și un cvasi-ciclu. Dar nu există cicluri, deci există doar o singură posibilitate: unde ajungem.
Din această teorem rezultă că dimensiunea spațiului ciclurilor unui grafic este egală cu numărul de muchii care nu intră în scheletul său. Deoarece scheletul conține muchii, unde este numărul de componente conectate ale graficului, această dimensiune este egală cu. Acest număr este numit numărul ciclomatic al graficului.
Construirea bazei ciclurilor
Baza spațiului ciclurilor unui grafic este numită pe scurt baza ciclurilor. Pe baza Teoremei 2, putem propune o metodă destul de simplă pentru construirea unei baze a ciclurilor unui grafic. Mai întâi, există un schelet, iar pentru fiecare margine care nu aparține scheletului, se caută singurul ciclu pe care se formează această margine cu marginile scheletului. Astfel, orice algoritm pentru construirea unui cadru poate fi folosit pentru a găsi baza ciclurilor.
Căutarea în adâncime este deosebit de convenabilă datorită proprietății principale a copacului DFS (Teorema 1 din "Căutarea în profunzime") - fiecare margine inversă față de acest arbore este longitudinală. Aceasta înseamnă că dintre cele două vârfuri ale unei astfel de margini, unul este strămoșul celuilalt în arborele DFS. Fiecare astfel de margine în procesul de căutare în adâncime se va întâlni de două ori - o dată, când vârful activ este un strămoș, celălalt moment când va fi descendent. În acest din urmă caz, ciclul fundamental necesar constă în marginea inversă luată în considerare și segmentul de cale din arborele DFS. conectând aceste două vârfuri. Dar în acest fel într-un fel sau altul memorat în procesul de trecere în profunzime. deoarece este necesar pentru returnarea ulterioară. Dacă, de exemplu, un teanc este utilizat pentru a stoca vârfuri deschise. atunci vârfurile acestei căi sunt în partea superioară a teancului. În orice caz, această cale este ușor accesibilă și ciclul este ușor. Să scriem procedura de construire a ciclurilor fundamentale pe baza algoritmului de căutare de adâncime cu construcția arborelui DFS. Variabila - contorul de cicluri, - o secvență (listă) de noduri care formează un ciclu cu un număr.
Algoritmul 1. Construirea bazei ciclurilor.
- marchează toate nodurile ca fiind noi
- pentru că atunci noi
- deschideți partea de sus
- în timp ce deschide
- dacă există o margine neexplorată
- apoi marcați marginea așa cum a fost investigată
- dacă vârful este nou
- apoi deschideți partea de sus
- altfel
- altfel închideți vârful
- Creați o listă dintr-un singur element
- repeta
- adăugați la listă
- până
Deși căutarea în sine este efectuată în profunzime pentru un timp liniar în numărul de vârfuri și muchii, influența decisivă asupra complexității acestui algoritm face necesară reținerea ciclurilor care apar. Să calculam lungimea totală a acestor cicluri pentru un grafic complet cu noduri. Arborele DFS în acest caz este un mod simplu, în raport cu acesta va exista un ciclu de lungime, o buclă de lungime de ciclu de lungime. Suma lungimilor tuturor ciclurilor fundamentale va fi
Astfel, pe unele grafice numărul de operații ale acestui algoritm va fi de ordinul mărimii.
Articole similare
Trimiteți-le prietenilor: