Eulerovský ťah: Rozdiel medzi revíziami
d revert |
dBez shrnutí editace |
||
Riadok 1: | Riadok 1: | ||
[[Súbor:Königsberg graph.svg|náhľad|Sedem mostov mesta [[Kaliningrad]] zobrazených ako graf]] |
[[Súbor:Königsberg graph.svg|náhľad|Sedem mostov mesta [[Kaliningrad]] zobrazených ako graf]] |
||
V [[Teória grafov|teórii grafov]] sa termínom '''eulerovský ťah''' označuje taký ťah, ktorý obsahuje každú hranu grafu práve jeden krát. Zaviedol ho [[Leonhard Euler]], keď sa v roku [[1736]] pokúšal vyriešiť slávny problém siedmych mostov cez [[Pregoľa|Pregoľu]] v [[Kaliningrad|Kráľovci]] vo [[Východné Prusko|Východnom Prusku]]. |
V [[Teória grafov|teórii grafov]] sa termínom '''eulerovský ťah''' označuje taký ťah, ktorý obsahuje každú hranu grafu práve jeden krát. Zaviedol ho [[Leonhard Euler]], keď sa v roku [[1736]] pokúšal vyriešiť slávny problém siedmych mostov cez [[Pregoľa|Pregoľu]] v [[Kaliningrad|Kráľovci]] ({{V jazyku|deu|Königsberg}}, dnešný Kaliningrad) vo [[Východné Prusko|Východnom Prusku]]. |
||
Ak existuje v grafe uzavrený eulerovský ťah, nazývame tento graf taktiež eulerovský.<ref>Základní pojmy z teorie grafů. [http://math.feld.cvut.cz/tiser/Grafy.pdf]</ref> Eulerovské grafy je možné nakresliť „jedným ťahom“. Eulerovské grafy majú každý vrchol párneho stupňa.<ref>{{cite journal |doi=10.1137/0128070 |author=C. L. Mallows, N. J. A. Sloane |title=Two-graphs, switching classes and Euler graphs are equal in number |journal=[[SIAM Journal on Applied Mathematics]] |volume=28 |year=1975 |pages=876–880 |jstor=2100368 |issue=4 |ref=harv}}</ref> |
Ak existuje v grafe uzavrený eulerovský ťah, nazývame tento graf taktiež eulerovský.<ref>Základní pojmy z teorie grafů. [http://math.feld.cvut.cz/tiser/Grafy.pdf]</ref> Eulerovské grafy je možné nakresliť „jedným ťahom“. Eulerovské grafy majú každý vrchol párneho stupňa.<ref>{{cite journal |doi=10.1137/0128070 |author=C. L. Mallows, N. J. A. Sloane |title=Two-graphs, switching classes and Euler graphs are equal in number |journal=[[SIAM Journal on Applied Mathematics]] |volume=28 |year=1975 |pages=876–880 |jstor=2100368 |issue=4 |ref=harv}}</ref> |
Verzia z 21:30, 27. november 2017
V teórii grafov sa termínom eulerovský ťah označuje taký ťah, ktorý obsahuje každú hranu grafu práve jeden krát. Zaviedol ho Leonhard Euler, keď sa v roku 1736 pokúšal vyriešiť slávny problém siedmych mostov cez Pregoľu v Kráľovci (nem. Königsberg, dnešný Kaliningrad) vo Východnom Prusku.
Ak existuje v grafe uzavrený eulerovský ťah, nazývame tento graf taktiež eulerovský.[1] Eulerovské grafy je možné nakresliť „jedným ťahom“. Eulerovské grafy majú každý vrchol párneho stupňa.[2]
Definícia
Eulerovský ťah v neorientovanom grafe je taký ťah v ktorom použijeme každú hranu práve raz. Ak takýto ťah existuje graf voláme „prejazdný“ alebo semi-eulerovský.[3]
Ak je neorientovaný graf a postupnosť, pre ktorú platí, že , nazývame túto postupnosť eulerovským ťahom. Ak je , nazývame tento ťah uzavretým.
Vlastnosti
- neorientovaný graf je eulerovský, ak je súvislý a každý jeho vrchol má párny stupeň,
- neorientovaný graf je eulerovský, ak je súvislý a ak má práva 2 vrcholy nepárneho stupňa (eulerov ťah bude potom otvorený),
- neorientovaný graf je eulerovský, ak je súvislý a ide hu rozložiť na hranovo disjunktné cykly.
Referencie
- ↑ Základní pojmy z teorie grafů. [1]
- ↑ C. L. Mallows, N. J. A. Sloane. Two-graphs, switching classes and Euler graphs are equal in number. SIAM Journal on Applied Mathematics, 1975, s. 876–880. DOI: 10.1137/0128070.
- ↑ Jun-ichi Yamaguchi, Introduction of Graph Theory.