Неориентированный граф G называется строго хордальным , если он является хордальным и любой цикл чётной длины ( ${\displaystyle \geqslant 6}$ ) в G имеет нечётную хорду , то есть ребро, которое соединяет две вершины цикла на нечётном расстоянии (>1) друг от друга .

Описание

Строго хордальные графы имеют описание запрещёнными графами как графы, не содержащие пророждённого цикла длиной более трёх или n -солнца ( ${\displaystyle n\geqslant 3}$ ) в качестве порождённого подграфа . n -Солнце — это хордальный граф с 2 n вершинами, разделёнными на два подмножества ${\displaystyle U=\{u_{1},u_{2},\dots \}}$ и ${\displaystyle W=\{w_{1},w_{2},\dots \}}$ так, что каждая вершина w _i из W имеет ровно два соседа, u _i и ${\displaystyle u_{(i+1)\mod n}}$ . n -Солнце не может быть строго хордальным, поскольку цикл ${\displaystyle u_{1}w_{1}u_{2}w_{2}}$ … не имеет нечётных хорд.

Строго хордальные графы могут быть описаны как графы, имеющие строгий совершенный порядок исключения, порядок вершин, такой, что соседи любой вершины, которые идут в порядке позже, образуют клику , и такой, что для любых ${\displaystyle i<j<k<l}$ , если i -ая вершина в порядке смежна с k -ой и l -ой вершиной, а j -ая и k -ая вершины смежны, то должны быть смежны и j -ая, и l -ая вершины .

Граф строго является хордальным тогда и только тогда, когда любой из его порождённых подграфов имеет простую вершину, то есть вершину, соседи которой линейно упорядочены по порядку включения . Также граф строго хордален тогда и только тогда, когда он хордален и любой цикл длины пять и более имеет 2-хордовый треугольник, то есть треугольник, образованный двумя хордами и ребром цикла .

Граф является строго хордальным тогда и только тогда, когда любой из его порождённых подграфов является двойственно хордальным графом .

Строго хордальные графы могут быть описаны в терминах числа полных подграфов , которым ребро принадлежит . Ещё одно описание дано в статье Де Кариа и Макки .

Распознавание

Можно определить, является ли граф строго хордальным, за полиномиальное время путём повторяемого поиска и удаления простой вершины. Если этот процесс исключает все вершины графа, граф должен быть строго хордален. В противном случае процесс не находит подграф без простой вершины и в этом случае исходный граф не может быть строго хордален. Для строго хордального графа порядок, в котором вершины удаляются в этом процессе, называется строгим совершенным порядком исключения .

Известны альтернативные алгоритмы, которые могут определить, является ли граф строго хордальным и, если да, построить строгий совершенный порядок исключения более эффективно, за время ${\displaystyle O(\min(n^{2},(n+m)\log n))}$ для графа с n вершинами и m рёбрами .

Подклассы

Важным подклассом (основанным на филогении ) является класс k - , то есть графов, образованных из листьев дерева путём соединения двух листьев ребром, если расстояние в дереве не превосходит k . Листовая степень — это граф, являющийся k -листовой степенью для некоторого k . Поскольку степени строго хордальных графов строго хордальны и деревья строго хордальны, отсюда следует, что листовые степени строго хордальны. Они образуют собственный подкласс строго хордальных графов, который, в свою очередь, включает как 2-листовые степени . Другим важным подклассом строго хордальных графов являются интервальные графы . В статье Бранштедта, Худта, Манчини и Вагнера показано, что интервальные графы и больший класс корневых ориентированных путей являются листовыми степенями.

Алгоритмические проблемы

Поскольку строго хордальные графы одновременно хордальны и двойственно хордальны , различные NP-полные задачи, такие как задача о независимом множестве , задача о клике , раскраска , задача о кликовом покрытии , доминирующее множество и задача Штейнера о минимальном дереве могут быть решены эффективно для строго хордальных графов. Задача изоморфизма графов GI-полна для строго хордальных графов . Поиск гамильтоновых циклов остаётся для строго хордальных расщепляемых графов NP-полной задачей .

Примечания

Литература