Hamiltonovská kružnica

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