Élgráf
matematikai fogalom a gráfelméletben / From Wikipedia, the free encyclopedia
A gráfelmélet területén egy irányítatlan G gráfhoz tartozó élgráf egy olyan L(G) gráf, amely a G gráf élei közötti szomszédsági viszonyokat reprezentálja. Röviden élgráf az a gráf, amiben a csúcspontok az eredeti gráf élei, és két csúcs akkor van összekötve, ha az eredeti gráfban a két élnek volt közös végpontja. Maga az élgráf (line graph) kifejezés (Harary & Norman 1960)-ból jön, bár a konstrukciót előtte (Whitney 1932) és (Krausz 1943) is használta.[1] Az élgráf egyéb megnevezései közé tartozik a covering graph (burkológráf), a derivative (származtatott gráf), az edge-to-vertex dual (él–csúcs-duális), a conjugate (konjugált gráf), a representative graph (reprezentatív gráf) és a ϑ-obrazom,[2] továbbá az edge graph (élgráf), az interchange graph (cseregráf), az adjoint graph és a derived graph.[3]
Hassler Whitney (1932) igazolta, hogy egy kivételes esettől eltekintve az összefüggő gráfok szerkezete visszanyerhető élgráfjuk ismeretében.[4] Az élgráfok számos tulajdonsága közvetlenül az eredeti gráf csúcsainak élekké konvertálására vezethető vissza, és Whitney tétele értelmében ez az átalakítás visszirányban is végrehajtható. Az élgráfok karommentesek, a páros gráfok élgráfjai pedig perfekt gráfok. Az élgráfokat kilenc tiltott részgráf jellemzi, és lineáris idő alatt felismerhetők.
Az élgráfok számos általánosítását tanulmányozták már, köztük az élgráfok élgráfjait, a multigráfok élgráfjait, a hipergráfok élgráfjait és a súlyozott gráfok élgráfjait.