Войти  |  Регистрация
Авторизация

Строго хордальный граф



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

Описание

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

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

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

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

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

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

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

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

Подклассы

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

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

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


Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent