Rangul contur

În teoria grafurilor, rangul de contur [1] al unui graf nedirecționat este numărul minim de muchii a căror îndepărtare distruge toate ciclurile grafului, transformându-l într- un copac sau pădure. Rangul conturului poate fi, de asemenea, înțeles ca numărul de cicluri independente dintr-un grafic. Spre deosebire de problema corespunzătoare de găsire a unui set de arce de tăiere a ciclului pentru grafice direcționate , rangul de contur r este ușor de calculat prin formula

unde m este numărul de muchii ale graficului dat, n este numărul de vârfuri și c este numărul de componente conexe [2] . De asemenea, este posibil să se construiască eficient un set de muchii de dimensiune minimă care întrerup ciclurile utilizând fie algoritmul lacom, fie complementul arborelui de acoperire .

Rangul conturului este cunoscut și ca număr ciclomatic al unui grafic. Poate fi explicat în termenii teoriei grafurilor algebrice ca dimensiune a spațiului ciclic al unui graf, în termeni de matroizi folosind noțiunea de coranc a matroidelor de graf [3] , și în termeni de topologie ca unul dintre Betti . numerele unui spațiu topologic derivat dintr-un grafic. Rangul de contur numără numărul de urechi dintr-o descompunere a urechii a unui grafic, care oferă baza pentru noțiunea de complexitate pe aproape arbori și este utilizat în metrica software ca parte a definiției complexității ciclomatice a unei bucăți de cod. Sub denumirea de complexitate ciclomatică, conceptul a fost introdus de Gustav Kirchhoff [4] [5] .

Rangul Matroid și construcția unui set minim de tăiere a ciclului

Rangul de contur al unui graf G poate fi descris folosind teoria matroidei ca corrank al unui graf matroid pentru G [6] . Ținând cont de proprietatea greedy a matroidelor, aceasta înseamnă că este posibil să găsim setul minim de muchii care distruge toate ciclurile folosind algoritmul greedy , care selectează la fiecare pas o muchie care aparține cel puțin unui ciclu din graficul rămas.

Pe de altă parte, setul minim de mulțimi care întrerupe toate ciclurile poate fi găsit prin construirea unei păduri spanning de G și alegerea unui set complementar de muchii care nu aparțin pădurii spanning.

Numărul de cicluri independente

În teoria grafurilor algebrice , rangul conturului este dimensiunea spațiului ciclului unui graf . Intuitiv, rangul conturului poate fi explicat ca numărarea numărului de cicluri independente ale unui grafic, unde un set de cicluri este considerat independent dacă este imposibil să se formeze un ciclu ca diferență simetrică a unui subset de alte cicluri [2] .

Acest număr de cicluri independente poate fi explicat folosind teoria omologiei , o ramură a topologiei . Orice grafic G poate fi privit ca un exemplu de complex simplic unidimensional , un tip de spațiu topologic , format prin reprezentarea fiecărei margini a graficului printr-un segment și lipirea acestor segmente la capete. Numărul ciclomatic este rangul primului grup de omologie (întreg) al acestui complex [7] ,

În legătură cu o astfel de conexiune topologică, numărul ciclomatic al graficului G este numit și primul număr Betti al graficului G [8] . Mai general, primul număr Betti al oricărui spațiu topologic numără numărul de cicluri independente din spațiu.

Rangul de contur al unui grafic este legat de rangul matricei sale de incidență prin relația .

Aplicații

Coeficientul de reticulare

O variantă a rangului de contur al unui graf plan , normalizată prin împărțirea la rangul de contur maxim posibil al oricărui graf plan cu același set de vârfuri, se numește factor de rețea . Pentru graficele plane conectate cu m muchii și n vârfuri, coeficientul de rețea poate fi calculat folosind formula [9]

În această formulă, numărătorul din formulă este rangul de contur al graficului dat, iar numitorul este cel mai mare rang de contur posibil al unui grafic plan cu n vârfuri. Factorul de plasă este între 0 pentru arbori și 1 pentru graficele plane maxime .

Descompunerea urechii

Rangul de contur reflectă numărul de urechi în descompunerea graficului, descompunerea marginilor graficului în căi și cicluri, care este adesea utilă în algoritmii graficului. În special, un grafic este conectat la vârful 2 dacă și numai dacă are o descompunere a urechii deschise, o secvență de subgrafe în care primul subgraf este un ciclu simplu, iar subgrafele rămase sunt căi simple și fiecare cale începe și se termină la vârfuri. aparținând subgrafelor anterioare și fiecare vârf interior al căii apare pentru prima dată în acel drum. În orice grafic biconectat cu rang de contur, orice descompunere a urechii deschise are exact urechi [10] .

Aproape copaci

Un grafic cu un număr ciclomatic se mai numește și un arbore aproape r , deoarece doar marginile r trebuie îndepărtate din grafic pentru a-l transforma într-un copac sau o pădure. Un aproape 1 copac este aproape un copac — un aproape copac conectat este o pseudopădure , un ciclu cu copaci (posibil banali) înrădăcinați la fiecare vârf [11] .

Unii autori au studiat complexitatea parametrizată a algoritmilor pe aproape r -arbori cu parametrizare conform [12] [13] .

Generalizare pentru grafice direcționate

Rangul ciclic este un invariant de grafic direcționat care măsoară nivelul de imbricare a ciclurilor într-un grafic. Acest invariant are o definiție mai complicată decât rangul ciclomatic (strâns legat de definiția adâncimii arborelui pentru graficele nedirecționate) și este mult mai dificil de calculat. O altă problemă pentru graficele direcționate legate de rangul ciclomatic este determinarea setului minim de arc de tăiere a ciclului , adică setul minim de arce a căror îndepărtare distruge toate ciclurile direcționate. Ambele probleme, calcularea rangului ciclic și determinarea setului minim de arce care taie ciclurile, sunt NP-hard .

De asemenea, este posibil să se calculeze un invariant mai simplu al graficelor direcționate ignorând direcțiile marginilor și calculând rangul ciclic al unui grafic nedirecționat. Acest principiu formează baza pentru definirea complexității ciclomatice , o măsură a complexității programului de calculator pentru estimarea complexității unei bucăți de cod de calculator.

Concepte înrudite

Alte numere definite în ceea ce privește eliminarea muchiilor dintr-un grafic nedirecționat includ conectivitatea muchiilor , numărul minim de muchii a căror eliminare provoacă pierderea conectivității și numărul de evitare a potrivirii , numărul minim de muchii a căror eliminare determină încetarea potrivirii perfecte a exista .

Note

1. ↑ În literatura în limba rusă, atât rangul de ciclu, cât și rangul de circuit sunt adesea traduse în același mod - rang ciclic. În literatura engleză, primul termen se referă la grafice direcționate, al doilea la grafice nedirecționate. În acest articol, termenul „rang ciclic” este folosit pentru graficele direcționate și „rang de contur” pentru graficele nedirecționate.
2. ↑ 12 Berge , 2001 , p. 27–30.
3. ↑ În literatura în limba rusă, se folosește și termenul de matroid grafic , care este o hârtie de calc a matroidei grafice engleze și nu corespunde în totalitate esenței conceptului.
4. ↑ Kotiuga, 2010 , p. douăzeci.
5. ↑ Hage, 1996 , p. 48.
6. ↑ Berge, 1976 , p. 477.
7. ↑ Serre, 2003 , p. 23.
8. ↑ Berkolaiko, Kuchment, 2013 , p. patru.
9. ↑ Buhl, Gautrais, Sole et al., 2004 , p. 123–129.
10. ↑ Whitney, 1932 , p. 339–362.
11. ↑ Brualdi, 2006 , p. 349.
12. ↑ Calămarul, Vișkin, 1985 , p. 27–45.
13. ↑ Fiala, Kloks, Kratochvíl, 2001 , p. 59–72.

Literatură

• Claude Berge. Teoria graficelor. - Publicațiile Courier Dover, 2001. - ISBN 9780486419756 .
• Claude Berge. Grafice și hipergrafe. - Elsevier, 1976. - V. 6. - (Biblioteca de matematică din Olanda de Nord). — ISBN 9780720424539 .
• C. Berge. Teoria grafurilor și aplicarea acesteia.
• J. Buhl, J. Gautrais, R. V. Sole, P. Kuntz, S. Valverde, J. L. Deneubourg, G. Theraulaz. Eficiență și robustețe în rețelele de galerii de furnici // The European Physical Journal B-Condensed Matter and Complex Systems. - Springer-Verlag, 2004. - T. 42 , nr. 1 . — S. 123–129 . - doi : 10.1140/epjb/e2004-00364-9 .
• H. Whitney. Grafice neseparabile și plane // Tranzacții ale Societății Americane de Matematică . - 1932. - T. 34 . — S. 339–362 . - doi : 10.2307/1989545 . Vezi teoremele 18 (conectarea descompunerii urechii cu rangul ciclic) și 19 (despre existența descompunerii urechii)
• Richard A. Brualdi. clase de matrice combinatorii. - Cambridge: Cambridge University Press , 2006. - V. 108. - P. 349. - (Encyclopedia of Mathematics and Its Applications). — ISBN 0-521-86565-4 .
• Don Coppersmith, Uzi Vishkin. Rezolvarea problemelor NP-hard în „aproape copaci”: acoperire cu vârfuri // Matematică aplicată discretă. - 1985. - T. 10 , nr. 1 . — S. 27–45 . - doi : 10.1016/0166-218X(85)90057-5 .
• Peter Robert Kotiuga. O sărbătoare a moștenirii matematice a lui Raoul Bott. - American Mathematical Soc., 2010. - P. 20. - ISBN 978-0-8218-8381-5 .
• Pe vârstă. Rețele insulare: Structuri de comunicare, rudenie și clasificare în Oceania. - Cambridge University Press, 1996. - P. 48. - ISBN 978-0-521-55232-5 .
• Jean-Pierre Serre. copaci. - Springer, 2003. - P. 23. - (Monografii Springer în matematică).
• Gregory Berkolaiko, Peter Kuchment. Introducere în graficele cuantice. - American Mathematical Soc., 2013. - P. 4. - ISBN 978-0-8218-9211-4 .