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