Hrana (teória grafov)

Hrana v teórii grafov je spojnica dvoch (v niektorých špeciálnych prípadoch aj viacerých) vrcholov grafu G = (V, E). Množinu hrán budeme v článkoch označovať  a jednotlivú hranu , z anglického edge. V slovenskej literatúre sa zvyknú tiež označovať  a . Hrany sa delia na neorientované a orientované. Neorientované hrany sú charakterizované neusporiadanou dvojicou vrcholov {u, v}, orientované hrany sú popisované usporiadanou dvojicou vrcholov (u, v), kde u je začiatočný a v koncový vrchol. V oboch prípadoch patria u a v množine V. Ak sa v množine E nachádza hrana {u, v} alebo (u, v), vrcholy u a v sa nazývajú susednými alebo priľahlými. Podobne dve hrany, ktoré majú spoločný vrchol sa nazývajú susedné. Ak je u jeden z vrcholov hrany e, potom je vrchol u incidentný s hranou e. V prípade, že platí u = v, takáto hrana sa nazýva slučka.

Neorientovaná hrana sa zvyčajne kreslí ako úsečka medzi vrcholmi, zatiaľ čo orientovaná ako šípka smerujúca od začiatočného vrcholu po koncový. Keďže hrany v grafoch spájajú vrcholy, reprezentujú tak napríklad cesty v cestnej sieti, kabeláž v telefónnej sieti či možnosť prechodu z jedného stavu do iného, ak vrcholy predstavujú tieto stavy.

Typy hrán
 orientovaná hrana – usporiadaná dvojica vrcholov; má vyznačený smer prechodu, hranou možno  prechádzať iba vo vyznačenom smere
 neorientovaná hrana – neusporiadaná dvojica; bez vyznačenia smeru prechodu, hranou možno  prechádzať oboma smermi
 násobné hrany – viac hrán spojujúcich rovnaké vrcholy
 slučka – hrana vedúca z vrcholu do neho samého
 ohodnotené hrany - Hrana môže byť ohodnotená. Ohodnotenie hrany vyjadruje kvalitu alebo kvantitu vzťahu medzi dvoma vrcholmi (napríklad vzdialenosť, priepustnosť, ...).

Kategória:Teória grafov