Hrana (teória grafov): Rozdiel medzi revíziami

'''Hrana''' v [[Teória grafov|teórii grafov]] znamená spojnicu dvoch (v niektorých špeciálnych prípadoch aj viacerých) [[Vrchol (teória grafov)|vrcholov]] [[Graf (matematika)|grafu]] ''G = (V, HE)''. Množinu hrán budeme v článkoch označovať <math>E\ </math> a jednotlivú hranu <math>e\ </math>, z englického edge. V slovenskej literatúre sa zvyknú tiež označovať <math>H\ </math> a <math>h\ </math>. Hrany sa delia na '''neorientované''' a '''orientované'''. Neorientované hrany sú charakterizované neusporiadanou dvojicou vrcholov ''{u, v}''. Na druhej strane, orientované hrany sú popisované [[usporiadaná dvojica|usporiadanou dvojicou vrcholov]] ''(u, v)'', kde ''u'' je začiatočný a ''v'' koncový vrchol. V oboch prípadoch patria ''u'' a ''v'' [[množina|množine]] ''V''. Ak sa v množine ''HE'' 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 ''he'', potom je vrchol ''u'' '''incidentný''' s hranou ''he''. 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 grafovgrafoch 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.