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

Smazaný obsah Přidaný obsah
Otm (diskusia | príspevky)
d H na E
Otm (diskusia | príspevky)
d a
Riadok 1:
[[Obrázok:Graph edge.png|thumb|upright=2|a) neorientovaná hrana, b) priama orientovaná hrana, c) a d) rovnobežné hrany, e) a f) násobné hrany, g) orientovaná smyčka, h) neorientovaná smyčka, i) a j) násobné hrany so smyčkou ]]
 
'''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, E)''. Množinu hrán budeme v článkoch označovať <math>E\ </math> a jednotlivú hranu <math>e\ </math>, z englickéhoanglické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}'', 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 ''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.