Ore's theorem (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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. (en) オーレの定理（オーレのていり、英: Ore's theorem）は、ノルウェーの数学者 によって1960年に証明されたグラフ理論の定理である。オアの定理とも表記される。これはグラフがハミルトングラフであるための十分条件を与えるもので、実質的に、グラフに十分多くの辺が存在していればハミルトン閉路を含んでいなければならないと述べている。特に、この定理ではグラフの隣接しない2頂点の次数の和について考える。もしこのような和が常にグラフの頂点数以上であれば、グラフはハミルトングラフである。 (ja) Il teorema di Ore è un teorema della teoria dei grafi provato nel 1960 dal matematico Norvegese Øystein Ore.Fornisce una condizione sufficiente, ma non necessaria, affinché un grafo sia Hamiltoniano, affermando che un grafo che contiene un sufficiente numero di archi, comparati al numero di vertici, deve contenere un ciclo Hamiltoniano. Esso è inoltre una generalizzazione del teorema di Dirac e a sua volta viene generalizzato dal teorema di Bondy-Chvátal. (it) Теорема Оре — результат в теории графов, доказанный в 1960 году норвежским математиком Ойстином Оре. Теорема даёт достаточное условие для того, чтобы граф был гамильтоновым, по существу утверждая, что граф с «достаточно большим числом рёбер» должен содержать гамильтонов цикл. В частности, теорема рассматривает суммы степеней пар несмежных вершин — если каждая такая пара в сумме даёт как минимум общее число вершин графа, граф является гамильтоновым. (ru) Twierdzenie Orego – twierdzenie podające warunek wystarczający na to, aby graf miał cykl Hamiltona. Zostało ono sformułowane w roku 1961 przez norweskiego matematyka Øysteina Orego. (pl) O Teorema de Ore é um resultado provado em 1960 pelo matemático norueguês Øystein Ore relacionado à Teoria dos grafos.Ele fornece uma condição suficiente para um grafo para ser Hamiltoniano, essencialmente, afirmando que um grafo com "quantidade de arestas suficiente" deve conter um ciclo de Hamilton. Especificamente, a teoria considera a soma dos graus dos pares de vértices não adjacentes: se cada um destes pares tem uma soma que, pelo menos, é equivalente ao número total de vértices no grafo, então o mesmo é Hamiltoniano. (pt) Теорема Оре — результат в теорії графів, доведений в 1960 році норвезьким математиком . Теорема дає достатню умову для того, щоб граф був гамільтоновим, по суті стверджуючи, що граф з «досить великим числом ребер» повинен містити гамільтонів цикл. Зокрема, теорема розглядає суми степенів пар несуміжних вершин - якщо кожна така пара в сумі дає як мінімум загальне число вершин графу, граф є гамільтоновим. (uk) 奥尔定理是挪威数学家奥斯丁·欧尔在1960年证明的图论定理。它为判断图为哈密顿图提供了一个充分条件，并且从本质上说明了如果一个图具有足够多的边，则它必然包含哈密顿环。具体来说，如果一个图中每一对非相邻顶点的度数和都大于等于顶点总数，那么该图为哈密顿图。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Ore_theorem_example.svg?width=300 |
| dbo:wikiPageID | 3100586 (xsd:integer) |
| dbo:wikiPageLength | 9462 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1032016963 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Non-adjacent dbr:Regular_graph dbr:Degree_(graph_theory) dbc:Articles_containing_proofs dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Graph_(discrete_mathematics) dbr:Øystein_Ore dbr:American_Mathematical_Monthly dbr:Edge_(graph_theory) dbc:Hamiltonian_paths_and_cycles dbr:Norway dbr:Directed_graph dbr:Graph_theory dbr:Strongly_connected_component dbc:Theorems_in_graph_theory dbr:Hamiltonian_graph dbr:Hamiltonian_path dbc:Extremal_graph_theory dbr:Vertex_(graph_theory) dbr:Dirac's_theorem_on_Hamiltonian_cycles dbr:Pancyclic_graph dbr:Hamilton_cycle dbr:Bondy–Chvátal_theorem dbr:Incidence_(graph_theory) dbr:Journal_of_Combinatorial_Theory,_Series_B dbr:File:Ore_theorem_example.svg dbr:File:Ore_theorem_proof.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:For dbt:Harv dbt:Harvtxt dbt:Math dbt:Mvar dbt:NumBlk |
| dct:subject | dbc:Articles_containing_proofs dbc:Hamiltonian_paths_and_cycles dbc:Theorems_in_graph_theory dbc:Extremal_graph_theory |
| gold:hypernym | dbr:Result |
| rdf:type | yago:WikicatMathematicalTheorems yago:WikicatTheoremsInGraphTheory yago:Abstraction100002137 yago:Act100030358 yago:Action100037396 yago:Communication100033020 yago:Course100038262 yago:Event100029378 yago:Message106598915 yago:Proposition106750804 yago:PsychologicalFeature100023100 yago:WikicatHamiltonianPathsAndCycles yago:YagoPermanentlyLocatedEntity yago:Statement106722453 yago:Theorem106752293 yago:Way100415676 |
| rdfs:comment | 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. (en) オーレの定理（オーレのていり、英: Ore's theorem）は、ノルウェーの数学者 によって1960年に証明されたグラフ理論の定理である。オアの定理とも表記される。これはグラフがハミルトングラフであるための十分条件を与えるもので、実質的に、グラフに十分多くの辺が存在していればハミルトン閉路を含んでいなければならないと述べている。特に、この定理ではグラフの隣接しない2頂点の次数の和について考える。もしこのような和が常にグラフの頂点数以上であれば、グラフはハミルトングラフである。 (ja) Il teorema di Ore è un teorema della teoria dei grafi provato nel 1960 dal matematico Norvegese Øystein Ore.Fornisce una condizione sufficiente, ma non necessaria, affinché un grafo sia Hamiltoniano, affermando che un grafo che contiene un sufficiente numero di archi, comparati al numero di vertici, deve contenere un ciclo Hamiltoniano. Esso è inoltre una generalizzazione del teorema di Dirac e a sua volta viene generalizzato dal teorema di Bondy-Chvátal. (it) Теорема Оре — результат в теории графов, доказанный в 1960 году норвежским математиком Ойстином Оре. Теорема даёт достаточное условие для того, чтобы граф был гамильтоновым, по существу утверждая, что граф с «достаточно большим числом рёбер» должен содержать гамильтонов цикл. В частности, теорема рассматривает суммы степеней пар несмежных вершин — если каждая такая пара в сумме даёт как минимум общее число вершин графа, граф является гамильтоновым. (ru) Twierdzenie Orego – twierdzenie podające warunek wystarczający na to, aby graf miał cykl Hamiltona. Zostało ono sformułowane w roku 1961 przez norweskiego matematyka Øysteina Orego. (pl) O Teorema de Ore é um resultado provado em 1960 pelo matemático norueguês Øystein Ore relacionado à Teoria dos grafos.Ele fornece uma condição suficiente para um grafo para ser Hamiltoniano, essencialmente, afirmando que um grafo com "quantidade de arestas suficiente" deve conter um ciclo de Hamilton. Especificamente, a teoria considera a soma dos graus dos pares de vértices não adjacentes: se cada um destes pares tem uma soma que, pelo menos, é equivalente ao número total de vértices no grafo, então o mesmo é Hamiltoniano. (pt) Теорема Оре — результат в теорії графів, доведений в 1960 році норвезьким математиком . Теорема дає достатню умову для того, щоб граф був гамільтоновим, по суті стверджуючи, що граф з «досить великим числом ребер» повинен містити гамільтонів цикл. Зокрема, теорема розглядає суми степенів пар несуміжних вершин - якщо кожна така пара в сумі дає як мінімум загальне число вершин графу, граф є гамільтоновим. (uk) 奥尔定理是挪威数学家奥斯丁·欧尔在1960年证明的图论定理。它为判断图为哈密顿图提供了一个充分条件，并且从本质上说明了如果一个图具有足够多的边，则它必然包含哈密顿环。具体来说，如果一个图中每一对非相邻顶点的度数和都大于等于顶点总数，那么该图为哈密顿图。 (zh) |
| rdfs:label | Teorema di Ore (it) オーレの定理 (ja) Ore's theorem (en) Twierdzenie Orego (pl) Teorema de Ore (pt) Теорема Оре (ru) Теорема Оре (uk) 奥尔定理 (zh) |
| owl:sameAs | freebase:Ore's theorem yago-res:Ore's theorem wikidata:Ore's theorem dbpedia-hu:Ore's theorem dbpedia-it:Ore's theorem dbpedia-ja:Ore's theorem dbpedia-pl:Ore's theorem dbpedia-pt:Ore's theorem dbpedia-ru:Ore's theorem dbpedia-sk:Ore's theorem dbpedia-uk:Ore's theorem dbpedia-zh:Ore's theorem https://global.dbpedia.org/id/28beq |
| prov:wasDerivedFrom | wikipedia-en:Ore's_theorem?oldid=1032016963&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Ore_theorem_example.svg wiki-commons:Special:FilePath/Ore_theorem_proof.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Ore's_theorem |
| is dbo:wikiPageRedirects of | dbr:Ore_theorem |
| is dbo:wikiPageWikiLink of | dbr:Cycle_(graph_theory) dbr:Pósa's_theorem dbr:Øystein_Ore dbr:Hamiltonian_path dbr:Extremal_graph_theory dbr:List_of_theorems dbr:Ore_theorem |
| is dbp:name of | dbr:Hamiltonian_path |
| is foaf:primaryTopic of | wikipedia-en:Ore's_theorem |
