Kantgraf

Från Wikipedia
Hoppa till: navigering, sök

En kantgraf eller linjegraf är inom matematik, speficikt grafteori, en graf som konstrueras från en given graf så att kanter i den ursprungliga grafen blir hörn i kantgrafen.

Formellt definieras linjegrafen L(G) till grafen G så att varje hörn i L(G) representeras av en kant i G och att två hörn i L(G) binds samman med en kant om och endast om motsvarande kanter i G har en gemensam ändpunkt.

Exempel[redigera | redigera wikitext]

Nedan visas ett exempel på hur en kantgraf L(G) (längst till höger) konstrueras från en given graf G (längst till vänster). Hörnen i kantgrafen får här namn efter hörnen i G som kanten binder ihop. Exempelvis fås hörnet (1,4) i L(G) från kanten som binder ihop hörnen 1 och 4 i G.

Egenskaper[redigera | redigera wikitext]

Egenskaper hos en graf G som endast beror på närhet av kanter kan översättas till egenskaper i L(G) som endast beror på närhet av hörn. Exempelvis motsvaras en matchning i G av en oberoende mängd i L(G).

Karaktärisering[redigera | redigera wikitext]

En graf som inte är en kantgraf. Kanterna som går uppåt, vänster och höger från noden i mitten har inga klickar gemensamt, så varje partionering av grafens noder i klickar måste ha en klick var för dessa kanter, som alla måste ha med mittnoden, vilket bryter mot villkoret att varje nod ligger i högst två klickar.

En graf G kan fås som en kantgraf ur en annan graf om och endast om det finns en samling av klickar i G som partionerar kanterna i G sådan att varje hörn tillhör högst två klickar. Om G inte är en triangel finns det högst ett sätt att bilda en sådan partition.[1] Om en sådan partitionering finns kan man återskapa grafen som har G som linjegraf genom att skapa ett hörn för varje klick och skapa en kant mellan två hörn om det i G finns ett hörn som ligger i båda klickarna. Så, om man bortser från den kompletta grafen K3 och den kompletta bipartita grafen K_{1,3}, så är två sammanhängande grafer isomorfa om deras kantgrafer är isomorfa.

De nio minimala graferna som inte är kantgrafer.

En annan karaktärisering utgörs av att det finns nio minimala grafer (se bild till vänster) som inte är linjegrafer, dvs om en graf innehåller någon av dessa minimala icke-kantgrafer som inducerad delgraf, är det inte en kantgraf.[2] Exempelvis innehåller grafen till höger en klo (den komplett bipartita grafen K_{1,3}) som är en av de förbjudna graferna, och kan därför inte vara en kantgraf.

För grafer med minimal grad 5 eller högre behövs endast de sex graferna i den vänstra och den högra kolumnen. [3]

Referenser[redigera | redigera wikitext]

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia

Fotnoter[redigera | redigera wikitext]

  1. ^ Whitney, H. (1932), ”Congruent graphs and the connectivity of graphs”, American Journal of Mathematics 54: 150–168, doi:10.2307/2371086 
  2. ^ Beineke, L. W. (1968), ”Derived graphs of digraphs”, i Sachs, H.; Voss, H.-J.; Walter, H.-J., Beiträge zur Graphentheorie, Leipzig: Teubner, s. 17–33 
  3. ^ Metelsky, Yury; Tyshkevich, Regina (1997), ”On line graphs of linear 3-uniform hypergraphs”, Journal of Graph Theory 25: 243–251, doi:10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K