A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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
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
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
- Cameron, P.J.: Combinatorics: Topics, techniques, algorithms. Cambridge University Press, 1994.
Externé odkazy
- Znenie Oreho vety - Wolfram MathWorld (po anglicky).
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk