Linjediagram

I grafteorin är linjegrafen L ( G ) för en oriktad graf G grafen L ( G ) som representerar grannskapet av kanterna på grafen G.

Konceptet med ett linjediagram för en given graf är så naturligt att det har introducerats oberoende av många författare. Naturligtvis gav var och en av dem sitt eget namn: Ore [1] kallade denna graf "adjacency graph" , Sabidussi [2] - "derivative graph" , Beinecke [3] - "derivative graph" , Sechu och Read [4] - "edge -vertex-dual" , Castelein [5] - "täckande graf" , Menon [6] - "adjoint" ("adjoint") [7] [8] [9] .

En av de tidigaste och viktigaste linjegrafsatserna beror på Whitney, som bevisade att, med ett undantag, är strukturen av en graf G helt definierad av en linjegraf. Med andra ord, med ett undantag, kan hela grafen rekonstrueras från linjediagrammet.

Formell definition

Låt en graf G ges , då är dess linjegraf L ( G ) en graf sådan att

Exempel

Konstruktionsexempel

Följande figur visar en graf (till vänster, med blå hörn) och dess linjediagram (till höger, med gröna hörn). Varje hörn av linjediagrammet är märkt med ett par av hörnnummer för motsvarande kant i den ursprungliga grafen. Till exempel motsvarar den gröna vertexen till höger märkt 1,3 kanten till vänster mellan de blå hörnen 1 och 3. Den gröna vertexen 1,3 ligger intill tre andra gröna hörn: 1,4, 1,2 ( motsvarande kanterna som delar vertex 1 i den blå grafen), och 4,3 (motsvarande kanter med en gemensam vertex 3 i den blå grafen).

Ackordsdiagram

Linjediagrammet för en komplett graf K n är känd som en kordalgraf (eller triangulerad graf ). En viktig sats om ackordsgrafer är satsen som säger att en ackordsgraf kännetecknas av ett spektrum , förutom n = 8 när det finns tre andra grafer med samma spektrum som L ( K 8 ). Undantag förklaras i Graph Switching .

Linjediagram av konvexa polyedrar

Källan till exempel på linjediagram kan hittas i geometri - för grafer av enkla polytoper . Om vi ​​bygger en linjegraf för en tetraedergraf får vi en oktaedergraf . Från grafen för kuben får vi grafen för kuboktaedern . Från grafen för dodekaedern får vi grafen för ikosidodekaedern osv. Geometriskt består operationen i att skära bort alla hörn på polyedern genom att ett plan skär alla kanter konjugerat till vertex i deras mitt.

Om polyedern inte är enkel (det vill säga den har fler än tre ytor per vertex), kommer linjegrafen inte att vara plan.

Mediangraf

En mediangraf är en variant av en linjegraf för en plan graf. I en mittengraf är två hörn intill om och endast om motsvarande kanter på den ursprungliga grafen är två på varandra följande kanter av något område av den plana grafen. För enkla polygoner är mediangrafen och linjegrafen desamma, men för komplexa polygoner förblir mediangrafen platt. Sålunda är de mellersta graferna för en kub och en oktaeder isomorfa med grafen för en kuboktaeder, och de mellersta graferna för en dodekaeder och en ikosaeder är isomorfa med grafen för en ikosidodekaeder.

Egenskaper

Egenskaper för grafen G som endast beror på närliggande kanter kan översättas till ekvivalenta egenskaper hos grafen L ( G ) som endast beror på närliggande hörn. Till exempel är en matchning i G  en uppsättning av bågar, varav ingen ligger intill den andra, och en motsvarande uppsättning av hörn i L ( G ), varav ingen ligger intill den andra, det vill säga en oberoende uppsättning av hörn .

Så,

Eftersom den maximala matchningen kan hittas i polynomtid, kan den maximala oberoende uppsättningen av en linjegraf också hittas i polynomtid, trots svårigheten att hitta en sådan uppsättning för mer allmänna graffamiljer.

Egenskaper och igenkänning

En graf G är en linjegraf av någon annan graf om och bara om det är möjligt att hitta en uppsättning klicker i G som delar G -bågarna på ett sådant sätt att varje vertex i G tillhör exakt två klick. Det kan hända att för att uppnå detta är det nödvändigt att välja enskilda hörn i klick. Enligt Whitneys sats  [10] [11] , om G inte är en triangel, kan det bara finnas en partition av detta slag. Om det finns en partition kan vi konstruera en graf där G är en linjegraf genom att skapa en vertex för varje klick och koppla samman de resulterande hörnen med en kant om vertexen tillhör båda klickarna. Sålunda, med undantag för och , om två linjediagram av sammankopplade grafer är isomorfa till , då är graferna också isomorfa. Roussopoulos [12] använde denna observation som grund för en tidslinjär algoritm för att känna igen linjegrafer och rekonstruera deras ursprungliga grafer.

Till exempel kan en sådan egenskap användas för att visa att följande graf inte är ett linjediagram:

I det här exemplet innehåller kanterna som går från den centrala spetsen av 4:e graden upp, till vänster och till höger inga vanliga klickar. Så varje uppdelning av grafens kanter i klicker måste innehålla minst en klick för var och en av dessa tre kanter, och alla tre klicken skär varandra vid den centrala vertexen, vilket bryter mot villkoret att varje vertex tillhör exakt två klicker. Den visade grafen kan alltså inte vara en linjegraf.

En annan egenskap hos en graf bevisades av Beinecke [13] (och nämndes utan bevis tidigare av honom [3] ). Han visade att det finns nio minimala icke-linjediagram så att alla icke-linjediagram innehåller en av dessa nio grafer som en genererad subgraf . Således är en graf ett linjediagram om och endast om ingen delmängd av hörn genererar en av dessa nio. I exemplet ovan genererar de fyra översta hörnen en klo (det vill säga en komplett tvådelad graf K 1,3 ), som visas längst upp till vänster på den förbjudna subgrafillustrationen. Således, enligt Beinecke-karaktäristiken, kan denna graf inte vara en linjegraf. För grafer med vertexgrad på minst 5 kan endast sex subgrafer i figurens vänstra och högra kolumner genereras av grafen [14] . Detta resultat liknar resultatet för hypergraflinjediagram [15] .

Upprepning av operationen att konstruera ett linjediagram

Ruij och Wilf [16] övervägde sekvensen av grafer

De visade att för en ändlig graf av en sammankopplad graf G är endast fyra beteenden i denna sekvens möjliga:

Om G är frånkopplad, gäller denna klassificering för varje enskild ansluten komponent i G .

Släktskap med andra graffamiljer

Varje linjediagram innehåller inte klor .

Linjediagrammet för en tvådelad graf är perfekt (se Königs sats ). Linjediagrammen för tvådelade grafer utgör en av de viktigaste byggstenarna som används för att bevisa den perfekta grafsatsen. Ett specialfall är torngrafer , linjediagram av kompletta tvådelade grafer .

Generaliseringar

Multigrafer

Konceptet med en linjegraf för en graf G kan naturligtvis utvidgas till fallet när G är en multigraf, även om i detta fall Whitneys unikhetsteorem blir ogiltigt. Till exempel har den kompletta tvådelade grafen K 1, n samma linjegraf som dipolgrafen och Shannon-multigrafen med samma antal kanter.

Kantdigrafer

Man kan också generalisera linjediagram till riktade grafer [17] . Om G  är en riktad graf, har dess riktade linjegraf eller linjedigraf en vertex för varje båge i G . Två hörn som motsvarar bågar från u till v och från w till x från grafen G är förbundna med en båge från uv till wx i en linjedigraf när v = w . Således motsvarar varje båge i linjedigrafen en väg med längden 2 i den ursprungliga grafen. De Bruijn-grafer kan erhållas genom att upprepade gånger konstruera riktade linjediagram, som börjar med en komplett digraf [18] .

Viktade linjediagram

Varje vertex av grad k i den ursprungliga grafen G skapar k(k-1)/2 kanter i linjegrafen L ( G ). För många typer av analyser innebär detta att höggradiga hörn i G är starkare representerade i linjediagrammet L ( G ). Föreställ dig till exempel en slumpmässig vandring över hörnen på den ursprungliga grafen G . Vi kommer att passera längs kanten e med viss sannolikhet f . Å andra sidan motsvarar kanten e en enda vertex, säg v , i linjediagrammet L ( G ). Om vi ​​nu utför samma typ av slumpmässig vandring över hörnen på en linjegraf, kan besöksfrekvensen v visa sig vara ganska annorlunda än f . Om vår kant e i G var kopplad till hörn av grad O(k) skulle den korsas O(k 2 ) oftare i linjediagrammet L ( G ). Således, medan Whitneys sats [10] garanterar att en linjegraf nästan alltid innehåller den kodade topologin för G , garanterar den inte att de två graferna har enkla dynamiska kopplingar. En lösning på detta problem är att skapa en viktad linjegraf, det vill säga en linjegraf vars kanter är viktade. Det finns flera naturliga sätt att göra detta [19] . Till exempel, om kanterna d och e i en graf G är konjugerade vid en vertex v av graden k , då i en linjegraf L ( G ) kan kanten som förbinder två hörn d och e tilldelas vikten 1/(k- 1) . På samma sätt kommer vilken kant som helst i G (såvida den inte är ansluten till en vertex av grad 1 ) att ha vikt 2 i linjediagrammet L ( G ), motsvarande två ändar av kanten i G .

Linjediagram av hypergrafer

Kanterna på en hypergraf kan bilda vilken familj av uppsättningar som helst, så linjediagrammet för en hypergraf  är detsamma som skärningsdiagrammet för uppsättningarna i en familj.

Anteckningar

  1. ↑ O. Ore. Hamilton kopplade grafer // J. Math. Pures Appl. - 1963. - T. 42 . - S. 21-27 .
  2. ↑ G. Sabidussi. Grafer med given grupp och givna prafteoretiska egenskaper  // 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. Linjära grafer och elektriska kretsar. - M . : Högre skola, 1971. - T. 42. - S. 21-27.
  5. ↑ Kasteleyn P. W. Ett lösligt självundvikande promenadproblem // Physica. - 1968. - T. 23 . - S. 85-89 .
  6. ↑ Menon V. På upprepade utbytesgrafer // Amer Math Monthly. - 1966. - T. 13 . - S. 986-989 .
  7. ↑ F. Harari . Graph Theory = Graph Theory / Översättning från engelska och förord ​​av V.P. Kozyrev. - 2. - M. : Redaktionell URSS, 2003. - 296 sid.
  8. ↑ Balakrishnan VK Schaums översikt över grafteorin. — 1:a. - McGraw-Hill, 1997. - ISBN 0-07-005489-4 .
  9. ↑ R.L. Hemminger, L.W. Beineke. Valda ämnen i grafteori. - Academic Press Inc., 1978. - S. 271-305 .
  10. ↑ 1 2 H. Whitney. Kongruenta grafer och grafernas anslutningsmöjligheter  // American Journal of Mathematics. - 1932. - T. 54 , nr. 1 . - S. 150-168 . - doi : 10.2307/2371086 . — .
  11. ↑ J. Krausz. Demonstration nouvelle d'un théorème de Whitney sur les réseaux // Mat. Fiz. Lapok. - 1943. - T. 50 . - S. 75-85 .
  12. ↑ N.D. Roussopoulos. En max { m , n } algoritm för att bestämma grafen H från dess linjediagram G  // Information Processing Letters. - 1973. - Vol. 2 , nummer. 4 . - S. 108-112 . - doi : 10.1016/0020-0190(73)90029-X .
  13. ↑ LW Beineke. Karakteriseringar av härledda grafer // Journal of Combinatorial Theory. - 1970. - Vol. 9. - S. 129-135 . - doi : 10.1016/S0021-9800(70)80019-9 .
  14. ↑ Yury Metelsky, Regina Tyshkevich. On line grafer av linjära 3-uniforma hypergrafer // 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  på Wolfram MathWorld- webbplatsen .
  16. ↑ ACM van Rooij, H. S. Wilf. Utbytesgrafen för en finit graf // Acta Mathematica Hungarica. - 1965. - T. 16 , nr. 3-4 . - S. 263-269 . - doi : 10.1007/BF01904834 .
  17. ↑ Frank Harary, RZ Norman. Några egenskaper hos linjedigrafer // 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. På de Bruijn–Bra grafer // Acta Math. Sinica. - 1987. - T. 30 , nr. 2 . - S. 195-205 .
  19. ↑ T. S. Evans, R. Lambiotte. Linjediagram, länkpartitioner och överlappande gemenskaper // Phys.Rev.E. - 2009. - T. 80 . - doi : 10.1103/PhysRevE.80.016105 .

Länkar