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
|
Portal di Ensiklopedia Dunia