| dbo:abstract
|
- Das Minorentheorem gilt als einer der tiefgreifendsten Sätze der Graphentheorie. Neil Robertson und Paul Seymour bewiesen es in einer Serie von 20 Veröffentlichungen mit über 500 Seiten. Der Teil 1 “Excluding a Forest” erschien 1983, Teil 20 “Wagner’s Conjecture” mit dem Abschluss des Beweises erschien 2004. Inzwischen gibt es weitere Fortsetzungen, 2010 erschien Teil 23 “Nash-Williams’ immersion conjecture”. Der Beweis ist nicht konstruktiv und liefert auch einen Beweis der Wagnerschen Vermutung. (de)
- En mathématiques, et plus précisément en théorie des graphes, le théorème de Robertson–Seymour affirme qu'un certain classement partiel entre graphes non orientés possède des propriétés remarquables (c'est un bel ordre). Ce théorème a pour conséquence qu'il devient possible de caractériser de nombreuses familles de graphes par une liste finie de graphes qu’elles ne contiennent pas. Ce théorème généralise ainsi le théorème de Kuratowski, qui caractérise les graphes planaires comme ceux ne contenant pas deux graphes particuliers. Le théorème de Robertson–Seymour est également appelé le théorème des mineurs, car le classement partiel évoqué dans son énoncé est défini par la relation « être un mineur ». Le théorème équivaut ainsi à dire que toute famille F de graphes fermée, c'est-à-dire telle que les mineurs des graphes de F appartiennent aussi à F, peut être caractérisée par un ensemble fini de « mineurs exclus ». Connu, avant qu'il soit démontré, sous le nom de conjecture de Wagner, ce théorème, démontré en 2004 par Neil Robertson et Paul Seymour, est considéré généralement comme un des résultats les plus importants de la théorie des graphes. Il a une démonstration extrêmement complexe et délicate, dont la publication, comportant plus de cinq cents pages, s'étale de 1983 à 2004 dans vingt articles de la revue Journal of Combinatorial Theory. Le théorème n'est pas constructif (on ne connait d'ailleurs les listes explicites de mineurs exclus que dans très peu de cas), mais Robertson et Seymour ont montré qu'il a d'importantes conséquences en théorie de la complexité, car il garantit l'existence d'algorithmes rapides pour de nombreux problèmes de décision. (fr)
- In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors, in the same way that Wagner's theorem characterizes the planar graphs as being the graphs that do not have the complete graph K5 or the complete bipartite graph K3,3 as minors. The Robertson–Seymour theorem is named after mathematicians Neil Robertson and Paul D. Seymour, who proved it in a series of twenty papers spanning over 500 pages from 1983 to 2004. Before its proof, the statement of the theorem was known as Wagner's conjecture after the German mathematician Klaus Wagner, although Wagner said he never conjectured it. A weaker result for trees is implied by Kruskal's tree theorem, which was conjectured in 1937 by Andrew Vázsonyi and proved in 1960 independently by Joseph Kruskal and S. Tarkowski. (en)
- In teoria dei grafi il teorema di Robertson-Seymour costituisce unageneralizzazione di ampia portata del considerato comeaffermazione che e sono "minori proibiti"per i grafi planari. (it)
- Na teoria dos grafos, o teorema de Robertson–Seymour (também chamado teorema menor dos grafos) estabelece que os grafos não direcionados, parcialmente ordenados pelo relacionamento do , formam um . (pt)
- Теорема Робертсона — Сеймура (также называемая теоремой о минорах графа ) утверждает, что любое семейство графов, замкнутое относительно операций удаления и стягивания рёбер, может быть определено конечным набором запрещённых графов. Например, множество планарных графов замкнуто по операциям удаления и стягивания рёбер; запрещёнными графами в этом случае являются полный граф K5 и полный двудольный граф K3,3. Последнее утверждение называется теоремой Вагнера и тесно связано с теоремой Понтрягина — Куратовского. Теорема широко известна элементарностью формулировки при отсутствии простого доказательства. Она носит имя Нила Робертсона и Пола Сеймура, которые доказали её в серии из двадцати статей общим объёмом в 500 страниц, вышедших с 1983 по 2004 годы. До доказательства утверждение теоремы было известно как гипотеза Вагнера, хотя сам Вагнер утверждал, что он никогда не высказывал этой гипотезы. Более слабое утверждение для деревьев следует из теоремы Краскала о деревьях. Утверждение было высказано в виде гипотезы в 1937 году венгерским математиком Эндрю Важоньи и доказано в 1960 независимо Джозефом Краскалом и С. Тарковским. (ru)
- Теорема Робертсона — Сеймура (також звана теоремою про мінори графа) стверджує, що будь-яке сімейство графів, замкнуте відносно операцій видалення і стягування ребер, можна визначити скінченним набором заборонених графів. Наприклад, множина планарних графів замкнута за операціями видалення і стягування ребер; забороненими графами в цьому випадку є повний граф K5 і повний двочастковий граф K3,3. Останнє твердження називається теоремою Вагнера і тісно пов'язане з теоремою Понтрягіна — Куратовського. Теорема широко відома елементарністю формулювання за відсутності простого доведення. Вона носить ім'я і , які довели її в серії з двадцяти статей загальним обсягом 500 сторінок, що вийшли від 1983 до 2004 року. До доведення твердження теорема була відомою як гіпотеза Вагнера, хоча сам стверджував, що він ніколи не висловлював цієї гіпотези. Слабше твердження для дерев випливає з . Твердження 1937 року висловив у вигляді гіпотези угорський математик і довели 1960 року незалежно і С. Тарковським. (uk)
|
| rdfs:comment
|
- Das Minorentheorem gilt als einer der tiefgreifendsten Sätze der Graphentheorie. Neil Robertson und Paul Seymour bewiesen es in einer Serie von 20 Veröffentlichungen mit über 500 Seiten. Der Teil 1 “Excluding a Forest” erschien 1983, Teil 20 “Wagner’s Conjecture” mit dem Abschluss des Beweises erschien 2004. Inzwischen gibt es weitere Fortsetzungen, 2010 erschien Teil 23 “Nash-Williams’ immersion conjecture”. Der Beweis ist nicht konstruktiv und liefert auch einen Beweis der Wagnerschen Vermutung. (de)
- In teoria dei grafi il teorema di Robertson-Seymour costituisce unageneralizzazione di ampia portata del considerato comeaffermazione che e sono "minori proibiti"per i grafi planari. (it)
- Na teoria dos grafos, o teorema de Robertson–Seymour (também chamado teorema menor dos grafos) estabelece que os grafos não direcionados, parcialmente ordenados pelo relacionamento do , formam um . (pt)
- En mathématiques, et plus précisément en théorie des graphes, le théorème de Robertson–Seymour affirme qu'un certain classement partiel entre graphes non orientés possède des propriétés remarquables (c'est un bel ordre). Ce théorème a pour conséquence qu'il devient possible de caractériser de nombreuses familles de graphes par une liste finie de graphes qu’elles ne contiennent pas. Ce théorème généralise ainsi le théorème de Kuratowski, qui caractérise les graphes planaires comme ceux ne contenant pas deux graphes particuliers. (fr)
- In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors, in the same way that Wagner's theorem characterizes the planar graphs as being the graphs that do not have the complete graph K5 or the complete bipartite graph K3,3 as minors. (en)
- Теорема Робертсона — Сеймура (также называемая теоремой о минорах графа ) утверждает, что любое семейство графов, замкнутое относительно операций удаления и стягивания рёбер, может быть определено конечным набором запрещённых графов. Например, множество планарных графов замкнуто по операциям удаления и стягивания рёбер; запрещёнными графами в этом случае являются полный граф K5 и полный двудольный граф K3,3. Последнее утверждение называется теоремой Вагнера и тесно связано с теоремой Понтрягина — Куратовского. (ru)
- Теорема Робертсона — Сеймура (також звана теоремою про мінори графа) стверджує, що будь-яке сімейство графів, замкнуте відносно операцій видалення і стягування ребер, можна визначити скінченним набором заборонених графів. Наприклад, множина планарних графів замкнута за операціями видалення і стягування ребер; забороненими графами в цьому випадку є повний граф K5 і повний двочастковий граф K3,3. Останнє твердження називається теоремою Вагнера і тісно пов'язане з теоремою Понтрягіна — Куратовського. (uk)
|
