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