Teorie grafů a její aplikace v dopravě

Front

Co je to neorientovaný graf?

Back

Uspořádaná trojice G=(V,X,p), kde V je konečná neprázdná množina vrcholů a X jsou hrany, které spojují tyto vrcholy.

Front

Jaký je stupeň vrcholu v neorientovaném grafu?

Back

Počet hran incidujících s vrcholem v grafu.

Front

Co je to orientovaný graf (digraf)?

Back

Graf D=(V,Y,p), kde Y jsou orientované hrany a p přiřazuje každé hraně uspořádanou dvojici vrcholů.

Front

Jak se nazývá hrana, jejímž odstraněním se počet komponent grafu zvýší o 1?

Back

Most.

Front

Jaké jsou speciální typy grafů?

Back

Izolovaný vrchol, prázdný graf, triviální graf, diskrétní graf, úplný graf, pravidelný graf, kružnice.

Front

Co je to podgraf?

Back

Graf G'=(V',X',p') je podgrafem grafu G=(V,X,p), pokud V'⊆V, X'⊆X a pro každou hranu h∈X' platí p'(h)=p(h).

Front

Jaké jsou vlastnosti stromu?

Back

Souvislý graf typu strom, každá hrana je most, každý vrchol se stupněm 2 a více je artikulací, |X|=|V|-1.

Front

Co je to heuristická metoda?

Back

Metoda, která poskytuje řešení, o kterém nevíme, zda je optimální.

Front

Jaké jsou příčiny neúspěchu v optimalizaci?

Back

1) Neexistence vhodné metody, 2) Nedostatek relevantních dat, 3) Nesprávná volba metody, 4) Zanedbání významných faktorů.

Front

Co je to Eulerova věta pro rovinné grafy?

Back

p + r - q = 2, kde p je počet vrcholů, r je počet stěn a q je počet hran.