Všetky hamiltonovské grafy sú vzájomne prepojené, ale obojstranne spojený graf nemusí byť hamiltonovský (pozri napríklad Petersenov graf). Eulerovský graf G (súvislý graf, v ktorom má každý vrchol párny stupeň) má nevyhnutne Eulerovu cestu, uzavretú prechádzku prechádzajúcu každou hranou G presne raz.
Môže byť graf hamiltonovský, ale nie eulerovský?
Súvislý graf G je hamiltonovský, ak existuje cyklus, ktorý zahŕňa každý vrchol G; takýto cyklus sa nazýva hamiltonovský cyklus. … Tento graf je eulerovský aj hamiltonovský. Tento graf je eulerovský, ale NIE hamiltonovský. Tento graf je hamiltioniánsky, ale NIE JE eulerovský.
Je každý hamiltonovský graf eulerovský?
Nie. Hamiltonovská cesta navštívi každý vrchol presne raz, ale môže sa opakovať hrany. Eulerovský okruh prechádza každou hranou v grafe presne raz, ale môže sa opakovať vrcholy.
Čo nie je eulerovské a nie hamiltonovské?
Úplný bipartitný graf K2, 4 má eulerovský okruh, ale je nehamiltonovský (v skutočnosti neobsahuje ani hamiltonovskú cestu). Každá hamiltonovská cesta by striedala farby (a nie je dostatok modrých vrcholov).
Sú všetky úplné grafy eulerovské?
Graf je Eulerovský práve vtedy, ak je stupeň každého vrcholu párny. Preto je Kn eulerovské, ak je n nepárne. (ii) Jediný semieulerovský úplný graf je K2. … Graf je prepojený a je ich tam presnedva vrcholy nepárneho stupňa.
