Teorie grafů: základní pojmy
Graf je struktura, která nám pomáhá znázorňovat objekty a vztahy mezi nimi. Skládá se z vrcholů a hran. Vrcholy často reprezentují reálné objekty a obvykle je kreslíme jako tečky nebo kolečka. Hrany představují vztahy mezi vrcholy, na obrázku obvykle vypadají jako čáry mezi vrcholy. Každá hrana vede mezi dvěma vrcholy, oba její konce tedy musí být připojeny k některému vrcholu.
Mezi základní grafové pojmy patří:
- Stupeň vrcholu je počet hran, které z daného vrcholu vychází.
- Cesta mezi dvěma určenými vrcholy existuje, pokud v grafu dokážeme přejít po hranách z jednoho vrcholu do druhého.
- Vzdálenost dvou vrcholů je délka nejkratší cesty mezi těmito vrcholy. Naopak nám vůbec nezáleží na tom, jak daleko jsou od sebe vrcholy na obrázku, pokud graf nakreslíme.
Dále si ukážeme některá rozšíření obyčejných grafů, tedy druhy grafů, jejichž vlastnosti jsou nějakým způsobem upravené.
V orientovaném grafu mají hrany přesně určený směr, kterým vedou, a tedy i začáteční a koncový vrchol. To je rozdíl od grafů, o kterých jsme uvažovali doposud – tam hrany vedou „mezi vrcholy“ a nemají dáno, kde začínají a kde končí. Hrany orientovaných grafů se často znázorňují jako šipky.
V ohodnoceném grafu má každá hrana přiřazenu určitou hodnotu (nazývanou také váha). V obrázku píšeme váhy jako čísla ke hranám. Pomocí těchto hodnot můžeme snadno znázornit například délky cest mezi městy.
Zavřít