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
Eksempler er enkle å observere: L(Pn) = Pn−1 for en sti Pn, og L(Cn) = Cn for en syklus
Begrensninger og gjenkjenning: ikke alle grafer er linjenettverk for en annen graf, og kjennskap til hvilke