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
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
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
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.
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
- 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
- ^ 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: