Preskočiť na obsah

Oreho veta

z Wikipédie, slobodnej encyklopédie

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.

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]