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

Перейти к навигации Перейти к поиску
Строка 6: Строка 6:




Первые два класса задач относятся к вложениям в плоскость. Граф является планарным, если он может быть изображен на плоскости или сфере без пересечения дуг. Граф имеет (эйлеров) род не более g, если он может быть изображен на плоскости с эйлеровой характеристикой g. Класс графов имеет ограниченный род, если каждый граф класса имеет род не более g при фиксированном g.
Первые два класса задач относятся к вложениям в плоскость. Граф является [[планарный граф|планарным]], если он может быть изображен на плоскости или сфере без пересечения дуг. Граф имеет (эйлеров) [[род графа|род]] не более g, если он может быть изображен на плоскости с эйлеровой характеристикой g. Класс графов имеет ''ограниченный род'', если каждый граф класса имеет род не более g при фиксированном g.




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


== Двумерные параметры ==
== Двумерные параметры ==