Linje graf

I grafteori er linjegrafen L ( G ) af en urettet graf G grafen L ( G ) , der repræsenterer naboskabet af kanter af grafen G.

Konceptet med en linjegraf for en given graf er så naturligt, at det er blevet uafhængigt introduceret af mange forfattere. Selvfølgelig gav hver af dem sit eget navn: Ore [1] kaldte denne graf "adjacency graph" , Sabidussi [2] - "derivative graph" , Beinecke [3] - "derivative graph" , Sechu og Read [4] - "kant -vertex-dual" , Castelein [5] - "dækkende graf" , Menon [6] - "adjoint" ("adjoint") [7] [8] [9] .

En af de tidligste og vigtigste linjegrafsætninger skyldes Whitney, som beviste, at strukturen af ​​en graf G med en enkelt undtagelse er fuldstændig defineret af en linjegraf. Med andre ord, med én undtagelse, kan hele grafen rekonstrueres fra linjegrafen.

Formel definition

Lad en graf G være givet , så er dens linjegraf L ( G ) en graf sådan, at

Eksempler

Konstruktionseksempel

Den følgende figur viser en graf (til venstre med blå hjørner) og dens linjegraf (til højre med grønne spidser). Hvert toppunkt på linjegrafen er mærket med et par toppunktnumre på den tilsvarende kant i den originale graf. For eksempel svarer det grønne toppunkt til højre mærket 1,3 til kanten til venstre mellem de blå toppunkter 1 og 3. Det grønne toppunkt 1,3 støder op til tre andre grønne toppunkter: 1,4, 1,2 ( svarende til de kanter, der deler toppunkt 1 i den blå graf), og 4,3 (svarende til kanter med fælles toppunkt 3 i den blå graf).

Chordal grafer

Linjegrafen for en komplet graf K n er kendt som en akkordgraf (eller trianguleret graf ). En vigtig sætning om akkordgrafer er sætningen om, at en akkordgraf er karakteriseret ved et spektrum , bortset fra n = 8, når der er tre andre grafer med samme spektrum som L ( K 8 ). Undtagelser er forklaret i Graph Switching .

Linjegrafer af konvekse polyedre

Kilden til eksempler på linjegrafer kan findes i geometri - for grafer af simple polytoper . Hvis vi bygger en linjegraf for en tetraedergraf , får vi en oktaedergraf . Fra grafen for kuben får vi grafen for cuboctahedron . Fra grafen for dodekaederet får vi grafen for icosidodecahedronen osv. Geometrisk består operationen i at afskære alle polyederens hjørner af et plan, der skærer alle kanterne konjugeret til toppunktet i deres midte.

Hvis polyederet ikke er simpelt (det vil sige, det har mere end tre flader pr. vertex), vil linjegrafen ikke være plan.

Mediangraf

En mediangraf er en variant af en linjegraf for en plan graf. I en midtergraf er to hjørner tilstødende, hvis og kun hvis de tilsvarende kanter på den originale graf er to på hinanden følgende kanter af et område af den plane graf. For simple polygoner er mediangrafen og linjegrafen de samme, men for komplekse polygoner forbliver mediangrafen flad. Således er de midterste grafer af en terning og et oktaeder isomorfe med grafen for et cuboctahedron, og de midterste grafer af et dodecahedron og et icosahedron er isomorfe med grafen for et icosidodecahedron.

Egenskaber

Egenskaber for grafen G , der kun afhænger af tilgrænsende kanter, kan oversættes til ækvivalente egenskaber for grafen L ( G ), der kun afhænger af tilgrænsende hjørner. For eksempel er en matchning i G  et sæt buer, hvoraf ingen støder op til den anden, og et tilsvarende sæt af hjørner i L ( G ), hvoraf ingen støder op til den anden, det vil sige et uafhængigt sæt af hjørner .

Så,

Da den maksimale matchning kan findes i polynomiel tid, kan det maksimale uafhængige sæt af en linjegraf også findes i polynomiel tid, på trods af vanskeligheden ved at finde et sådant sæt for mere generelle graffamilier.

Karakteristika og genkendelse

En graf G er en linjegraf af en anden graf, hvis og kun hvis det er muligt at finde et sæt kliker i G , der deler buerne af G på en sådan måde, at hvert hjørne af G hører til præcis to kliker. Det kan ske, at det for at opnå dette er nødvendigt at vælge individuelle hjørner i kliker. Ved Whitneys sætning  [10] [11] kan der kun være én partition af denne art , hvis G ikke er en trekant. Hvis der findes en partition, kan vi konstruere en graf, for hvilken G er en linjegraf, ved at skabe et toppunkt for hver klike og forbinde de resulterende toppunkter med en kant, hvis toppunktet tilhører begge kliker. Således, med undtagelse af og , hvis to linjegrafer af forbundne grafer er isomorfe til , så er graferne også isomorfe. Roussopoulos [12] brugte denne observation som grundlag for en tids-lineær algoritme til at genkende linjegrafer og rekonstruere deres oprindelige grafer.

For eksempel kan en sådan karakteristik bruges til at vise, at følgende graf ikke er en linjegraf:

I dette eksempel indeholder kanterne, der går fra det centrale toppunkt af 4. grad op, til venstre og til højre, ikke almindelige kliker. Så enhver opdeling af grafens kanter i kliker skal indeholde mindst én klik for hver af disse tre kanter, og alle tre kliker skærer hinanden ved det centrale vertex, hvilket overtræder betingelsen om, at hvert vertex tilhører præcis to kliker. Den viste graf kan således ikke være en linjegraf.

En anden karakteristik af en graf blev bevist af Beinecke [13] (og nævnt uden bevis tidligere af ham [3] ). Han viste, at der er ni minimale ikke-linjegrafer, således at enhver ikke-linjegraf indeholder en af ​​disse ni grafer som en genereret undergraf . En graf er således en linjegraf, hvis og kun hvis ingen delmængde af toppunkter genererer en af ​​disse ni. I eksemplet ovenfor genererer de øverste fire hjørner en klo (det vil sige en komplet todelt graf K 1,3 ), vist øverst til venstre i den forbudte undergrafillustration. Ifølge Beinecke-karakteristikken kan denne graf således ikke være en linjegraf. For grafer med toppunktsgrad på mindst 5 kan kun seks undergrafer i venstre og højre kolonne i figuren genereres af grafen [14] . Dette resultat svarer til resultatet for hypergraflinjegrafer [15] .

Gentagelse af operationen med at konstruere en linjegraf

Ruij og Wilf [16] overvejede sekvensen af ​​grafer

De viste, at for en endelig graf af en forbundet graf G , er kun fire adfærd af denne sekvens mulige:

Hvis G er afbrudt, gælder denne klassifikation for hver enkelt tilsluttet komponent af G .

Forholdet til andre familier af grafer

Enhver linjegraf indeholder ikke kløer .

Linjegrafen for en todelt graf er perfekt (se Königs sætning ). Linjegraferne i todelte grafer udgør en af ​​de vigtigste byggesten, der bruges til at bevise den perfekte grafsætning. Et særligt tilfælde er tårngrafer , linjegrafer af komplette todelte grafer .

Generaliseringer

Multigrafer

Konceptet med en linjegraf for en graf G kan naturligt udvides til det tilfælde, hvor G er en multigraf, selvom Whitneys unikkesætning i dette tilfælde bliver ugyldig. For eksempel har den komplette todelte graf K 1, n den samme linjegraf som dipolgrafen og Shannon multigrafen med det samme antal kanter.

Kant-digrafer

Man kan også generalisere linjegrafer til rettede grafer [17] . Hvis G  er en rettet graf, så har dens rettet linjegraf eller linjedigraf et toppunkt for hver bue i G . To hjørner svarende til buer fra u til v og fra w til x fra grafen G er forbundet med en bue fra uv til wx i en linjedigraf, når v = w . Således svarer hver bue i linjedigrafen til en sti med længde 2 i den originale graf. De Bruijn-grafer kan opnås ved gentagne gange at konstruere rettede linjegrafer, startende med en komplet digraf [18] .

Vægtede linjegrafer

Hvert hjørne af grad k i den originale graf G skaber k(k-1)/2 kanter i linjegrafen L ( G ). For mange slags analyser betyder det, at højgraders toppunkter i G er stærkere repræsenteret i linjegrafen L ( G ). Forestil dig for eksempel en tilfældig gåtur over hjørnerne af den originale graf G . Vi vil passere langs kanten e med en vis sandsynlighed f . På den anden side svarer kanten e til et enkelt toppunkt, f.eks. v , i linjegrafen L ( G ). Hvis vi nu udfører den samme type tilfældig vandring over hjørnerne af en linjegraf, kan besøgsfrekvensen v vise sig at være ret forskellig fra f . Hvis vores kant e i G var forbundet med toppunkter i grad O(k) , ville den blive krydset O(k 2 ) oftere i linjegrafen L ( G ). Selvom Whitneys sætning [10] garanterer, at en linjegraf næsten altid indeholder den kodede topologi af G , garanterer den ikke, at de to grafer har simple dynamiske forbindelser. En løsning på dette problem er at lave en vægtet linjegraf, det vil sige en linjegraf, hvis kanter er vægtet. Der er flere naturlige måder at gøre dette på [19] . Hvis f.eks. kanter d og e i en graf G er konjugerede ved et toppunkt v af grad k , så kan i en linjegraf L ( G ) kanten, der forbinder to hjørner d og e , tildeles en vægt på 1/(k- 1) . På samme måde vil enhver kant i G (medmindre den er forbundet med et toppunkt på grad 1 ) have vægt 2 i linjegrafen L ( G ), svarende til to ender af kanten i G .

Linjegrafer af hypergrafer

Kanterne på en hypergraf kan danne en hvilken som helst familie af sæt, så linjegrafen for en hypergraf  er den samme som skæringsgrafen for sætene i en familie.

Noter

  1. ↑ O. Ore. Hamilton forbundne grafer // J. Math. Pures Appl. - 1963. - T. 42 . - S. 21-27 .
  2. ↑ G. Sabidussi. Grafer med given gruppe og givne praksisteoretiske egenskaber  // 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. Lineære grafer og elektriske kredsløb. - M . : Højere Skole, 1971. - T. 42. - S. 21-27.
  5. ↑ Kasteleyn P. W. Et opløseligt selvundgående gåproblem // Physica. - 1968. - T. 23 . - S. 85-89 .
  6. ↑ Menon V. På gentagne udvekslingsgrafer // Amer Math Monthly. - 1966. - T. 13 . - S. 986-989 .
  7. ↑ F. Harari . Graph Theory = Graph Theory / Oversættelse fra engelsk og forord af V.P. Kozyrev. - 2. - M. : Redaktionel URSS, 2003. - 296 s.
  8. ↑ Balakrishnan VK Schaums disposition af grafteori. — 1. - McGraw-Hill, 1997. - ISBN 0-07-005489-4 .
  9. ↑ R.L. Hemminger, L.W. Beineke. Udvalgte emner i grafteori. - Academic Press Inc., 1978. - S. 271-305 .
  10. ↑ 1 2 H. Whitney. Kongruente grafer og grafers forbindelse  // 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 } algoritme til at bestemme grafen H ud fra dens linjegraf G  // Information Processing Letters. - 1973. - Bind 2 , udgave. 4 . - S. 108-112 . - doi : 10.1016/0020-0190(73)90029-X .
  13. ↑ LW Beineke. Karakteriseringer af afledte grafer // Journal of Combinatorial Theory. - 1970. - Bd. 9. - S. 129-135 . - doi : 10.1016/S0021-9800(70)80019-9 .
  14. ↑ Yury Metelsky, Regina Tyshkevich. On line grafer af lineære 3-uniforme hypergrafer // Journal of Graph Theory. - 1997. - T. 25 , no. 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- webstedet .
  16. ↑ ACM van Rooij, H. S. Wilf. Udvekslingsgrafen for en endelig graf // Acta Mathematica Hungarica. - 1965. - T. 16 , no. 3-4 . - S. 263-269 . - doi : 10.1007/BF01904834 .
  17. ↑ Frank Harary, RZ Norman. Nogle egenskaber ved linjedigrafer // Rendiconti del Circolo Matematico di Palermo . - 1960. - T. 9 , no. 2 . - S. 161-169 . - doi : 10.1007/BF02854581 .
  18. ↑ Fu Ji Zhang, Guo Ning Lin. På de Bruijn-Gode grafer // Acta Math. Sinica. - 1987. - T. 30 , no. 2 . - S. 195-205 .
  19. ↑ T. S. Evans, R. Lambiotte. Linjegrafer, linkpartitioner og overlappende fællesskaber // Phys.Rev.E. - 2009. - T. 80 . - doi : 10.1103/PhysRevE.80.016105 .

Links