Grafic liniare

În teoria grafurilor, graficul de linii L ( G ) al unui graf nedirecționat G este graficul L ( G ) care reprezintă vecinătatea muchiilor graficului G .

Conceptul de grafic linie pentru un grafic dat este atât de natural încât a fost introdus independent de mulți autori. Desigur, fiecare dintre ei și-a dat propriul nume: Ore [1] a numit acest grafic „graf de adiacență” , Sabidussi [2] - „graf derivat” , Beinecke [3] - „graf derivat” , Sechu și Read [4] - „muchie -vertix-dual” , Castelein [5] - „graf de acoperire” , Menon [6] - „adjunct” („adjunct”) [7] [8] [9] .

Una dintre cele mai vechi și mai importante teoreme de graf liniare se datorează lui Whitney, care a demonstrat că, cu o singură excepție, structura unui graf G este complet definită de un graf cu linii. Cu alte cuvinte, cu o singură excepție, întregul grafic poate fi reconstruit din graficul cu linii.

Definiție formală

Fie dat un grafic G , atunci graficul său cu linii L ( G ) este un grafic astfel încât

Exemple

Exemplu de construcție

Figura următoare prezintă un grafic (în stânga, cu vârfuri albastre) și graficul său cu linii (în dreapta, cu vârfuri verzi). Fiecare vârf al graficului cu linii este etichetat cu o pereche de numere de vârf ale muchiei corespunzătoare din graficul original. De exemplu, vârful verde din dreapta etichetat 1,3 corespunde muchiei din stânga dintre vârfurile albastre 1 și 3. Vârful verde 1,3 este adiacent altor trei vârfuri verzi: 1,4, 1,2 ( corespunzând muchiilor care împart vârful 1 în graficul albastru) și 4,3 (corespunzând muchiilor cu un vârf comun 3 în graficul albastru).

Grafice de acorduri

Graficul liniare al unui grafic complet K n este cunoscut sub denumirea de grafic cordal (sau grafic triangulat ). O teoremă importantă despre grafurile cordale este teorema care afirmă că un graf cordal este caracterizat de un spectru , cu excepția n = 8 când există alte trei grafice cu același spectru ca L ( K 8 ). Excepțiile sunt explicate în Comutarea graficului .

Grafice liniare ale poliedrelor convexe

Sursa de exemple de grafice liniare poate fi găsită în geometrie - pentru graficele politopilor simple . Dacă construim un grafic de linii pentru un grafic tetraedric , obținem un grafic octaedru . Din graficul cubului obținem graficul cuboctaedrului . Din graficul dodecaedrului obținem graficul icosidodecaedrului și așa mai departe.Geometric, operația constă în tăierea tuturor vârfurilor poliedrului printr-un plan care intersectează toate muchiile conjugate cu vârful din mijlocul lor.

Dacă poliedrul nu este simplu (adică are mai mult de trei fețe pe vârf), graficul de linii nu va fi plan.

Graficul median

Un grafic median este o variantă a unui grafic de linii pentru un grafic plan. Într-un grafic din mijloc, două vârfuri sunt adiacente dacă și numai dacă muchiile corespunzătoare ale graficului original sunt două muchii consecutive ale unei zone a graficului plan. Pentru poligoane simple, graficul median și graficul cu linii sunt aceleași, dar pentru poligoane complexe, graficul median rămâne plat. Astfel, graficele din mijloc ale unui cub și ale unui octaedru sunt izomorfe cu graficul unui cuboctaedru, iar graficele din mijloc ale unui dodecaedru și ale unui icosaedru sunt izomorfe cu graficul unui icosidodecaedru.

Proprietăți

Proprietățile graficului G care depind doar de adiacența muchiilor pot fi translate în proprietăți echivalente ale graficului L ( G ) care depind doar de adiacența vârfurilor. De exemplu, o potrivire în G  este un set de arce, dintre care niciunul nu este adiacent celuilalt, și un set corespunzător de vârfuri în L ( G ), niciunul dintre care nu este adiacent celuilalt, adică un set independent de vârfuri .

Asa de,

Deoarece potrivirea maximă poate fi găsită în timp polinomial, mulțimea independentă maximă a unui grafic cu linii poate fi găsită și în timp polinomial, în ciuda dificultății de a găsi o astfel de mulțime pentru familii mai generale de grafice.

Caracteristici și recunoaștere

Un grafic G este un grafic liniare al unui alt grafic dacă și numai dacă este posibil să se găsească o mulțime de clicuri în G care împart arcele lui G în așa fel încât fiecare vârf al lui G să aparțină exact la două clicuri. Se poate întâmpla ca, pentru a realiza acest lucru, să fie necesar să selectați vârfuri individuale în clicuri. După teorema lui Whitney  [10] [11] , dacă G nu este un triunghi, poate exista o singură partiție de acest fel. Dacă există o partiție, putem construi un grafic pentru care G este un grafic cu linii, creând un vârf pentru fiecare clică și conectând vârfurile rezultate cu o muchie dacă vârful aparține ambelor clicuri. Astfel, cu excepția și , dacă două grafice liniare ale grafurilor conectate sunt izomorfe cu , atunci graficele sunt și izomorfe. Roussopoulos [12] a folosit această observație ca bază pentru un algoritm liniar în timp pentru recunoașterea graficelor de linii și reconstruirea graficelor lor originale.

De exemplu, o astfel de caracteristică poate fi utilizată pentru a arăta că următorul grafic nu este un grafic cu linii:

În acest exemplu, muchiile care merg de la vârful central al gradului 4 în sus, la stânga și la dreapta nu conțin clicuri comune. Deci, orice partiție a muchiilor graficului în clicuri trebuie să conțină cel puțin o clică pentru fiecare dintre aceste trei margini și toate cele trei clicuri se intersectează la vârful central, ceea ce încalcă condiția ca fiecare vârf să aparțină exact la două clicuri. Astfel, graficul prezentat nu poate fi un grafic cu linii.

O altă caracteristică a unui graf a fost demonstrată de Beinecke [13] (și menționată fără dovezi mai devreme de către el [3] ). El a arătat că există nouă grafice minime neliniare, astfel încât orice grafic neliniar conține unul dintre aceste nouă grafice ca subgraf generat . Astfel, un grafic este un grafic de linii dacă și numai dacă niciun subset de vârfuri nu generează unul dintre aceste nouă. În exemplul de mai sus, primele patru vârfuri generează o gheară (adică un grafic bipartit complet K 1,3 ), afișat în partea stângă sus a ilustrației subgrafului interzis. Astfel, conform caracteristicii Beinecke, acest grafic nu poate fi un grafic de linii. Pentru graficele cu gradul de vârf de cel puțin 5, numai șase subgrafe din coloanele din stânga și din dreapta figurii pot fi generate de graficul [14] . Acest rezultat este similar cu rezultatul pentru graficele cu linii hipergraf [15] .

Repetarea operației de construire a unui grafic linear

Ruij și Wilf [16] au considerat succesiunea graficelor

Ei au arătat că pentru un graf finit al unui graf conex G , sunt posibile doar patru comportamente ale acestei secvențe:

Dacă G este deconectat, atunci această clasificare se aplică fiecărei componente conectate a lui G.

Relația cu alte familii de grafice

Orice grafic de linii nu conține gheare .

Graficul liniare al unui grafic bipartit este perfect (vezi teorema lui König ). Graficele liniare ale graficelor bipartite formează unul dintre elementele de bază cheie care este folosită pentru a demonstra teorema grafului perfect. Un caz special sunt graficele turn , graficele liniare ale graficelor bipartite complete .

Generalizări

Multigrafe

Conceptul de graf cu linii pentru un graf G poate fi extins în mod natural la cazul în care G este un multigraf, deși în acest caz teorema de unicitate a lui Whitney devine invalidă. De exemplu, graficul bipartit complet K 1, n are același grafic cu linii ca și graficul dipol și multigraful Shannon cu același număr de muchii.

Digrafele marginilor

De asemenea, se pot generaliza graficele liniare la grafice direcționate [17] . Dacă G  este un graf direcționat, atunci graficul său cu linie direcționată sau digraful cu linie are un vârf pentru fiecare arc din G . Două vârfuri corespunzătoare arcelor de la u la v și de la w la x din graficul G sunt conectate printr-un arc de la uv la wx într-un digraf de linii atunci când v = w . Astfel, fiecare arc din digraful liniei corespunde unui drum de lungime 2 din graficul original. Graficele De Bruijn pot fi obținute prin construirea repetată a graficelor cu linii direcționate, începând cu un digraf complet [18] .

Grafice cu linii ponderate

Fiecare vârf de grad k din graficul original G creează k(k-1)/2 muchii în graficul de linii L ( G ). Pentru multe tipuri de analiză, aceasta înseamnă că vârfurile de grad înalt din G sunt reprezentate mai puternic în graficul de linii L ( G ). Imaginați-vă, de exemplu, o mers aleatorie peste vârfurile graficului original G . Vom trece de-a lungul muchiei e cu o oarecare probabilitate f . Pe de altă parte, muchia e corespunde unui singur vârf, să spunem v , în graficul de linii L ( G ). Dacă acum efectuăm același tip de mers aleatoriu peste vârfurile unui grafic cu linii, frecvența de vizită v se poate dovedi a fi destul de diferită de f . Dacă muchia noastră e din G ar fi conectată la vârfuri de gradul O(k) , aceasta ar fi parcursă O(k 2 ) mai des în graficul de linii L ( G ). Astfel, în timp ce teorema lui Whitney [10] garantează că un grafic cu linii aproape întotdeauna conține topologia codificată a lui G , nu garantează că cele două grafice au conexiuni dinamice simple. O soluție la această problemă este crearea unui grafic cu linii ponderate, adică un grafic cu linii ale căror margini sunt ponderate. Există mai multe moduri naturale de a face acest lucru [19] . De exemplu, dacă muchiile d și e dintr-un grafic G sunt conjugate la un vârf v de gradul k , atunci într-un grafic cu linii L ( G ) muchiei care leagă două vârfuri d și e i se poate atribui o pondere de 1/(k- 1) . În același mod, orice muchie din G (cu excepția cazului în care este conectată la un vârf de gradul 1 ) va avea ponderea 2 în graficul de linii L ( G ), corespunzătoare la două capete ale muchiei din G .

Grafice liniare ale hipergrafelor

Marginile unui hipergraf pot forma orice familie de mulțimi, astfel încât graficul cu linii ale unui hipergraf  este același cu graficul de intersecție al mulțimilor unei familii.

Note

  1. ↑ O. Ore. Grafice conectate Hamilton // J. Math. Pure Appl. - 1963. - T. 42 . - S. 21-27 .
  2. ↑ G. Sabidussi. Grafice cu grup dat și proprietăți praf-teoretice date  // Canad. J Math. - 1957. - T. 9 . - S. 515-525 .
  3. ↑ 1 2 L. W. Beineke. Beitrage zur Graphentheorie. — Leipzig: Teubner, 1968.
  4. ↑ Seshu S., Reed M. Grafice liniare și circuite electrice. - M . : Liceu, 1971. - T. 42. - S. 21-27.
  5. ↑ Kasteleyn P. W. A soluble self-avoiding walk problem // Physica. - 1968. - T. 23 . - S. 85-89 .
  6. ↑ Menon V. Pe graficele de schimb repetate // Amer Math Monthly. - 1966. - T. 13 . - S. 986-989 .
  7. ↑ F. Harari . Teoria graficelor = Teoria graficelor / Traducere din engleză și prefață de V.P. Kozyrev. - 2. - M. : Editorial URSS, 2003. - 296 p.
  8. ↑ Balakrishnan VK Schaum's Outline of Graph Theory. — 1-a. - McGraw-Hill, 1997. - ISBN 0-07-005489-4 .
  9. ↑ R.L. Hemminger, L.W. Beineke. Subiecte selectate în teoria grafurilor. - Academic Press Inc., 1978. - S. 271-305 .
  10. ↑ 1 2 H. Whitney. Grafice congruente și conectivitatea graficelor  // American Journal of Mathematics. - 1932. - T. 54 , nr. 1 . - S. 150-168 . - doi : 10.2307/2371086 . — .
  11. ↑ J. Krausz. Demonstration new d'un theorème de Whitney sur les réseaux // Mat. Fiz. Lapok. - 1943. - T. 50 . - S. 75-85 .
  12. ↑ N.D. Roussopoulos. Un algoritm de max { m , n } pentru determinarea graficului H din graficul său linii G  // Litere de procesare a informațiilor. - 1973. - Vol. 2 , numărul. 4 . - S. 108-112 . - doi : 10.1016/0020-0190(73)90029-X .
  13. ↑ LW Beineke. Caracterizări ale graficelor derivate // Journal of Combinatorial Theory. - 1970. - Vol. 9. - S. 129-135 . - doi : 10.1016/S0021-9800(70)80019-9 .
  14. ↑ Iuri Metelsky, Regina Tyshkevich. On line graphs of linear 3-uniform hypergraphs // Journal of Graph Theory. - 1997. - T. 25 , nr. 4 . - S. 243-251 . - doi : 10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K .
  15. ↑ Weisstein, Eric W. Line Graph  pe site- ul Wolfram MathWorld .
  16. ↑ ACM van Rooij, H. S. Wilf. Graficul de schimb al unui grafic finit // Acta Mathematica Hungarica. - 1965. - T. 16 , nr. 3-4 . - S. 263-269 . - doi : 10.1007/BF01904834 .
  17. ↑ Frank Harary, RZ Norman. Unele proprietăți ale digrafelor de linii // Rendiconti del Circolo Matematico di Palermo . - 1960. - T. 9 , nr. 2 . - S. 161-169 . - doi : 10.1007/BF02854581 .
  18. ↑ Fu Ji Zhang, Guo Ning Lin. Despre graficele de Bruijn–Good // Acta Math. Sinica. - 1987. - T. 30 , nr. 2 . - S. 195-205 .
  19. ↑ T. S. Evans, R. Lambiotte. Grafice cu linii, partiții de legături și comunități suprapuse // Phys.Rev.E. - 2009. - T. 80 . - doi : 10.1103/PhysRevE.80.016105 .

Link -uri