Hamiltonovská kružnica je taký podgraf, ktorý je kružnica a obsahuje všetky vrcholy pôvodného grafu.
Postačujúce podmienky existencie hamiltonovskej kružnice: Podmienka 1: Nech pre graf G=(V, H), ktorý má aspoň 3 vrcholy, platí pre každé jeho 2 rôzne nepriľahlé vrcholy u, v st(u) + st(v) ≥ |V| . Potom graf obsahuje hamiltonovskú kružnicu. Podmienka 2: Nech pre graf G=(V, H), ktorý má aspoň 3 vrcholy, platí pre každý vrchol v V st(v) ≥ |V| / 2 . Potom graf obsahuje hamiltonovskú kružnicu.
Pozri aj
Hamiltonovský graf
Externé odkazy Hamiltonovská kružnica
Kategória:Diskrétna matematika Kategória:Teória grafov