Двумерность: различия между версиями

Таким образом, двумерность со сжатием не определена для графов, свободных от H-миноров (или графов общего вида).

Примерами двумерных параметров могут служить количество вершин, диаметр и размеры различных структур – таких как [[разрывающее множество вершин]], [[вершинное покрытие]], минимальное [[паросочетание]] с максимальным весом, [[покрытие гранями]], серия параметров для удаления вершин, [[доминирующее множество]], доминирующее множество ребер, R-доминирующее множество, [[связное доминирующее множество]], связное доминирующее множество ребер, связное R-доминирующее множество, невзвешенная [[метрическая задача коммивояжера]] (обход графа с посещением всех вершин) и [[хордальное дополнение]] (заполнение). Например, разрывающее множество вершин является <math>\Omega (r^2) \;</math>-минорно-двумерным (и, следовательно, сжато-двумерным), поскольку: (1) удаление или сжатие ребра сохраняет существующие разрывающие множества вершин; (2) любая вершина разрывающего множества вершин разрушает не более четырех квадратов решетки <math>r \times r \;</math>, а поскольку в ней имеется <math>(r — 1)^2 \;</math> квадратов, любое разрывающее множество вершин должно содержать <math>\Omega (r^2) \;</math> вершин. В [1, 3] можно ознакомиться с рассуждениями по поводу минорной двумерности и двумерности со сжатием для других параметров.