Co je to Traversable Graph v teorii grafů?
V kontextu teorie grafů je prostupný graf graf, ve kterém je možné procházet všechny vrcholy a hrany. Jinými slovy, je to graf, který nám umožňuje navštívit každý vrchol přesně jednou a vrátit se do výchozího vrcholu. .
Uvažujme například jednoduchý graf se třemi vrcholy A, B a C, kde je hrana mezi A a B, hrana mezi B a C a hrana mezi A a C. Tento graf je průchodný, protože můžeme začněte ve vrcholu A, postupujte podle hran k B a pak k C a vraťte se k A.
Na druhou stranu graf se dvěma oddělenými komponentami, jako jsou dva samostatné grafy, nelze procházet, protože není možné navštívit každý vrchol přesně jednou a vrátit se do výchozího vrcholu.
To se mi líbí
To se mi nelíbí
Nahlásit chybu obsahu
Podíl
