Kantgraf
En kantgraf eller linjegraf är inom matematik, specifikt 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 i L(G) från kanten som binder ihop hörnen 1 och 4 i G.
-
Grafen G.
-
Hörn i L(G) konstrueras från kanterna i G.
-
Kanter i L(G) läggs till.
-
När hörnen i G tas bort får man kantgrafen L(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).
- En sammanhängande graf har en kantgraf som är sammanhängande. I en sammanhängande graf finns det en väg mellan alla par av hörn, vilket blir en väg som binder samman varje par av hörn i kantgrafen. En graf som har några isolerade hörn, och därför inte är sammanhängande, kan dock ha en sammanhängande kantgraf.
- En största oberoende mängd i en kantgraf motsvaras av en största matchning i den ursprungliga grafen.
- En hörntransitiv grafs kantgraf är en kanttransitiv graf.
- Om grafen G har en Eulercykel så har L(G) en Hamiltoncykel.
- Alla linjegrafer är klofria.
Karaktärisering[redigera | redigera wikitext]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/54/LineGraphExampleA.svg/150px-LineGraphExampleA.svg.png)
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 , så är två sammanhängande grafer isomorfa om deras kantgrafer är isomorfa.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Forbidden_line_subgraphs.svg/150px-Forbidden_line_subgraphs.svg.png)
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 ) 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]
- Godsil, Chris; Gordon Royle (2001). Algebraic Graph Theory. Springer Verlag. ISBN 0-387-95241-1
- Diestel, Reinhard (2005). Graph Theory. Springer Verlag. ISBN 3-540-26182-6
- Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, Line graph, 9 oktober 2009.
Fotnoter[redigera | redigera wikitext]
- ^ Whitney, H. (1932), ”Congruent graphs and the connectivity of graphs”, American Journal of Mathematics 54: 150–168, doi:
- ^ 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
- ^ Metelsky, Yury; Tyshkevich, Regina (1997), ”On line graphs of linear 3-uniform hypergraphs”, Journal of Graph Theory 25: 243–251, doi: