Hrana (graf)

Hrana je v teorii grafů uspořádaná nebo neuspořádaná dvojice (obecně k-tice) vrcholů grafu. Graficky se znázorňuje jako úsečka nebo oblouk mezi vrcholy, které spojuje.

a) neorientovaná hrana, b) přímá orientovaná hrana, c) a d) násobné hrany, e) a f) rovnoběžné hrany, g) orientovaná smyčka, h) neorientovaná smyčka, i) a j) násobné hrany se smyčkou

Typy hran

orientovaná hrana – uspořádaná dvojice vrcholů; má vyznačen směr průchodu, hranou lze procházet pouze ve vyznačeném směru
neorientovaná hrana – neuspořádaná dvojice; bez vyznačení směru průchodu, hranou lze procházet oběma směry
násobné hrany – více hran spojujících stejné vrcholy
most – hrana, jejímž odebráním se zvýší počet komponent grafu
smyčka – hrana vedoucí z vrcholu do něj samotného

Hrana může být ohodnocena. Ohodnocení hrany vyjadřuje kvalitu nebo kvantitu vztahu mezi dvěma vrcholy (například vzdálenost, průchodnost apod.).

Označení grafů

Výskyt různých typů hran má vliv na označení grafu:

jednoduchý (obyčejný) graf – neobsahuje smyčky a násobné hrany
multigraf – obsahuje násobné hrany
prostý graf – neobsahuje násobné hrany
pseudograf – obsahuje smyčky

Rovnoběžné hrany

Pojem rovnoběžné (paralelní) hrany má význam u grafu s násobnými hranami. Pojem rovnoběžných hran je důležitý při určování několika různých vlastností grafů, například: Stupeň uzlu, jestli je graf obyčejný, úplný, prostý nebo například souvislost grafů či jiné.

V neorientovaném grafu jako rovnoběžné hrany určujeme dvě či více hran, které spojují stejnou dvojici uzlů.
V orientovaném grafu jako rovnoběžné hrany určujeme dvě či více hran, které spojují stejnou dvojici uzlů a jsou stejně orientované.