Linje graf

I grafteori , den linjegrafen L ( G ) af en ikke-orienteret graf G , er en graf, der repræsenterer adjacency forhold mellem kanterne af G . Navnet linje graf stammer fra en artikel af Harary og Norman offentliggjort i 1960. Den samme konstruktion havde dog allerede blevet brugt af Whitney i 1932 og Krausz i 1943. Det kaldes også en adjungeret graf .

En af de første og vigtigste linjediagram teoremer er anført af Hassler Whitney i 1932, der godtgør, at bortset fra en enkelt undtagelsestilfælde, strukturen af G kan helt fundet fra L ( G ) i tilfælde af relaterede grafer .

Formel definition

Ved en graf G er dens linjegraf L ( G ) grafen defineret som følger:

Hvert toppunkt af L ( G ) repræsenterer en kant af G ;
To hjørner af L ( G ) er tilstødende, hvis og kun hvis de tilsvarende kanter deler et fælles slutpunkt i G (vi siger, at de er tilstødende).

Eksempler

Eksempel på konstruktion

Den følgende figur illustrerer en graf (til venstre med blå hjørner) og dens linjediagram (til højre med grønne hjørner). Hvert toppunkt i linjegrafen er mærket med slutpunkterne for den tilsvarende kant i den originale graf.

Graf G
Hjørner af L ( G ) konstrueret fra kanter af G
Tilføjelse af kanter på L ( G )
Den linjegraf L ( G )

Nogle linjegrafer

Den Petersen graf er den komplementær graf af linjediagrammet af den komplet graf . $K_5$
Den linjediagram af det tetraedriske graf er den oktaedriske graf .
Den linjediagram af den seksfladede graf er den cuboctahedral graf .
Den linjediagram af den dodecahedral graf er den tyvefladet graf .

Ejendomme

Elementære egenskaber

Egenskaberne for en graf G, der kun afhænger af tilgrænsningen mellem kanter, kan oversættes på L ( G ) til ækvivalente egenskaber afhængigt af tilgrænsningen mellem hjørner. For eksempel svarer en kobling i G , det vil sige et sæt kanter, der ikke har noget toppunkt til fælles, et sæt ikke-tilstødende to-to-to hjørner i L ( G ), derfor til en stald på L ( G ).

Derfor har vi følgende egenskaber:

Den linjegraf af en tilsluttet graf er tilsluttet. Det omvendte er dog ikke sandt. En graf G med isolerede hjørner kan have en tilsluttet linjegraf .
En stabil sæt maksimale vægt i en linjegraf L ( G ) svarer til en maksimal matching i G . Da en maksimal kobling kan findes i polynomisk tid, udføres søgningen efter et stabilt sæt med maksimal vægt også i polynomial tid i en linjediagram , selvom det i almindelighed er et NP-komplet problem. I betydningen af kompleksitetsteori .
Det kromatiske indeks for en graf G er lig med det kromatiske antal af dens linjegraf L ( G ). Faktisk svarer farvning af kanterne på en graf til farvning af hjørnerne i dens linjegraf .
Den linjegraf af et toppunkt-transitiv graf er en kant-transitiv graf .
Hvis en graf G har en Eulerian-cyklus , dvs. hvis G er forbundet, og alle dens hjørner er af lige grad, er linjegrafen L ( G ) en Hamiltonian-graf . Der kan dog Hamiltonian cyklusser i L ( G ), som ikke kommer Euler cyklusser i G .

Forhold til andre graffamilier

Den linje graf er klo-fri grafer , det vil sige grafer, der ikke tillader den graf klo som induceret delgraf .

Den linje graf af en todelt graf er en perfekt graf (se König sætning ). Den linje graf af delte grafer bruges i beviset for den perfekte graf sætning .

Karakterisering af linjegrafer

En graf G er linjediagrammet for en anden graf, hvis og kun hvis det er muligt at finde et sæt klikker i G, der skiller kanterne af G således, at hvert hjørne af G tilhører nøjagtigt to af klikkerne. Nogle af disse klikker kan reduceres til et enkelt toppunkt.

Ved et resultat af Hassler Whitney, hvis G ikke er en trekant, kan der kun være en sådan partition. Hvis der findes en sådan partition, er det muligt at finde den originale graf, hvoraf G er linjediagrammet . For at gøre dette, skal du blot oprette en top for hvert klik og forbinde med kanter par kliker, der deler en fælles toppunkt i G . Roussopoulos brugte i 1973 dette resultat som grundlag for at opbygge en algoritme, der gør det muligt at identificere linjediagrammerne i lineær tid.

En følge af dette resultat er, at bortset fra tilfældene med den komplette graf og den komplette bipartitgraf , hvis linjediagrammerne L ( G ) og L ( H ) for to grafer G og H er isomorfe, så er graferne G og H er isomorfe. $K_ {3}$ $K _ {{1,3}}$

En anden karakterisering af linje grafer blev foreslået af Beineke i 1968 (dengang bevist i 1970). Han viste, at der var ni minimale grafer, som ikke var linjegrafer, således at enhver graf, der ikke var en linjegraf, havde mindst en af disse minimale grafer som dens inducerede subgraf.

Iteration af linjegrafen operatør

I 1965 er van Rooij og Wilf interesseret i iteration af linjegrafoperatøren . Overvej følgende rækkefølge:

G, L (G), L (L (G)), L (L (L (G))), \ prikker. \

Derefter, hvis G er en endelig tilsluttet graf , er kun fire forskellige adfærdsmuligheder mulige for denne sekvens:

Hvis G er en cyklusgraf, så er L ( G ) såvel som hver graf i sekvensen en graf, der er isomorf for G selv. Cyklusgrafer er de eneste tilsluttede grafer, der er isomorfe til deres linjegraf .
Hvis G er klo-grafen K 1,3 , så er L ( G ) og alle graferne, der følger i sekvensen, trekantgrafer (derfor cykliske grafer med længde 3).
Hvis G er en kurvediagram , er hver graf, der følger i sekvensen, en kortere sti, indtil den slutter med singletongrafen og til sidst nulgrafen.
I alle andre tilfælde øges størrelsen på graferne i sekvensen uden at være afgrænset.

Hvis G ikke er tilsluttet, så er denne klassifikation gælder separat for hver tilsluttet komponent af G .

Anvendelser og anvendelser

Begrebet linjegraf bruges især i distribueret beregningsteori , for eksempel i den nedre grænse af Nati Linial til farvning af den lokale model.

Noter og referencer

(fr) Denne artikel er helt eller delvist taget fra Wikipedia-artiklen på engelsk med titlen " Linjegraf " ( se listen over forfattere ) .

(i) F. Harary og RZ Norman , " Nogle egenskaber ved linjegrafier " , Rendiconti del Circulo Mathematico di Palermo , flyvning. 9,1960, s. 161–169 ( DOI 10.1007 / BF02854581 ).
(da) H. Whitney , " Congruent graves and the connectivity of charts " , American Journal of Mathematics , bind. 54, nr . 1,1932, s. 150–168 ( DOI 10.2307 / 2371086 , læs online ).
(en) J. Krausz , " ny demonstration af Whitneys sætning på netværk " , Mat. Fiz. Lapok , vol. 50,1943, s. 75–85.
Didier Müller. Introduktion til grafteori. Cahiers de la CRM nummer 6, Kommissionen Romande de Mathématiques, 2012 [1] .
(in) ND Roussopoulos , " max { m , n } Algoritme til bestemmelse af grafen H fra icts linjediagram G " , Information Processing Letters , vol. 2, nr . 4,1973, s. 108–112 ( DOI 10.1016 / 0020-0190 (73) 90029-X ).
(en) LW Beineke , Beiträge zur Graphentheorie , Leipzig, Teubner,1968, 17–33 s..
(in) LW Beineke , " Karakterisering af afledte grafer " , Journal of Combinatorial Theory , bind. 9,1970, s. 129–135 ( DOI 10.1016 / S0021-9800 (70) 80019-9 ).
(in) ACM van Rooij og HS Wilf , " Udvekslingsgrafen for en endelig graf " , Acta Mathematica Hungarica , vol. 16, n knogle 3-4,1965, s. 263–269 ( DOI 10.1007 / BF01904834 ).
(i) Nathan Linial , " Lokalitet i distribuerede grafalgoritmer " , SIAM Journal we Computing , bind. 21, nr . 1,1992, s. 193-201.

Se også