| The Robertson-Seymour theorem has an important consequence in computational complexity, due to the proof by Robertson and Seymour that, for each fixed graph G, there is a polynomial time algorithm for testing whether larger graphs have G as a minor. | Теорема Робертсона - Сеймура имеет важное следствие в теории вычислительной сложности, поскольку Робертсон и Сеймур доказали, что для каждого фиксированного графа G существует алгоритм полиномиального времени для проверки, имеет ли больший граф G в качестве минора. |
| The Robertson-Seymour theorem proves that, for the particular case of graph minors, a family that is closed under minors always has a finite obstruction set. | Теорема Робертсона - Сеймура доказывает, что в определённых случаях миноров графа, семейство, замкнутое по минорам, всегда имеет конечное препятствующее множество. |
| Although the Robertson-Seymour theorem extends these results to arbitrary minor-closed graph families, it is not a complete substitute for these results, because it does not provide an explicit description of the obstruction set for any family. | Хотя теорема Робертсона - Сеймура распространяет эти результаты на произвольные замкнутые по минорам семейства графов, она не подменяет эти результаты, поскольку не даёт явного описания препятствующего множества для любого семейства. |
| 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. | Теорема Робертсона - Сеймура названа именами математиков Нейла Робертсона и Пола Сеймура, которые доказали её в серии из двадцати статей общим объёмом в 500 страниц, вышедших с 1983 по 2004 годы. |
| Notably, Seymour's decomposition theorem characterizes the regular matroids (the matroids representable by totally unimodular matrices) as the 3-sums of graphic matroids (the matroids representing spanning trees in a graph), cographic matroids, and a certain 10-element matroid. | Теорема разложения Сеймура описывает регулярные матроиды (матроиды, представляющие вполне унимодулярные матрицы) как З-суммы графических матроидов (матроиды, представляющие остовные деревья), кографические матроиды и некоторые 10-элементные матроиды. |
| The theorem is stated in the seventeenth of a series of 23 papers by Neil Robertson and Paul Seymour. | Теорема была сформулирована в семнадцати статьях из серии из 23 статей Нейла Робертсона и Пола Сеймура. |
| The proof is based on a theorem of Robertson and Seymour that the families of graphs with unbounded treewidth have arbitrarily large grid minors. | Доказательство опирается на теорему Робертсона и Сеймура о том, что семейства графов с неограниченной древесной шириной имеют произвольно большие миноры-решётки. |
| Some examples of finite obstruction sets were already known for specific classes of graphs before the Robertson-Seymour theorem was proved. | Некоторые примеры конечных препятствующих множеств были уже известны для некоторых классов ещё до доказательства теоремы Робертсона - Сеймура. |
| Therefore, according to the Robertson-Seymour theorem, they can be characterized by a finite number of forbidden minors. | Таким образом, согласно теореме Робертсона - Сеймура, они могут быть охарактеризованы конечным числом запрещённых миноров. |
| This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson-Seymour theorem. | Теорема была одной из наиболее ранних работ в теории миноров графа и её можно рассматривать как предшественницу теоремы Робертсона - Сеймура. |
| Forbidden minors have also been studied for matroid branchwidth, despite the lack of a full analogue to the Robertson-Seymour theorem in this case. | Запрещённые миноры изучаются также для ширины ветвления матроида, вопреки отсутствия полной аналогии теоремы Робертсона - Сеймура в этом случае. |
| Therefore, by the Robertson-Seymour theorem, the linklessly embeddable graphs have a forbidden graph characterization as the graphs that do not contain any of a finite set of minors. | Таким образом, по теореме Робертсона - Сеймура, имеющие незацепленное вложение графы имеют характеризацию запрещёнными графами как графы, не содержащие любого из конечного набора миноров. |
| According to the Robertson-Seymour theorem, there exists a finite set H of minimal elements in S. These minimal elements form a forbidden graph characterization of F: the graphs in F are exactly the graphs that do not have any graph in H as a minor. | Согласно теореме Робертсона - Сеймура существует конечное множество Н минимальных элементов в S. Эти минимальные элементы образуют характеризацию запрещёнными графами множества F - графы из F являются в точности теми графами, которые не имеют какого-либо графа из H в качестве минора. |
| The existence of forbidden minor characterizations for all minor-closed graph families is an equivalent way of stating the Robertson-Seymour theorem. | Существование характеризаций запрещёнными минорами для всех минорно замкнутых семейств графов является эквивалентной формулировкой теоремы Робертсона - Сеймура. |
| The Robertson-Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions. | Из теоремы Роберсона - Сеймура следует, что аналоги характеризации запрещёнными минорами существуют для любого свойства графов, которые сохраняются при удалениях и стягивании рёбер. |
| Robertson and Seymour conjectured that the matroids representable over any particular finite field are well-quasi-ordered, analogously to the Robertson-Seymour theorem for graphs, but so far this has been proven only for the matroids of bounded branchwidth. | Робертсон и Сеймур высказали предположение, что матроиды, представимые любым конкретным конечным полем, вполне квазиупорядоченны, что является аналогией Теорема Робертсона - Сеймура для графов, но гипотеза доказана только для матроидов с ограниченной шириной ветвления. |
| For any fixed constant k, the partial k-trees are closed under the operation of graph minors, and therefore, by the Robertson-Seymour theorem, this family can be characterized in terms of a finite set of forbidden minors. | Для любой фиксированной константы к частичные к деревья замкнуты относительно операции взятия миноров графов, а потому по теореме Робертсона - Сеймура, такое семейство графов может быть описано конечным набором запрещённых миноров. |
| Two nice theorems in this direction are Jaeger's 4-flow theorem (every 4-edge-connected graph has a nowhere-zero 4-flow) and Seymour's 6-flow theorem (every bridgeless graph has a nowhere-zero 6-flow). | Две элегантные теоремы в этом направлении - теорема Джагера о 4-потоке (любой рёберно 4-связный граф имеет нигде не нулевой 4-поток) и теорема Сеймура о 6-потоке (любой граф без мостов имеет нигде не нулевой 6-поток). |