Remove ads
tah v grafu, který obsahuje každou hranu právě jednou From Wikipedia, the free encyclopedia
V teorii grafů se termínem eulerovský tah označuje takový tah, který obsahuje každou hranu grafu právě jednou. Zavedl jej Leonhard Euler, když se roku 1736 pokoušel vyřešit slavný problém sedmi mostů města Královce.
Existuje-li v grafu uzavřený eulerovský tah, nazýváme tento graf rovněž eulerovský. Eulerovské grafy lze nakreslit „jedním tahem“.
Je-li G = (V, E) neorientovaný graf a posloupnost, pro kterou platí, že , nazveme tuto posloupnost eulerovským tahem. Je-li , nazveme tento tah uzavřeným.
Pro orientované grafy je nutné pojem tah nahradit pojmem cyklus.
V orientovaných grafech lze použitím následujícího vzorce spočítat počet neekvivalentních eulerovských cyklů:
popřípadě
kde C je libovolný kofaktor Laplaceovy matice daného grafu.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.