Přejít na cvičení:
Rozhodovačka
Přejít na téma:
Teorie grafů: základní pojmy
Zobrazit na celou obrazovku
Procvičujte neomezeně

Váš denní počet odpovědí je omezen. Pro navýšení limitu či přístup do svého účtu s licencí se přihlaste.

Přihlásit se
Zobrazit shrnutí tématu
MR1
Sdílet
Zobrazit nastavení cvičení

QR kód

QR kód lze naskenovat např. mobilním telefonem a tak se dostat přímo k danému cvičení nebo sadě příkladů.

Kód / krátká adresa

Tříznakový kód lze napsat do vyhledávacího řádku, také je součástí zkrácené adresy.

Zkopírujte kliknutím.

MR1
umime.to/MR1

Nastavení cvičení


Pozor, nastavení je platné pouze pro toto cvičení a předmět.

umime.to/MR1

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

Teorie grafů: základní pojmy (střední)

Vyřešeno:

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