Кіріспе
Оре теоремасы – сақиналар теориясындағы, 1960 жылы норвегиялық математик Ойштейн Оре дәлелдеген нәтиже. Бұл теорема графтың Гамильтондық болуы үшін жеткілікті шартты келтіреді, яғни, жеткілікті көп қабырғалары бар граф Гамильтон циклын қамтиды. Атап айтқанда, теорема жанындас емес төбелер жұптарының дәрежелерінің қосындысын қарастырады: егер мұндай әрбір жұптың қосындысы графиктегі төбелердің жалпы санынан кем болмаса, онда граф Гамильтондық болады.
Ore's theorem is a result in graph theory proved in 1960 by Norwegian mathematician Øystein Ore. It gives a sufficient condition for a graph to be Hamiltonian, essentially stating that a graph with sufficiently many edges must contain a Hamilton cycle. Specifically, the theorem considers the sum of the degrees of pairs of non adjacent vertices: if every such pair has a sum that at least equals the total number of vertices in the graph, then the graph is Hamiltonian.
Ресми мәлімдеме
G n ≥ 3 төбесі бар (шекті және қарапайым) граф болсын. Біз deg v арқылы G графындағы v төбесінің дәрежесін, яғни v төбесіне жанасқан қабырғалар санын белгілейміз. Содан кейін, Оре теоремасы былай гластейды: егер
болса, онда G гамильтондық болады.
Дәлел
Бұл Г-ның барлық Гамильтондық емес графигі (*)-шартты орындамайтынын көрсетумен тең. Осыған сәйкес, G n ≥ 3 төбесі бар Гамильтондық емес граф болсын, ал H Гамильтондық циклды жасамастан G-ден біртіндеп қабырғаларды қосу арқылы құрылсын, одан әрі қабырғаларды қосу мүмкін болмайтындай. Х және у H-де кез келген екі іргелес емес төбе болсын. Содан кейін H-ге xy қабырғасын қосу кем дегенде бір жаңа Гамильтондық циклды жасайды, ал мұндай циклдағы xy-дан басқа қабырғалар H-де 1=x = v1 және 1=y = vn Гамильтондық жол v1v2…vn құрауы керек. 2 ≤ i ≤ n аралығындағы әрбір i индексі үшін H-дегі v1-ден vi-ға және vi-1-ден vn-ға дейінгі екі мүмкін қабырғаны қарастырыңыз. Бұл екі қабырғаның ең көп дегенде біреуі H-да болуы мүмкін, әйтпесе v1v2…vi-1vnvn-1vi циклі Гамильтондық цикл болар еді. Осылайша, v1 немесе vn-ге түсетін қабырғалардың жалпы саны i-нің таңдау санымен тең, яғни n - 1. Сондықтан H (*)-қасиетке бағынбайды, бұл қабырғалардың жалпы саны (deg v1 + deg vn) n-ден үлкен немесе оған тең болуы керек. G-дегі төбелердің дәрежелері ең көп дегенде H-дегі дәрежелерге тең болғандықтан, G де (*)-қасиетке бағынбайды.
Байланысты нәтижелер
Оре теоремасы – Дирак теоремасының жалпылауы болып табылады, егер әрбір төбесінің дәрежесі кем дегенде n/2 болса, онда граф Гамильтондық болады. Егер граф Дирак шартына сай келсе, онда әрбір төбе жұбының дәрежелерінің қосындысы кем дегенде n-ге тең болады. Өз кезегінде Оре теоремасы Бонди–Чватал теоремасымен жалпыландырылады. Графқа жабылу операциясын қолдануға болады, яғни егер екі жаппасы көршілес емес төбелердің дәрежелерінің қосындысы кем дегенде n-ге тең болса, онда оларды қосатын қабырға қосылады; егер граф Оре теоремасының шарттарына сәйкес келсе, оның жабылуы толық граф болады. Бонди–Чватал теоремасы графтың Гамильтондық екенін, оның жабылуы Гамильтондық болған жағдайда ғана айтады; толық граф Гамильтондық болғандықтан, Оре теоремасы оның тікелей салдары болып табылады. Оре теоремасының бағытталған графтарға қатысты нұсқасы да бар. Егер G диграфындағы кез келген u және v төбелері үшін, u-ден v-ге қабырға болса немесе u-дың шығу дәрежесі және v-ның кіру дәрежесі G графындағы төбелер санынан кем емес немесе тең болса, онда Вудолл теоремасы бойынша G-де бағытталған Гамильтон циклі болады. Оре теоремасын Вудоллдан берілген бағытталмаған графтың әрбір қабырғасын бағытталған қабырғалар жұбымен алмастыру арқылы алуға болады. Оған жақын теорема, n төбесі бар және қатты байланысқан диграфта, кез келген жаппасы көршілес емес u және v төбелері үшін, u немесе v төбелеріне келіп түсетін қабырғалардың жалпы саны кем дегенде 2n–1 болса, онда граф Гамильтондық болады деп мәлімдейді. Оре теоремасын теоремадағы дәрежелік шарттың нәтижесі ретінде Гамильтондықтан да күшті қорытынды беру үшін күшейтуге болады. Атап айтқанда, Оре теоремасының шарттарын қанағаттандыратын әрбір граф – тұрақты толық екі бөлікті граф немесе панциклдік граф болып табылады.
In turn Ore's theorem is generalized by the Bondy–Chvátal theorem. One may define a closure operation on a graph in which, whenever two nonadjacent vertices have degrees adding to at least n, one adds an edge connecting them; if a graph meets the conditions of Ore's theorem, its closure is a complete graph. The Bondy–Chvátal theorem states that a graph is Hamiltonian if and only if its closure is Hamiltonian; since the complete graph is Hamiltonian, Ore's theorem is an immediate consequence. found a version of Ore's theorem that applies to directed graphs. Suppose a digraph G has the property that, for every two vertices u and v, either there is an edge from u to v or the outdegree of u plus the indegree of v equals or exceeds the number of vertices in G. Then, according to Woodall's theorem, G contains a directed Hamiltonian cycle. Ore's theorem may be obtained from Woodall by replacing every edge in a given undirected graph by a pair of directed edges. A closely related theorem by states that an n vertex strongly connected digraph with the property that, for every two nonadjacent vertices u and v, the total number of edges incident to u or v is at least 2n − 1 must be Hamiltonian. Ore's theorem may also be strengthened to give a stronger conclusion than Hamiltonicity as a consequence of the degree condition in the theorem. Specifically, every graph satisfying the conditions of Ore's theorem is either a regular complete bipartite graph or is pancyclic .