В теории графов , теорема Шнайдера в это характеристика плоских графов в терминах размерности порядка их падения ч.у.м. . Он назван в честь Уолтера Шнайдера, опубликовавшего свое доказательство в 1989 году .
Частота ч.у.м. Р ( О ) из неориентированного графа G с вершиной множество V и ребром множество Е является частично упорядоченным множеством из высоты 2 , который имеет V ∪ E , как ее элементы. В этом частичном порядке существует отношение порядка x < y, когда x - вершина, y - ребро, а x - одна из двух конечных точек y .
Порядковая размерность частичного порядка - это наименьшее количество полных порядков, пересечение которых является данным частичным порядком; такой набор порядков называется реализатором частичного порядка. Теорема Шнайдера утверждает, что граф G является плоским тогда и только тогда, когда размерность P ( G ) не превосходит трех.
Расширения
Эта теорема была обобщена Брайтвеллом и Троттером ( 1993 , 1997 ) до жесткой границы размерности трех частично упорядоченных множеств по высоте, образованных аналогичным образом из вершин, ребер и граней выпуклого многогранника или, в более общем смысле, вложенного плоского многогранника. График: в обоих случаях размерность упорядоченного набора не превышает четырех. Однако этот результат не может быть обобщен на выпуклые многогранники большей размерности , поскольку существуют четырехмерные многогранники, решетки граней которых имеют неограниченную размерность порядка.
В более общем смысле, для абстрактных симплициальных комплексов размерность порядка расположения граней комплекса не превышает 1 + d , где d - минимальная размерность евклидова пространства, в котором комплекс имеет геометрическую реализацию (Ossona de Mendez 1999 , 2002 ).
Другие графики
Как замечает Шнайдер, чум инцидентности графа G имеет размерность два, если и только если граф является путем или подграфом пути. Ибо, когда размерность порядка инцидентности poset равна двум, ее единственный возможный реализатор состоит из двух полных порядков, которые (при ограничении вершинами графа) являются обратными друг другу. Любые другие два порядка будут иметь пересечение, которое включает отношение порядка между двумя вершинами, что недопустимо для множеств инцидентности. Для этих двух порядков на вершинах ребро между последовательными вершинами можно включить в порядок, поместив его сразу после более поздней из двух конечных точек ребер, но никакие другие ребра не могут быть включены.
Если граф может быть раскрашен в четыре цвета, то его посет инцидентности имеет размерность порядка не более четырех ( Schnyder 1989 ).
ЧУМ инцидентности полного графа на n вершинах имеет размерность порядка( Спенсер, 1971 ).
Рекомендации
- Brightwell, G .; Trotter, WT (1993), "О порядке размерность выпуклых многогранников", SIAM журнал по дискретной математике , 6 (2): 230-245, DOI : 10,1137 / 0406018 , МР 1215230.
- Brightwell, G .; Trotter, WT (1997), "Размерность порядок плоских карт", SIAM Journal по дискретной математике , 10 (4): 515-528, CiteSeerX 10.1.1.127.1016 , DOI : 10,1137 / S0895480192238561 , МР 1477654.
- Оссона де Мендес, П. (1999), "Геометрическая реализация симплициальных комплексов", в Kratochvil, J. (ed.), Proc. Int. Symp. График Drawing (GD 1999) , Lecture Notes в области компьютерных наук, 1731 , Springer-Verlag, стр 323-332,. Дои : 10.1007 / 3-540-46648-7_33 , MR 1856785.
- Ossona де Мендес, P. (2002), "Реализация ч.у.м." (PDF) , журнал Graph алгоритмов и приложений , 6 (1): 149-153, DOI : 10,7155 / jgaa.00048 , MR 1898206.
- Шнайдера, W. (1989), "планарные графы и размеры посетом" Order , 5 (4): 323-343, DOI : 10.1007 / BF00353652 , MR 1010382 , S2CID 122785359.
- Спенсер, Дж (1971), "Минимальные скремблировании множество простых порядков", Acta Mathematica Academiae Scientiarum Hungaricae , 22 (3-4): 349-353, DOI : 10.1007 / bf01896428 , МР 0292722 , S2CID 123142998.