Теорема Шнайдера

Теорема Шнайдера — это описание планарных графов в терминах порядковой размерности^[англ.] его частично упорядоченного множества инцидентности вершин^[англ.]. Теорема носит имя Вальтера Шнайдера, опубликовавшего её доказательство в 1989 году.

Частично упорядоченное множество инцидентных вершин ${\displaystyle P(G)}$ неориентированного графа G со множеством вершин и V и множеством рёбер E — это частично упорядоченное множество высоты 2, которое имеет ${\displaystyle V\cup E}$ в качестве элементов. В этом частично упорядоченном множестве имеется отношения порядка ${\displaystyle x<y}$, если x является вершиной, y является ребром и x является одним из концов дуги y.

Порядковая размерность частично упорядоченного множества — это наименьшее число полных порядков, пересечение которых даёт данное частично упорядоченное множество. Такое множество порядков называется реализатором частично упорядоченного множества. Теорема Шнайдера утверждает, что граф G является планарным тогда и только тогда, когда порядковая размерность ${\displaystyle P(G)}$ не превосходит трёх.

Расширения

Теорему обобщили Брайтвел и Троттер^[1][2] для получения точной оценки размерности частично упорядоченных множеств высоты три, образованных аналогичным образом из вершин рёбер и граней выпуклого многогранника, или, более обще, вложенного планарного графа. В обоих случаях порядковая размерность частично упорядоченное множество не превосходит четырёх. Однако результат не может быть обобщён на многомерные выпуклые многогранники, так как существуют четырёхмерные многогранники, решётки граней^[англ.] которых имеют неограниченную порядковую размерность.

Для абстрактных симплициальных комплексов^[англ.], порядковая размерность частично упорядоченного множества граней комплекса не превосходит 1 + d, где d — минимальная размерность евклидова пространства, в котором комплекс имеет геометрическую реализацию^[3][4].

Другие графы

Как заметил Шнайдер, частично упорядоченное множество инцидентности вершин графа G имеет порядковую размерность два тогда и только тогда, когда граф является путём или подграфом пути. Чтобы частично упорядоченное множество инцидентности вершин имело порядковую размерность два, необходимо, чтобы реализатор состоял из двух полных порядков, которые (ограниченные на вершины графа) обратны друг другу. Любые другие два порядка давали бы пересечение, которое включает отношение порядка между двумя вершинами, что недопустимо для частично упорядоченного множества инцидентности вершин. Для этих двух порядков на вершинах ребро между двумя соседними вершинами может быть включено в порядок путём размещения его непосредственно за последним из двух конечных вершин дуги, но никакие другие рёбра включить нельзя.

Если граф можно раскрасить в четыре цвета, то его частично упорядоченное множество инцидентности вершин имеет порядковую размерность, не превосходящую четырёх (Schnyder 1989).

Частично упорядоченное множество инцидентности вершин полного графа с n вершинами имеет порядковую размерность ${\displaystyle \Theta (\log \log n)}$^[5].

Примечания

Литература

Эта страница в последний раз была отредактирована 5 апреля 2021 в 07:03.