Ciclurile reprezintă o parte foarte importantă a structurii grafice, acestea trebuie să facă față multor probleme. Există o mulțime de cicluri în grafic (vezi problema 5.15), prin urmare este util să avem mijloacele pentru o descriere compactă a mulțimii tuturor ciclurilor unui grafic dat și pentru manipularea acestora. Unul dintre mijloacele cele mai convenabile de acest fel este furnizat de aparatul de algebră liniară.
În continuare, luăm în considerare graficele cu un set fix de vârfuri v. Noi indicăm prin O graficul gol :.
Prin suma modulo 2 (în continuare, în această secțiune vom numi pur și simplu suma) a două grafice și este un grafic, unde se denumește diferența simetrică a seturilor.
Următoarele proprietăți ale operațiunii introduse sunt evidente sau ușor de verificat.
1) Comutativitatea: pentru orice și.
2) Asociativitate: pentru orice.
3) pentru orice G.
4) pentru orice G.
Aceasta implică faptul că setul de grafice cu setul de vârfuri V formează un grup abelian sub operarea plus modulo 2. Element neutru ( „zero“), acest grup este un grafic O. opus fiecărui grafic este graficul în sine. O ecuație cu X necunoscută și graficele date G și H are o soluție unică. Datorită proprietății asociativității putem forma un fel de exprimare fără a utiliza paranteze pentru a indica ordinea operațiilor. Este ușor de observat că o margine aparține unui grafic dacă și numai dacă aparține unui număr impar de grafuri.
Luați în considerare un set de două elemente. Este câmpul în raport cu operațiile de înmulțire și modulo 2 elemente de multiplicare definesc funcționarea acestui câmp pe coloane: pentru orice grafic G. Setul de grafice cu setul de noduri V la operațiunile de intrare de adăugare și multiplicarea elementelor de grafice ale câmpului este un spațiu vectorial liniar (adică adică se supune axiomaticilor acestor spații).
Fixați un grafic și luați în considerare setul de subgrafe ale acestuia. Acest set constă din elemente, printre care graficul G și graficul. Este închisă în ceea ce privește adăugarea de grafice și înmulțirea prin elemente ale câmpului, deci este un subspațiu al spațiului tuturor grafurilor. Se numește spațiul subgrafurilor din grafic G.
În spațiul subgrafelor, se pot introduce coordonate într-un mod natural. Numărăm marginile graficului G. Acum subgraful span poate fi asociat cu vectorul caracteristic al setului său de margini:
Obținem o corespondență unu-la-unu între setul de subgrafe și setul de vectori binari n-dimensionali. Suma graficelor corespunde unei sume vectori (coordonate-înțelepte) modulo 2 a vectorilor lor caracteristici.
Restul acestei secțiuni cuvântul „ciclu“ va fi înțeles un pic diferit decât înainte de ciclul de Contele por.Imenno G budemnazyvat subgrafic său se întinde pe care are o componentă conectată este un ciclu simplu, iar restul - izolate vârfuri. Un subgraf care se întinde, a cărui grade de toate nodurile sunt plane, este numit cvasi-ciclu. Astfel, orice ciclu este un cvasi-ciclu, iar graficul G este un cvasi-ciclu.
Teorema cvasi-ciclu. Setul tuturor quasiciclurilor unui graf dat este inchis sub modulul 2 aditional.
Din această teoremă rezultă că mulțimea tuturor cvasi-ciclurilor graficului G este un subspațiu al spațiului subgrafurilor, se numește spațiul ciclului unui grafic.
O reprezentare compactă a unui spațiu vectorial liniar își oferă baza. Baza spațiului ciclurilor este pur și simplu numită baza ciclurilor. Putem construi baza ciclurilor în modul următor. Am ales în G orice T. cadru Să - toate muchiile grafului G. nu aparțin T. Dacă adăugăm la nervura T, apoi un singur ciclu în grafic rezultat. Astfel, obținem o familie de cicluri s, se numesc cicluri fundamentale în raport cu scheletul T.
Teorema ciclului fundamental Setul tuturor ciclurilor fundamentale cu privire la orice schelet T al lui G formează baza spațiului ciclului din acest grafic.
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 k este numărul de componente conectate ale graficului, această dimensiune este egală cu. Acest număr este numit numărul ciclomatic al graficului.
Graficul poate fi construit în mai multe moduri. Pentru construirea unei baze a ciclurilor unui grafic, este deosebit de convenabil să căutăm în profunzime datorită proprietății principale a unui arbore DFS - fiecare margine posterioară a acestui copac 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 care leagă aceste două noduri. Dar acest mod este oarecum amintit în procesul de traversare în profunzime, deoarece este necesar pentru revenirea ulterioară. Dacă, de exemplu, un teanc este utilizat pentru a stoca vârfuri deschise, atunci vârfurile acestei căi se află în partea de sus a stivei. În orice caz, această cale este ușor accesibilă și ciclul este ușor.
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 algoritmului face necesară reținerea ciclurilor care apar. Calculăm lungimea totală a ciclurilor fundamentale obținute prin căutarea în adâncime a unui grafic complet cu n noduri. Arborele DFS este în acest caz un mod simplu, în legătură cu acesta va exista un ciclu de lungime 3, un ciclu de lungime 4, ..., 1 ciclu de lungime n. 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.
Spațiul tăieturilor graficului este strâns legat de spațiul ciclului. Să. Tăierea graficului G. definită de mulțimea A este un subgraf care se extinde, ale cărui muchii sunt toate marginile graficului care unește vârfurile de la A la vârfurile lui.
Teorema tăiată. Setul tuturor tăieturilor unui grafic dat este închis sub modulul 2 adițional.
O secțiune definită de un singur set A este considerată a fi elementară. Baza spațiului tăieturilor unui grafic conectat poate fi obținută prin preluarea tuturor secțiunilor sale elementare, cu excepția unuia (oricui). Pentru un grafic deconectat, acest lucru trebuie făcut pentru fiecare componentă conectată. Astfel, dimensiunea spațiului tăieturilor unui grafic cu componentele k este.
Fie u vectorii caracteristici ai celor două subgrafe ale lui G. Spunem că aceste subgrafe sunt ortogonale. în cazul în care. Acest lucru este echivalent cu faptul că subgrafurile au un număr par de muchii comune.
O teoremă a ciclurilor și a tăieturilor. Orice ciclu al unui grafic dat este ortogonal oricărei tăieturi.
Deoarece suma dimensiunilor spațiilor de cicluri și tăieturi este egală cu dimensiunea spațiului subgrafelor, rezultă din această teoremă că spațiile ciclurilor și tăieturilor sunt complementare ortogonale unele cu altele. Aceasta poate fi utilizată pentru a construi o bază a ciclurilor din matricea de incidență. Să arătăm acest lucru cu un exemplu. Să se ceară să se găsească baza ciclurilor pentru graficul prezentat în Figura 8. Construim-o
matrice de incidență și eliminați una (orice) linie de la ea (în cazul unui grafic disjunct, un rând din fiecare componentă conectată este șters):
Rândurile acestei matrice sunt vectorii caracteristici ai secțiunilor elementare care formează baza tăieturilor. Deoarece spațiul ciclurilor este o completare ortogonală a spațiului de tăieturi, rămâne să găsim un sistem fundamental de soluții ale unui sistem de ecuații lineare omogene cu această matrice (pe un câmp de două elemente). Pentru a face acest lucru, folosim operațiile de pe rânduri pentru a transforma matricea astfel încât în primele coloane să se formeze o singură submatriculă:
Ștergem primele patru coloane, matricea rămasă fiind transpusă și îi atribuie o singură submatrică pe dreapta:
Rândurile matricei rezultate reprezintă o bază a ciclurilor.
Articole similare
Trimiteți-le prietenilor: