Tait's conjecture (original) (raw)
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 ».
| Property | Value |
|---|---|
| dbo: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) |
| dbo:thumbnail | wiki-commons:Special:FilePath/TutteFrag.png?width=300 |
| dbo:wikiPageExternalLink | http://jlms.oxfordjournals.org/cgi/reprint/s1-21/2/98.pdf%7Cjournal=Journal http://www.math.niu.edu/%7Erusin/known-math/97/tutte |
| dbo:wikiPageID | 52435 (xsd:integer) |
| dbo:wikiPageLength | 5136 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1025920800 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Barnette's_conjecture dbr:Rhombic_dodecahedron dbr:Cubic_graph dbc:Planar_graphs dbr:K-vertex-connected_graph dbc:Disproved_conjectures dbr:Edge_coloring dbc:Hamiltonian_paths_and_cycles dbr:Four_color_theorem dbr:Pentagonal_prism dbr:Bipartite_graph dbr:Planar_graph dbr:Grinberg's_theorem dbr:Graph_connectivity dbr:Vertex_(geometry) dbr:Philosophical_Magazine dbr:Tutte_graph dbr:Polyhedral_graph dbr:Steinitz'_theorem dbr:Hamiltonian_cycle dbr:Bridgeless_graph dbr:File:PlanarNonHamil.png dbr:File:TutteFrag.png |
| dbp:authorlink | W. T. Tutte (en) P. G. Tait (en) |
| dbp:first | P. G. (en) W. T. (en) |
| dbp:last | Tait (en) Tutte (en) |
| dbp:title | Tait's Hamiltonian Graph Conjecture (en) |
| dbp:urlname | TaitsHamiltonianGraphConjecture (en) |
| dbp:wikiPageUsesTemplate | dbt:About dbt:Citation dbt:Harvtxt dbt:Mathworld dbt:Reflist dbt:Short_description dbt:Harvs dbt:Disproved_conjectures |
| dbp:year | 1884 (xsd:integer) 1946 (xsd:integer) |
| dct:subject | dbc:Planar_graphs dbc:Disproved_conjectures dbc:Hamiltonian_paths_and_cycles |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Action100037396 yago:Cognition100023271 yago:Communication100033020 yago:Concept105835747 yago:Content105809192 yago:Course100038262 yago:Event100029378 yago:Graph107000195 yago:Hypothesis105888929 yago:Idea105833840 yago:PsychologicalFeature100023100 yago:WikicatHamiltonianPathsAndCycles yago:YagoPermanentlyLocatedEntity yago:Speculation105891783 yago:VisualCommunication106873252 yago:Way100415676 yago:WikicatDisprovedConjectures yago:WikicatPlanarGraphs |
| 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) |
| rdfs:label | Conjecture de Tait (fr) Tait's conjecture (en) Гипотеза Тэйта (теория графов) (ru) Гіпотеза Тета (теорія графів) (uk) |
| owl:sameAs | freebase:Tait's conjecture yago-res:Tait's conjecture wikidata:Tait's conjecture dbpedia-fr:Tait's conjecture dbpedia-hu:Tait's conjecture dbpedia-ru:Tait's conjecture dbpedia-uk:Tait's conjecture https://global.dbpedia.org/id/4vH5s |
| prov:wasDerivedFrom | wikipedia-en:Tait's_conjecture?oldid=1025920800&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/PlanarNonHamil.png wiki-commons:Special:FilePath/TutteFrag.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Tait's_conjecture |
| is dbo:wikiPageRedirects of | dbr:Tutte's_fragment dbr:Tutte_fragment dbr:Tait_conjecture |
| is dbo:wikiPageWikiLink of | dbr:List_of_conjectures dbr:Barnette's_conjecture dbr:List_of_graph_theory_topics dbr:Peter_Tait_(physicist) dbr:Cubic_graph dbr:W._T._Tutte dbr:Hamiltonian_path dbr:Counterexample dbr:Herschel_graph dbr:Grinberg's_theorem dbr:Walther_graph dbr:Tutte_graph dbr:Polyhedral_graph dbr:Table_of_simple_cubic_graphs dbr:Tutte's_fragment dbr:Tutte_fragment dbr:Tait_conjecture |
| is foaf:primaryTopic of | wikipedia-en:Tait's_conjecture |
