Характеризация запрещёнными графами
Характеризация запрещёнными графами — это метод описания семейства графов или гиперграфов путём указания подструктур, которым запрещено появляться внутри любого графа в семействе.
В теории графов многие важные семейства графов могут быть описаны конечным числом индивидуальных графов, которые не принадлежат семейству, и исключаются все графы из семейства, которые содержат любой из этих запрещённых графов в качестве (порождённого) подграфа или минора. В качестве прототипа явления служит теорема Понтрягина — Куратовского, которая утверждает, что граф планарен (граф, который можно нарисовать на плоскости без пересечений) тогда и только тогда, когда граф не содержит любой из двух запрещённых подграфов, полный граф K5 и полный двудольный граф K3,3.
В различных семействах природа запрещённого меняется. В общем случае структура G является членом семейства тогда и только тогда, когда запрещённая структура не содержится в G. Запрещённая подструктура может быть одной из:
Множество структур, которым запрещено принадлежать данному семейству графов, можно также назвать препятствующим множеством семейства.
Характеризация запрещёнными графами может быть использована в алгоритмах для проверки, принадлежит ли граф данному семейству. Во многих случаях можно проверить за полиномиальное время, содержит ли данный граф какой-либо член препятствующего множества, а потому, принадлежит ли граф семейству, определяемому препятствующим множеством.
Чтобы семейство имело характеризацию запрещёнными графами с определённым типом подструктур, семейство должно быть замкнуто по подструктурам. То есть любая подструктура (данного типа) графа в семействе должна быть другим графом в семействе. Эквивалентно, если граф не входит в семейство, все большие графы, содержащие его в качестве подструктуры, должны быть также исключены из семейства. Если это верно, всегда существует препятствующее множество (множество графов, не принадлежащих семейству, но все меньшие подструктуры принадлежат семейству). Однако, при некоторых представлениях, что понимать под подструктурой, это препятствующее множество может оказаться бесконечным. Теорема Робертсона – Сеймура доказывает, что в определённых случаях миноров графа, семейство, замкнутое по минорам, всегда имеет конечное препятствующее множество.