In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle (along the edges) through all its vertices". It was proposed by P. G. Tait and disproved by W. T. Tutte, who constructed a counterexample with 25 faces, 69 edges and 46 vertices. Several smaller counterexamples, with 21 faces, 57 edges and 38 vertices, were later proved minimal by .The condition that the graph be 3-regular is necessary due to polyhedra such as the rhombic dodecahedron, which forms a bipartite graph with six degree-four vertices on one side and eight degree-three vertices on the other side; because any Hamiltonian cycle would have to alternate between the two sides of the bipartition, but they have unequal numbers of vertices, the rhombic dodecahedron is not Ham
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Conjecture de Tait (fr)
- Tait's conjecture (en)
- Гипотеза Тэйта (теория графов) (ru)
- Гіпотеза Тета (теорія графів) (uk)
|
| rdfs:comment
| - En mathématiques, et plus particulièrement en théorie des graphes, la conjecture de Tait affirme que « tout graphe cubique planaire 3-connexe possède un cycle hamiltonien ». (fr)
- In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle (along the edges) through all its vertices". It was proposed by P. G. Tait and disproved by W. T. Tutte, who constructed a counterexample with 25 faces, 69 edges and 46 vertices. Several smaller counterexamples, with 21 faces, 57 edges and 38 vertices, were later proved minimal by .The condition that the graph be 3-regular is necessary due to polyhedra such as the rhombic dodecahedron, which forms a bipartite graph with six degree-four vertices on one side and eight degree-three vertices on the other side; because any Hamiltonian cycle would have to alternate between the two sides of the bipartition, but they have unequal numbers of vertices, the rhombic dodecahedron is not Ham (en)
- Гипотеза Тэйта — опровергнутая математическая гипотеза о том, что любой 3-связный планарный кубический граф имеет гамильтонов цикл, проходящий через все его вершины. Высказана в 1884 году Питером Тэйтом, опровергнута в 1946 году Уильямом Таттом, который построил контрпример с 25 гранями, 69 рёбрами и 46 вершинами — граф Татта. Позднее, в 1988 году, найден контрпример с 21 гранями, 57 рёбрами и 38 вершинами и доказано, что этот граф минимален. (ru)
- Гіпотеза Тета — спростована математична гіпотеза про те, що будь-який 3-зв'язний планарний кубічний граф має гамільтонів цикл, що проходить через усі його вершини . Висловлена в Пітером Тетом , спростована в Вільямом Таттом , який побудував контрприклад з 25 гранями, 69 ребрами і 46 вершинами — граф Татта. Пізніше, 1988 року, знайдено контрприклад з 21 гранню, 57 ребрами і 38 вершинами і доведено, що цей граф мінімальний. (uk)
|
| foaf:depiction
| |
| dct:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| authorlink
| - W. T. Tutte (en)
- P. G. Tait (en)
|
| first
| |
| last
| |
| title
| - Tait's Hamiltonian Graph Conjecture (en)
|
| urlname
| - TaitsHamiltonianGraphConjecture (en)
|
| year
| |
| has abstract
| - En mathématiques, et plus particulièrement en théorie des graphes, la conjecture de Tait affirme que « tout graphe cubique planaire 3-connexe possède un cycle hamiltonien ». (fr)
- In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle (along the edges) through all its vertices". It was proposed by P. G. Tait and disproved by W. T. Tutte, who constructed a counterexample with 25 faces, 69 edges and 46 vertices. Several smaller counterexamples, with 21 faces, 57 edges and 38 vertices, were later proved minimal by .The condition that the graph be 3-regular is necessary due to polyhedra such as the rhombic dodecahedron, which forms a bipartite graph with six degree-four vertices on one side and eight degree-three vertices on the other side; because any Hamiltonian cycle would have to alternate between the two sides of the bipartition, but they have unequal numbers of vertices, the rhombic dodecahedron is not Hamiltonian. The conjecture was significant, because if true, it would have implied the four color theorem: as Tait described, the four-color problem is equivalent to the problem of finding 3-edge-colorings of bridgeless cubic planar graphs. In a Hamiltonian cubic planar graph, such an edge coloring is easy to find: use two colors alternately on the cycle, and a third color for all remaining edges. Alternatively, a 4-coloring of the faces of a Hamiltonian cubic planar graph may be constructed directly, using two colors for the faces inside the cycle and two more colors for the faces outside. (en)
- Гипотеза Тэйта — опровергнутая математическая гипотеза о том, что любой 3-связный планарный кубический граф имеет гамильтонов цикл, проходящий через все его вершины. Высказана в 1884 году Питером Тэйтом, опровергнута в 1946 году Уильямом Таттом, который построил контрпример с 25 гранями, 69 рёбрами и 46 вершинами — граф Татта. Позднее, в 1988 году, найден контрпример с 21 гранями, 57 рёбрами и 38 вершинами и доказано, что этот граф минимален. Условие 3-регулярности (3-регулярные графы называются кубическими) необходимо, поскольку существуют многогранники, такие как ромбододекаэдр. Ромбододекаэдр образует двудольный граф и любой гамильтонов цикл в этом графе должен поочерёдно менять доли (стороны) графа, так что число вершин в долях должно быть равно, однако граф имеет шесть вершин степени 4 на одной стороне и восемь вершин степени 3 на другой. Если бы гипотеза была верна, то из неё следовало бы простое решение проблемы четырёх красок. Согласно Тэйту, задача четырёх красок эквивалентна задаче поиска рёберной 3-раскраски кубических планарных графов без мостов. В гамильтоновом кубическом планарном графе такую раскраску рёбер легко найти — поочерёдно используем два цвета для раскраски рёбер вдоль гамильтонова цикла, а третьим цветом выкрасим оставшиеся рёбра. Альтернативно можно построить раскраску в четыре цвета граней гамильтонова кубического планарного графа прямо, если использовать два цвета для раскраски граней внутри цикла и два цвета для граней снаружи. (ru)
- Гіпотеза Тета — спростована математична гіпотеза про те, що будь-який 3-зв'язний планарний кубічний граф має гамільтонів цикл, що проходить через усі його вершини . Висловлена в Пітером Тетом , спростована в Вільямом Таттом , який побудував контрприклад з 25 гранями, 69 ребрами і 46 вершинами — граф Татта. Пізніше, 1988 року, знайдено контрприклад з 21 гранню, 57 ребрами і 38 вершинами і доведено, що цей граф мінімальний. Умова 3-регулярності (3-регулярні графи називаються кубічними) необхідна, оскільки існують багатогранники, такі як ромбододекаедр. Ромбододекаедр утворює двочастковий граф і будь-який гамільтонів цикл у цьому графі має почергово змінювати частки (сторони) графа, так що число вершин в частках має бути однаковим, проте граф має шість вершин степеня 4 на одному боці і вісім вершин степеня 3 на іншому. Якби гіпотеза була правильна, то з неї випливав би простий розв'язок задачі чотирьох фарб. Згідно з Тетом, задача чотирьох фарб еквівалентна задачі пошуку реберної 3-розмальовки кубічних планарних графів без мостів. У гамільтоновому кубічному планарному графі таку розмальовку ребер легко знайти — по черзі використовуємо два кольори для розмальовування ребер уздовж гамільтонового циклу, а третім кольором пофарбуємо решту ребер. Альтернативно можна побудувати розмальовку в чотири кольори граней гамільтонового кубічного планарного графа прямо, якщо використовувати два кольори для розмальовування граней всередині циклу і два кольори для граней зовні. (uk)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
