Děkujeme za Vaše hodnocení.

Teorie grafů: základní pojmy

MZH
Zkopírovat krátkou adresu (umime.to/MZH)
Ukázat QR kód

umime.to/MZH


Stáhnout QR kód
Ukázat/skrýt shrnutí

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.

Souhrn mi pomohl
Souhrn mi nepomohl
Souhrn je skryt.

Rozhodovačka

Rychlé procvičování výběrem ze dvou možností.


Teorie grafů: základní pojmy  
Zobrazit souhrn tématu


Pexeso

Hledání dvojic, které k sobě patří.


Teorie grafů: základní pojmy  
Zobrazit souhrn tématu


NAPIŠTE NÁM

Děkujeme za vaši zprávu, byla úspěšně odeslána.

Napište nám

Nevíte si rady?

Nejprve se prosím podívejte na časté dotazy:

Čeho se zpráva týká?

Vzkaz Obsah Ovládání Přihlášení Licence