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é.