| dbo:abstract
|
- 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 -ból jön, bár a konstrukciót előtte és is használta. 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, továbbá az edge graph (élgráf), az interchange graph (cseregráf), az adjoint graph és a derived graph. igazolta, hogy egy kivételes esettől eltekintve az összefüggő gráfok szerkezete visszanyerhető élgráfjuk ismeretében. 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 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. (hu)
- 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 -ból jön, bár a konstrukciót előtte és is használta. 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, továbbá az edge graph (élgráf), az interchange graph (cseregráf), az adjoint graph és a derived graph. igazolta, hogy egy kivételes esettől eltekintve az összefüggő gráfok szerkezete visszanyerhető élgráfjuk ismeretében. 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 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. (hu)
|
