linjenettverkene

Linjenettverkene er i grafteori en representasjon av kantene i en graf ved å danne en ny graf hvor hver kant i den opprinnelige grafen blir til en node i linjenettverket. To noder i linjenettverket er koblet dersom de tilsvarende kantene i den opprinnelige grafen deler et felles endepunkt.

Formelt: hvis G = (V, E) er en enkel graf, er linjenettverket L(G) = (E, E′), der to kanter e1 og e2 i E er adjacent i L(G) hvis e1 og e2 deler en endepunkt i G (de er ifølge kantene i G inne i samme vertex). Dette setter kantenes akse i fokus og gir en ny graf som avbilder et annet aspekt av den opprinnelige strukturen.

Eksempler er enkle å observere: L(Pn) = Pn−1 for en sti Pn, og L(Cn) = Cn for en syklus Cn. En stjerne K1,m gir L(K1,m) = Km, en fullstendig graf på m vertexer. Generelle egenskaper inkluderer at graden til en kant e = uv i L(G) er deg(u) + deg(v) − 2, og at linjenettverkene er claw-fri (ingen indukt subgraf er K1,3).

Begrensninger og gjenkjenning: ikke alle grafer er linjenettverk for en annen graf, og kjennskap til hvilke som er linjenettverk kan være utfordrende. Belegeineske teorem beskriver ni forbudte indukte undergrafer som karakteriserer linjenettverk. Linjenettverk kjenner vanligvis tilførsel i algoritmer og brukes i kjemi og nettverksdesign, samt i teoretiske undersøkelser av relasjoner mellom grafstrukturer.