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

Следующие три класса задач касаются исключения миноров. Пусть дано ребро e = {v, w} в графе G. [[Сжатие ребра]] e в графе G заключается в определении вершин v и w в G и удалении всех циклов и дублирующихся ребер. Граф H, полученный в результате последовательности таких операций сжатия ребер в исходном графе G, называется ''сжатием'' графа G. Граф H называется [[минор графа|минором]] графа G, если H является подграфом некоторого сжатия G. Класс графов C является ''замкнутым относительно операции взятия минора'', если любой минор любого графа из C также является членом C. Класс графов C, замкнутый относительно операции взятия минора, является ''свободным от H-миноров'', если <math>H /notin C \;</math>. В более общем смысле, термин «свободный от H-миноров» относится к любому классу графов, замкнутому относительно операции взятия минора, который не включает некоторый фиксированный граф H. ''Граф с однократным пересечением'' представляет собой минор графа, который может быть изображен на плоскости так, что в нем будет пересекаться не более одной пары ребер. Класс графов, замкнутый относительно операции взятия минора, является ''свободным от миноров с однократным пересечением'', если из него исключен фиксированный граф с однократным пересечением. [[Апексный граф|Апексным графом]] называется граф, который становится планарным при удалении из него некоторой вершины. Класс графов является ''свободным от апексных миноров'', если из него исключен некоторый фиксированный апексный граф.