Hrana (graf)

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání
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

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

Typy hran[editovat | editovat zdroj]

  • 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ů[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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