Oreho veta
Oreho veta je matematické tvrdenie hovoriace o postačujúcej podmienke existencie hamiltonovskej kružnice v grafe. Vetu sformuloval v roku 1961 nórsky matematik Øystein Ore.
Znenie vety
[upraviť | upraviť zdroj]Nech G = (V,E) je neorientovaný graf s vrcholmi taký, že pre stupne ľubovoľnej dvojice nesusedných vrcholov platí
Potom G obsahuje hamiltonovskú kružnicu.
Dôkaz
[upraviť | upraviť zdroj]Sporom. Predpokladajme, že existuje graf G = (V,E) spĺňajúci podmienku zo znenia vety, ktorý hamiltonovskú kružnicu neobsahuje. Ďalej predpokladajme, že G je čo do počtu hrán maximálny graf o n vrcholoch s touto vlastnosťou, t. j. po pridaní ľubovoľnej hrany v grafe vznikne hamiltonovská kružnica.
Graf s vrcholmi, ktorý neobsahuje hamiltonovskú kružnicu, zjavne nemôže byť kompletný, a preto v grafe G existuje dvojica nesusedných vrcholov . Zo skutočnosti, že G je maximálny nehamiltonovský graf vyplýva, že po pridaní hrany do E dostávame hamiltonovský graf. Každá hamiltonovská kružnica v tomto grafe musí nutne obsahovať hranu e, pretože inak by bol aj graf G hamiltonovský. Z toho vyplýva, že G obsahuje hamiltonovskú cestu
Položme
a
Keďže x a y sú nesusedné, z predpokladu vety vyplýva
Vrchol však zjavne nepatrí ani do A, ani do B, a preto
Z uvedených dvoch nerovností potom vyplýva
čo znamená, že existuje vrchol patriaci súčasne do A aj do B. Potom však môžeme v grafe G skonštruovať hamiltonovskú kružnicu nasledujúcim spôsobom: z do po hamiltonovskej ceste grafu G. Zo skutočnosti vyplýva, že susedí s , prejdeme teda do a spätným postupom po hamiltonovskej ceste prídeme až do vrchola , ktorý, keďže patrí do A, susedí s . Prechodom do x tak je možné hamiltonovskú kružnicu uzatvoriť.
Existencia tejto kružnice je však v spore s predpokladom, že G nie je hamiltonovský. Tvrdenie je tak dokázané.
Literatúra
[upraviť | upraviť zdroj]- Cameron, P.J.: Combinatorics: Topics, techniques, algorithms. Cambridge University Press, 1994.
Externé odkazy
[upraviť | upraviť zdroj]- Znenie Oreho vety - Wolfram MathWorld (po anglicky).