Hrana (teória grafov)
Z Wikipédie
Hrana v teórii grafov znamená spojnicu dvoch (v niektorých špeciálnych prípadoch aj viacerých) vrcholov grafu G = (V, H). Hrany sa delia na neorientované a orientované. Neorientované hrany sú charakterizované neusporiadanou dvojicou vrcholov {u, v}. Na druhej strane 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 H 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 h, potom je vrchol u incidentný s hranou h. 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 grafov 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.