„Elválasztó él” változatai közötti eltérés

 

==Fák és erdők==

 

Minden irányítatlan gráfban létezik a csúcsokon értelmezett [[ekvivalenciareláció]], mely szerint két csúcs relációban van egymással, ha létezik közöttük egyetlen élükben sem megegyező két út (minden csúcs relációban van saját magával, amennyiben létezik a saját magával összekötő két nulla hosszúságú út, melyek ugyan megegyeznek, de egyetlen közös élük sincs). A reláció ekvivalenciaosztályai a '''kétszeresen élösszefüggő komponensek''', és a gráf hídjai pontosan azok az élek, melyek végpontjai különböző komponensekhez tartoznak. Egy gráf '''híd–blokk fája''' ''(bridge-block tree)'' egy-egy csúcsot tartalmaznak az eredeti gráf minden nem triviális komponense után, és minden hídhoz egy élet.<ref>{{citation