| http://dbpedia.org/ontology/abstract
|
In graph theory, the Heawood conjecture or … In graph theory, the Heawood conjecture or Ringel–Youngs theorem gives a lower bound for the number of colors that are necessary for graph coloring on a surface of a given genus. For surfaces of genus 0, 1, 2, 3, 4, 5, 6, 7, ..., the required number of colors is 4, 7, 8, 9, 10, 11, 12, 12, .... OEIS: , the chromatic number or Heawood number. The conjecture was formulated in 1890 by Percy John Heawood and proven in 1968 by Gerhard Ringel and Ted Youngs. One case, the non-orientable Klein bottle, proved an exception to the general formula. An entirely different approach was needed for the much older problem of finding the number of colors needed for the plane or sphere, solved in 1976 as the four color theorem by Haken and Appel. On the sphere the lower bound is easy, whereas for higher genera the upper bound is easy and was proved in Heawood's original short paper that contained the conjecture. In other words, Ringel, Youngs and others had to construct extreme examples for every genus g = 1,2,3,.... If g = 12s + k, the genera fall into 12 cases according as k = 0,1,2,3,4,5,6,7,8,9,10,11. To simplify, suppose that case k has been established if only a finite number of g's of the form 12s + k are in doubt. Then the years in which the twelve cases were settled and by whom are the following:
* 1954, Ringel: case 5
* 1961, Ringel: cases 3,7,10
* 1963, Terry, Welch, Youngs: cases 0,4
* 1964, Gustin, Youngs: case 1
* 1965, Gustin: case 9
* 1966, Youngs: case 6
* 1967, Ringel, Youngs: cases 2,8,11 The last seven sporadic exceptions were settled as follows:
* 1967, Mayer: cases 18, 20, 23
* 1968, Ringel, Youngs: cases 30, 35, 47, 59, and the conjecture was proved.35, 47, 59, and the conjecture was proved.
, En théorie des graphes, la conjecture de H … En théorie des graphes, la conjecture de Heawood ou, maintenant qu'elle est démontrée le théorème de Ringel–Youngs donne un minorant pour le nombre de couleurs nécessaires pour colorer une surface de genre donné. Pour les surfaces de genre 0, 1, 2, 3, 4, 5, 6, 7,... qui sont la sphère et le tore à 1, 2, 3, 4, 5, 6, 7... trous, le nombre de couleurs requises est 4, 7, 8, 9, 10, 11, 12, 12, .... (c'est la suite ), le nombre chromatique ou nombre de Heawood. Pour la sphère, de genre 0, le nombre 4 est l'énoncé de théorème des quatre couleurs. La conjecture a été formulée en 1890 par Percy John Heawood et définitivement démontrée en 1968 par Gerhard Ringel et John William Theodore Youngs. Un cas, la bouteille de Klein, constitue une exception a la formule générale. Une approche totalement différente a permis de résoudre le problème bien plus ancien du nombre de couleurs nécessaires pour le plan ou la sphère, sa solution en 1976 est le théorème des quatre couleurs démontré par Wolfgang Haken et Kenneth Appel. Sur la sphère, la borne inférieure est facile, alors que pour les genres supérieurs, c'est la majoration qui est facile ; elle a été démontrée par Heawood dans son article original qui contient la conjecture.ticle original qui contient la conjecture.
, Гипотеза Хивуда, или теорема Рингеля — Янг … Гипотеза Хивуда, или теорема Рингеля — Янгса даёт нижнюю границу для числа цветов, которые необходимы для раскраски графа на поверхности с заданным родом. Эта граница называется хроматическим числом поверхности или числом Хивуда. Для поверхностей рода 0, 1, 2, 3, 4, 5, 6, 7, ..., требуемое число цветов равно 4, 7, 8, 9, 10, 11, 12, 12, .... ,. Гипотеза была сформулирована в 1890 году Перси Джоном Хивудом и доказана в 1968 Герхардом Рингелем и . Один случай, а именно, неориентированная Бутылка Клейна, является исключением в общей формуле. Совершенно другой подход был нужен для куда более старой задачи нахождения числа цветов, необходимых для плоскости или сферы, и решённой в 1976 и (теорема о четырёх красках). На сфере нижнюю границу найти легко, а на поверхностях более высокого рода легко установить верхнюю границу и она была доказана в оригинальной короткой статье Хивуда, содержащей формулировку гипотезы. Другими словами, для доказательства теоремы Рингель, Янгс и другие должны были сконструировать экстремальные примеры для каждого рода поверхности g = 1,2,3,.... Если g = 12s + k, род поверхности распадается на 12 случаев согласно остатку k = 0,1,2,3,4,5,6,7,8,9,10,11. Годы, в которые были решены двенадцать случаев и кто их решил:
* 1954, Рингель: случай 5
* 1961, Рингель: случаи 3,7,10
* 1963, Терри, Велч, : случаи 0,4
* 1964, Густин, Янгс: случай 1
* 1965, Густин: случай 9
* 1966, Янгс: случай 6
* 1967, Рингель, Янгс: случаи 2,8,11 Последние семь отдельных исключений были решены:
* 1967, Майер: случаи 18, 20, 23
* 1968, Рингель, Янгс: случаи 30, 35, 47, 59 и гипотеза была доказана.и 30, 35, 47, 59 и гипотеза была доказана.
, En teoria de grafs, la conjectura de Heawo … En teoria de grafs, la conjectura de Heawood o el teorema de Ringel-Youngs estableix una cota inferior per al nombre de colors que són necessaris per acolorir un graf en una superfície d'un determinat. Va ser formulada el 1890 per John Percy Heawood i demostrada el 1968 per Gerhard Ringel i . Un dels casos, l'ampolla de Klein no orientable, va resultar ser una excepció a la fórmula general. Es va necessitar un enfocament totalment diferent per al problema de trobar el nombre de colors necessaris per al pla, o de forma equivalent, l'esfera, resolt el 1976 com el teorema dels quatre colors per i . En l'esfera la cota inferior és fàcil, mentre que gèneres més grans la cota superior és fàcil i va ser demostrada en el breu article original de Heawood que contenia la conjectura.nal de Heawood que contenia la conjectura.
, 曲面染色是图论中的问题，是继四色定理之后的问题延续，奇怪的是问题的解决反而在四色定理之前，这个与庞加莱猜想有相似的情况（高维反而最先解决，低维反而更加困难）。
, Der Satz von Ringel-Youngs, auch Heawood-V … Der Satz von Ringel-Youngs, auch Heawood-Vermutung genannt, gibt in der Graphentheorie eine Formel für die minimale Anzahl der Farben, die für die Färbung einer beliebigen Fläche nötig ist abhängig vom topologischen Geschlecht der Fläche (wobei hier ein Geschlecht betrachtet wird). Percy Heawood hatte die Formel 1890 angegeben, bewiesen, dass diese Formel für Geschlecht eine obere Schranke darstellt und die Vermutung formuliert, dass sie auch eine untere Schranke ist. Das heißt, er bewies, dass jede Landkarte auf den entsprechenden Flächen mit der durch die Formel angegebenen Anzahl von Farben färbbar ist, und vermutete, dass man im Allgemeinen nicht mit weniger Farben auskommt. 1968 wurde das von Gerhard Ringel und J. W. T. Youngs bewiesen, mit Ausnahme der Fälle der Kleinschen Flasche und der Kugel. Der Fall der Kugel (Geschlecht g=0) entspricht dem schwierigen Fall des Vier-Farben-Satzes (wobei hier das Problem darin liegt die obere Schranke zu beweisen, für die untere Schranke kann man eine einfache Landkarte angeben, die nur mit vier Farben färbbar ist) und wurde erst 1977 bewiesen, die Formel ist aber auch hier gültig. Die Kleinsche Flasche blieb eine Ausnahme für die Gültigkeit der Formel.ne Ausnahme für die Gültigkeit der Formel.
|
| rdfs:comment |
曲面染色是图论中的问题，是继四色定理之后的问题延续，奇怪的是问题的解决反而在四色定理之前，这个与庞加莱猜想有相似的情况（高维反而最先解决，低维反而更加困难）。
, Der Satz von Ringel-Youngs, auch Heawood-V … Der Satz von Ringel-Youngs, auch Heawood-Vermutung genannt, gibt in der Graphentheorie eine Formel für die minimale Anzahl der Farben, die für die Färbung einer beliebigen Fläche nötig ist abhängig vom topologischen Geschlecht der Fläche (wobei hier ein Geschlecht betrachtet wird).obei hier ein Geschlecht betrachtet wird).
, Гипотеза Хивуда, или теорема Рингеля — Янг … Гипотеза Хивуда, или теорема Рингеля — Янгса даёт нижнюю границу для числа цветов, которые необходимы для раскраски графа на поверхности с заданным родом. Эта граница называется хроматическим числом поверхности или числом Хивуда. Для поверхностей рода 0, 1, 2, 3, 4, 5, 6, 7, ..., требуемое число цветов равно 4, 7, 8, 9, 10, 11, 12, 12, .... ,.
* 1954, Рингель: случай 5
* 1961, Рингель: случаи 3,7,10
* 1963, Терри, Велч, : случаи 0,4
* 1964, Густин, Янгс: случай 1
* 1965, Густин: случай 9
* 1966, Янгс: случай 6
* 1967, Рингель, Янгс: случаи 2,8,11ай 6
* 1967, Рингель, Янгс: случаи 2,8,11
, En teoria de grafs, la conjectura de Heawo … En teoria de grafs, la conjectura de Heawood o el teorema de Ringel-Youngs estableix una cota inferior per al nombre de colors que són necessaris per acolorir un graf en una superfície d'un determinat. Va ser formulada el 1890 per John Percy Heawood i demostrada el 1968 per Gerhard Ringel i . Un dels casos, l'ampolla de Klein no orientable, va resultar ser una excepció a la fórmula general. Es va necessitar un enfocament totalment diferent per al problema de trobar el nombre de colors necessaris per al pla, o de forma equivalent, l'esfera, resolt el 1976 com el teorema dels quatre colors per i . En l'esfera la cota inferior és fàcil, mentre que gèneres més grans la cota superior és fàcil i va ser demostrada en el breu article original de Heawood que contenia la conjectura.nal de Heawood que contenia la conjectura.
, En théorie des graphes, la conjecture de H … En théorie des graphes, la conjecture de Heawood ou, maintenant qu'elle est démontrée le théorème de Ringel–Youngs donne un minorant pour le nombre de couleurs nécessaires pour colorer une surface de genre donné. Pour les surfaces de genre 0, 1, 2, 3, 4, 5, 6, 7,... qui sont la sphère et le tore à 1, 2, 3, 4, 5, 6, 7... trous, le nombre de couleurs requises est 4, 7, 8, 9, 10, 11, 12, 12, .... (c'est la suite ), le nombre chromatique ou nombre de Heawood. Pour la sphère, de genre 0, le nombre 4 est l'énoncé de théorème des quatre couleurs. l'énoncé de théorème des quatre couleurs.
, In graph theory, the Heawood conjecture or … In graph theory, the Heawood conjecture or Ringel–Youngs theorem gives a lower bound for the number of colors that are necessary for graph coloring on a surface of a given genus. For surfaces of genus 0, 1, 2, 3, 4, 5, 6, 7, ..., the required number of colors is 4, 7, 8, 9, 10, 11, 12, 12, .... OEIS: , the chromatic number or Heawood number.
* 1954, Ringel: case 5
* 1961, Ringel: cases 3,7,10
* 1963, Terry, Welch, Youngs: cases 0,4
* 1964, Gustin, Youngs: case 1
* 1965, Gustin: case 9
* 1966, Youngs: case 6
* 1967, Ringel, Youngs: cases 2,8,11se 6
* 1967, Ringel, Youngs: cases 2,8,11
|
