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