Hrana (teória grafov)

a) neorientovaná hrana, b) priama orientovaná hrana, c) a d) rovnobežné hrany, e) a f) násobné hrany, g) orientovaná slučka, h) neorientovaná slučka, i) a j) násobné hrany so slučkou

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ť $E\$ a jednotlivú hranu $e\$, z anglického edge. V slovenskej literatúre sa zvyknú tiež označovať $H\$ a $h\$. 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ť, ...).