Pseudo-pădure

În teoria grafurilor, o pseudopădure este un graf nedirecționat [1] în care orice componentă conexă are cel mult un ciclu . Adică, este un sistem de vârfuri și muchii care conectează perechi de vârfuri, astfel încât două cicluri să nu aibă vârfuri comune și să nu poată fi conectate printr-o cale. Un pseudo -arbore este o pseudo-pădure conectată.

Numele sunt luate prin analogie cu arbori și păduri bine-cunoscute (un copac este un grafic conectat fără cicluri, o pădure este o uniune de arbori deconectați). Gabov și Tarjan [2] atribuie studiul pseudopădurilor cărții lui Danzig din 1963 despre programarea liniară , în care pseudopădurile apar în rezolvarea unor probleme de flux de trafic [3] . Pseudopădurile formează și modele grafice teoretice ale funcțiilor și apar în unele probleme algoritmice . Pseudopădurile sunt grafice rare - au foarte puține muchii în raport cu numărul de vârfuri, iar structura lor matroide permite ca și alte familii de grafice rare să fie descompuse într-o uniune de păduri și pseudopăduri. Denumirea „pseudo-pădure” provine dintr-un articol al lui Picard și Keran [4] .

Definiții și structură

Definim un graf nedirecționat ca un set de vârfuri și muchii astfel încât fiecare muchie să conțină două vârfuri (posibil care se potrivesc) ca puncte finale. Adică, sunt permise mai multe muchii (muchii cu aceleași vârfuri de capăt) și bucle (muchii ale căror vârfuri de capăt sunt aceleași) [1] . Un subgraf al unui graf este un grafic format dintr-un submult de vârfuri și muchii, astfel încât orice muchie din acel submult are vârfuri terminale în submulțimea de vârfuri. O componentă conexă a unui graf nedirecționat este un subgraf format din vârfuri și muchii la care se poate ajunge urmărind muchiile pornind de la un vârf de pornire. Un grafic este conectat dacă orice vârf sau muchie poate fi atins de la orice alt vârf sau muchie. Un ciclu într-un graf nedirecționat este un subgraf conex în care orice vârf este incident la exact două muchii sau este o buclă.

O pseudopădure este un grafic nedirecționat în care fiecare componentă conectată conține cel mult un ciclu [5] . În mod echivalent, este un graf nedirecționat în care fiecare componentă conexă nu are mai multe muchii decât vârfuri [6] . Componentele care nu au cicluri sunt doar arbori , iar componentele care au un singur ciclu se numesc 1-arbori sau grafice cu un singur ciclu . Adică, un arbore 1 este un grafic conectat care conține exact un ciclu. O pseudopădure cu o singură componentă conectată (denumită în mod obișnuit pseudoarbore , deși unii autori definesc un pseudoarbore ca fiind un arbore 1) este fie un copac, fie un arbore 1. În general, o pseudopădure poate conține mai multe componente conectate, toate fiind copaci sau 1-copaci.

Dacă eliminăm una dintre marginile buclei din 1-arborele, obținem un arbore ca rezultat. În direcția opusă, dacă adăugăm o nouă muchie arborelui care leagă oricare două vârfuri, obținem un arbore 1. Calea arborelui care conectează cele două puncte finale ale arcului adăugat, împreună cu arcul adăugat însuși, formează un singur ciclu de 1 arbore. Dacă adăugăm o muchie la arborele 1 care leagă unul dintre vârfurile arborelui cu vârful nou format, rezultatul va fi din nou un arbore 1 cu încă un vârf. O altă metodă de construire a arborilor 1 începe cu un singur ciclu, iar vârfurile sunt adăugate secvenţial la arborele 1 de un număr arbitrar de ori. Marginile oricărui 1 arbore pot fi împărțite în mod unic în două subgrafe, dintre care unul este un ciclu, iar al doilea este o pădure, iar fiecare arbore de pădure conține exact un vârf de ciclu [7]

Sunt studiate și tipuri ceva mai înguste de pseudopăduri.

O 1-pădure , numită uneori pseudopădure maximă , este o pădure la care nu se poate adăuga nicio margine fără a forma un grafic cu mai mult de un ciclu. Dacă o pseudopădure conține un copac ca una dintre componentele sale, nu poate fi o pădure 1, deoarece puteți adăuga o margine la acea componentă pentru a parcurge acea componentă sau puteți adăuga o margine care unește arborele cu o altă componentă. Astfel, 1-păduri sunt exact pseudo-păduri în care fiecare componentă este un 1-copac. O pseudopădure a unui grafic nedirecționat G este un subgraf care este o pseudopădure, adică o pseudopădure a graficului G care conține toate vârfurile graficului G. Asemenea pseudopăduri nu trebuie să aibă muchii, deoarece, de exemplu, un subgraf gol (adică care conține toate vârfurile graficului G și nu are margini) este o pseudopădure (și componentele sale sunt copaci, fiecare dintre ele format a unui singur vârf). Pseudopădurile maxime ale lui G sunt subgrafele lui G care sunt pseudopăduri care nu sunt conținute în nicio pseudopădure mai mare conținută în G . Pseudopădurea maximă a unui grafic G este întotdeauna un pseudoarbore care se întinde, dar invers nu este adevărat. Dacă G nu are componente conectate care să fie copaci, atunci pseudopădurile sale maxime sunt 1-păduri, dar dacă G are un copac ca componentă, atunci pseudopădurile sale maxime nu vor fi 1-păduri. Mai precis, în orice grafic G , pseudopădurile sale maxime constau din toate pădurile lui G împreună cu unul sau mai mulți arbori 1 care acoperă vârfurile rămase ale lui G .

Pseudopăduri orientate

Versiunile acestor definiții sunt folosite și pentru graficele direcționate . Ca și graficele nedirecționate, graficele direcționate sunt formate din vârfuri și muchii, dar fiecare muchie are o direcție (o muchie direcționată este de obicei numită arc). O pseudopădure direcționată este un grafic direcționat în care fiecare vârf are cel mult un arc de ieșire. Adică, graficul are un grad de rezultat care nu depășește unu. O 1-pădure direcționată , numită adesea graf funcțional (vezi mai jos ) și uneori pseudopădure direcționată maxim , este un graf direcționat în care fiecare vârf are un grad exterior de exact unul [8] . Dacă D este o pseudopădure direcționată, graficul nedirecționat format prin eliminarea direcțiilor de la marginile lui D este o pseudopădure nedirecționată.

Număr de muchii

Orice pseudopădure de pe un set de n vârfuri are cel mult n muchii, iar orice pseudopădure maximă de pe un set de n vârfuri are exact n vârfuri. În schimb, dacă un graf G are proprietatea că pentru orice submulțime S de vârfuri de graf, numărul de muchii dintr-un subgraf generat al graficului S nu depășește numărul de vârfuri ale graficului S , atunci G este o pseudopădure. 1-arborele pot fi definiți ca grafice conectate cu același număr de vârfuri și muchii [2] .

Pentru familiile de grafuri, dacă o familie de grafuri are proprietatea că orice subgraf al unui graf din familie este în aceeași familie și fiecare graf din familie nu are mai multe muchii decât vârfuri, atunci familia conține doar pseudopăduri. De exemplu, orice subgraf al unui trackle (un grafic desenat în așa fel încât orice pereche de muchii să aibă un punct de intersecție) este, de asemenea, un trackle, astfel încât ipoteza lui Conway că orice trackle nu are mai multe muchii decât vârfuri poate fi reformulată că fiecare trackle este o pseudopădure. Mai precis, dacă presupunerea este adevărată, atunci trekles sunt exact pseudopăduri fără cicluri cu patru vârfuri și cel mult un ciclu cu un număr impar de vârfuri [9] [10] .

Strainu și Teran [11] au generalizat proprietățile rarii în definiția pseudopădurilor - definește un grafic ca ( k , l )-spars dacă orice subgraf nevid cu n vârfuri are cel mult kn  -  l muchii și ( k , l )-dens dacă ( k , l )-rar și are exact kn  −  l muchii. Astfel, pseudopădurile sunt grafice rare (1,0), iar pseudopădurile maxime sunt grafice dense (1,0). Alte familii importante de grafice pot fi definite pentru alte valori ale lui k și l , iar dacă l  ≤  k , ( k , l )-grafice rare pot fi descrise ca grafice formate prin unirea dintre pădurile fără margini și k  -  l pseudopăduri [12] .

Aproape orice graf aleator suficient de rar este o pseudopădure [13] . Adică, dacă c este o constantă (0 < c < 1/2) și P c ( n ) este probabilitatea ca un grafic ales aleatoriu dintre graficele cu n vârfuri și cn muchii să fie o pseudopădure, atunci P c ( n ) tinde la unu în limită pe măsură ce n crește . Cu toate acestea, pentru c > 1/2, aproape orice grafic aleatoriu cu margini cn are o componentă mare, care nu are un singur ciclu.

Enumerare

Un grafic este simplu dacă nu are bucle sau margini multiple. Numărul de 1-arbori simpli cu n vârfuri etichetate este [14]

Valorile pentru n până la 18 pot fi găsite în secvența Encyclopedia of Integer Sequences A057500 .

Numărul de pseudopăduri de n -vertex maxim direcționate în care sunt permise bucle este n n , deoarece pentru orice vârf există n vârfuri de capăt posibile ale arcelor de ieșire. André Joyal a folosit acest fapt pentru a demonstra în mod bijectiv [15] formula lui Cayley că numărul de arbori nedirecționați pe n vârfuri este egal cu n n  - 2 prin găsirea unei bijecții între pseudopăduri orientate maxim și arbori nedirecționați cu două vârfuri diferite . 16] . Dacă sunt permise bucle, numărul maxim de pseudopăduri direcționate este ( n  − 1) n .

Grafice de funcții

Pseudopădurile direcționate și autohărțile sunt într-un anumit sens echivalente din punct de vedere matematic. Orice mapare a lui ƒ pe o mulțime X pe sine (adică un endomorfism pe X ) poate fi interpretată ca definiția unei pseudopăduri direcționate care are un arc de la x la y atunci când ƒ( x ) = y . Pseudopădurea direcționată rezultată este maximă și poate include bucle dacă pentru unele x ƒ( x ) = x . Eliminarea buclelor duce la pseudopăduri non-maximale. În direcția opusă, orice pseudopădure orientată maximal definește o mapare ƒ pentru care ƒ( x ) este egal cu vârful final al arcului care iese din x și orice pseudopădure orientată maximal poate fi făcută maximă prin adăugarea de bucle și conversia într-o funcție în la fel. Din acest motiv, pseudopădurile direcționate maximal sunt uneori numite grafice funcționale [2] . Reprezentarea unei funcții ca grafic funcțional oferă un limbaj convenabil pentru descrierea proprietăților care nu sunt ușor de descris din punctul de vedere al teoriei funcțiilor. Această tehnică este utilă în special pentru problemele care implică funcții iterate , care corespund căilor din teoria grafurilor.

Căutarea ciclului , problema trasării căilor într-un grafic funcțional pentru a găsi un ciclu în el, are aplicații în criptografie și teoria numerelor computaționale ca parte a ro-algoritmului lui Pollard pentru factorizarea întregilor și ca metodă de găsire a coliziunilor în hash criptografic . funcții . Aceste aplicații presupun că ƒ este aleatoriu. Flajolet și Odlyzhko [17] au studiat proprietățile graficelor funcționale obținute din mapări aleatorii. În special, o versiune a paradoxului zilei de naștere implică faptul că într-un graf funcțional aleatoriu cu n vârfuri, calea pornind de la un vârf ales aleatoriu, de obicei, se face buclă după O(√ n ) pași. Konyagin și colab. au efectuat analize și studii statistice computaționale [18] .

Martin, Odlyzko și Wolfram [19] au explorat pseudopădurile care modelează dinamica automatelor celulare . Acestea sunt grafice funcționale, le-au numit diagrame de tranziție de stare , au câte un vârf pentru fiecare configurație posibilă în care pot fi localizate celulele automatului celular, iar arcele conectează fiecare configurație care se obține din acesta conform regulilor automatului celular. Este posibil să se obțină proprietăți automate din structura acestor diagrame, cum ar fi numărul de componente, lungimea ciclurilor finite, adâncimea arborilor care leagă stările nefinale ale acestor cicluri sau simetria diagramei. De exemplu, orice vârf fără un arc de intrare corespunde Grădinii Edenului , în timp ce vârfurile cu o buclă corespund unei naturi moarte .

O altă aplicație timpurie a graficelor funcționale este în lanțuri [20] utilizate pentru studiul sistemelor triple Steiner [21] [22] [23] . Un lanț de triple este un grafic funcțional care conține un vârf pentru fiecare triplu posibil de caractere. Fiecare triplu pqr este mapat de funcția ƒ la stu , unde pqs , prt și qru  sunt triple aparținând sistemului triplu și conțin perechile pq , pr și , respectiv, qr . Lanțurile s-au dovedit a fi un invariant puternic al unui sistem triplu, deși calculul lor este greoi.

Matroida biciclică

Un matroid este o structură matematică în care anumite mulțimi de elemente sunt definite ca independente, în sensul că mulțimile independente satisfac proprietăți care modelează proprietățile independenței liniare într-un spațiu vectorial . Unul dintre exemplele standard de matroizi este graph matroid , în care seturile independente sunt seturile de muchii din pădurile grafului. Structura matroidei a pădurilor este importantă pentru algoritmii de calcul al arborelui de acoperire minim al unui grafic. Într-un mod similar se pot defini matroizi pentru pseudopăduri.

Pentru orice grafic G = ( V , E ), putem defini un matroid pe muchiile lui G în care mulțimea muchiilor este independentă dacă și numai dacă această mulțime formează o pseudopădure. Acest matroid este cunoscut ca matroidul biciclic al graficului G [24] [25] . Seturile minime dependente pentru acest matroid sunt subgrafele minime conectate ale lui G care au mai mult de un ciclu, iar aceste subgrafe sunt uneori numite biciclete. Există trei tipuri posibile de biciclete - graficul theta are două vârfuri conectate prin trei căi care nu au puncte comune interne, „opt” constă din două cicluri care au un vârf comun, iar „cătușele” sunt formate din două cicluri care nu nu au vârfuri comune, legate prin [ 26] . Un graf este o pseudopădure dacă și numai dacă nu conține o bicicletă ca subgraf [11] .

Minori ilegali

Formarea unei pseudopăduri minore prin contractarea unor margini și îndepărtarea altor margini formează o nouă pseudopădure. Astfel, familia pseudopădurilor este închisă în minori și din teorema Robertson-Seymour rezultă că pseudopădurile pot fi descrise în termenii unui set finit de minori interziși , similar teoremei Wagner de a descrie grafurile plane ca grafuri care nu au niciunul. un grafic complet K 5 și nici un grafic complet bipartit K 3.3 ca minori. După cum sa discutat mai devreme, orice grafic non-pseudoforest conține fie cătușe, cifra opt, fie theta ca subgraf. Orice „cătușe” și „opt” pot fi contractate la un „fluture” („opt” cu cinci vârfuri), iar orice grafic „theta” poate fi contractat la un „ diamant ” (grafic „theta” cu patru vârfuri) [27 ] , astfel încât orice grafic care nu este o pseudopădure conține fie un „fluture” fie un „diamant” ca minor și doar aceste grafice sunt grafice minime care nu aparțin familiei pseudopăduri. Dacă doar „diamantul” este interzis, dar nu „fluturele”, obținem o familie mai largă de grafice, constând din „cactuși” și o unire disparată a unui set de „cactuși” [28] .

Dacă luăm în considerare multigrafele cu bucle , există un singur minor interzis, un vârf cu două bucle.

Algoritmi

O aplicație algoritmică timpurie a pseudopădurilor a folosit algoritmul de rețea simplex și aplicarea acestuia la problema generalizată a fluxului de rețea pentru a modela transformările produselor de la un tip la altul [3] [29] . În aceste probleme este definită o rețea de transport , în care vârfurile modelează fiecare produs, iar marginile modelează admisibilitatea transformării de la un produs la altul. Fiecare margine este etichetată cu randament (cantitatea de produs care poate fi convertită pe unitatea de timp), flux (rata de conversie între produse) și preț (cât pierdem în conversie per unitate de produs). Provocarea este de a determina cât de mult din fiecare produs trebuie convertit pe fiecare arc al rețelei de transport pentru a minimiza costurile sau a maximiza veniturile fără a încălca constrângerile și pentru a nu permite niciun tip de produs să rămână neutilizat. Acest tip de problemă poate fi formulată ca o problemă de programare liniară și rezolvată folosind metoda simplex . Soluțiile intermediare obținute din acest algoritm, precum și soluția optimă finală, au structuri speciale - fiecare arc al rețelei de transport fie nu este utilizat, fie utilizează lățimea de bandă maximă, cu excepția unui subset de arce care formează pseudopădurea de bază a rețelei de transport. rețeaua de transport, iar pe acest subset de arce fluxul poate lua o valoare de la zero până la debitul maxim. În această aplicație, graficele cu un singur ciclu sunt uneori numite și arbori augmentați , iar pseudopădurile maxime sunt numite și păduri augmentate [29] .

Problema pseudopădurii care se întinde minim folosește găsirea unei pseudopăduri cu greutate minimă într-un grafic mai mare G cu ponderi. Datorită structurii matroide a pseudopădurilor, pseudopădurile maxime cu greutate minimă pot fi găsite folosind algoritmi lacomi, similari cu problema arborelui de întindere minimă . Cu toate acestea, Gabov și Tarjan au găsit o abordare mai eficientă în timp liniar pentru acest caz [2] .

Pseudo-treeness al unui grafic G este definit prin analogie cu arboreness ca numărul minim de pseudopăduri în care marginile pot fi împărțite. În mod echivalent, este numărul minim k astfel încât graficul G să fie ( k , 0)-rar, sau numărul minim k astfel încât marginile graficului G să poată fi direcționate astfel încât graficul direcționat rezultat să aibă cel mult un grad în afara k . Datorită structurii matroide a pseudopădurilor, pseudoarborele poate fi calculată în timp polinomial [30]

Un graf bipartit aleatoriu cu n vârfuri pe fiecare dintre părțile sale cu cn muchii alese aleator și independent pentru fiecare pereche de n 2 perechi posibile de vârfuri este o pseudopădure cu o probabilitate mare pentru o constantă c strict mai mică de unu. Acest fapt joacă un rol esențial în analiza hashing-ului cucului [31] , o structură de date pentru găsirea perechilor cheie-valoare analizând unul dintre cele două tabele hash în locația determinată de cheie - se poate forma un „graf împerecheat” ale căror vârfuri corespund poziției locației în tabelele hash, iar marginile leagă două locații unde poate fi găsită una dintre chei. Hashingul pe perechi găsește toate cheile dacă și numai dacă graficul asociat este o pseudopădure [32] .

Pseudopădurile joacă, de asemenea, un rol cheie în algoritmii de colorare a graficelor paralele și problemele conexe [33] [34] .

Note

  1. ↑ 1 2 Graficele nedirecționate considerate aici sunt multigrafe sau pseudografe, nu simple grafice .
  2. ↑ 1 2 3 4 Gabow, Tarjan, 1988 .
  3. ↑ 12 Dantzig , 1963 .
  4. ↑ Picard, Queyranne, 1982 .
  5. ↑ Această definiție, de exemplu, este folosită de Gabow și Westermann ( Gabow, Westermann (1992 )).
  6. ↑ Această definiție este folosită de Gabow și Tarjan ( Gabow, Tarjan (1988 )).
  7. ↑ Vezi, de exemplu, demonstrația Lemei 4 în Alvarez, Bles și Cern ( Àlvarez și colab. (2002 )).
  8. ↑ Krusk, Rudolf și Snir ( Kruskal și colab. (1990 )) folosesc în schimb definiția inversă, în care fiecare vârf are un grad de intrare de unu. Graficele rezultate, pe care le numesc un singur ciclu , sunt graficele transpuse ale graficelor considerate în această lucrare.
  9. ↑ Woodall, 1969 .
  10. ↑ Lovász et al, 1997 .
  11. ↑ 12 Streinu, Theran, 2009 .
  12. ↑ Whiteley, 1988 .
  13. ↑ Bolobash ( Bollobás (1985 )). A se vedea, în special, Corolarul 24, p. 120, pentru o limită a numărului de vârfuri aparținând componentelor cu un singur ciclu într-un grafic aleatoriu, și Corolarul 19, p. 113, pentru o limită a numărului de diferite etichete unu- grafice de ciclu.
  14. ↑ Riddell (1951 ); vezi A057500 în Encyclopedia of Integer Sequences .
  15. ↑ Puteți citi despre metoda demonstrației bijective în articolul lui Vershik ( Vershik (1986 ))
  16. ↑ Aigner, Ziegler, 1998 .
  17. ↑ Flajolet, Odlyzko, 1990 .
  18. ↑ Konyagin et al, 2016 .
  19. ↑ Martin, Odlyzko, Wolfram, 1984 .
  20. ↑ În versiunea în limba engleză - trenuri
  21. ↑ White, 1913 .
  22. ↑ Colbourn, Colbourn, Rosenbaum, 1982 .
  23. ↑ Stinson, 1983 .
  24. ↑ Simoes-Pereira, 1972 .
  25. ↑ Matthews, 1977 .
  26. ↑ Glosar de grafice semnate și câștig și zone aliate . Preluat la 23 octombrie 2016. Arhivat din original la 3 martie 2016.
  27. ↑ Pentru această terminologie, consultați lista de grafice mici Arhivată la 22 iulie 2012 la Wayback Machine din Information System on Graph Class Inclusions Arhivată la 5 februarie 2019 la Wayback Machine . Cu toate acestea, fluturele se poate referi la o familie diferită de grafice, legate de hipercuburi .
  28. ↑ El-Mallah, Colbourn, 1988 .
  29. ↑ 1 2 Ahuja, Magnanti, Orlin, 1993 .
  30. ↑ Gabow, Westermann (1992 ). Vezi și schemele de aproximare rapidă ale lui Kowalik ( Kowalik (2006 )).
  31. ↑ . În general, termenul nu are succes, dar și-a prins rădăcini în literatura de limbă rusă (ca traducere directă a cucului hashing ). Aparent, termenul a apărut din cauza împerecherii „cucului”. Metoda ar trebui să fie numită hashing pereche sau în două etape.
  32. ↑ Kutzelnigg, 2006 .
  33. ↑ Goldberg, Plotkin, Shannon, 1988 .
  34. ↑ Kruskal și colab., 1990 .

Literatură

Link -uri