граф со свойством, что в каждом его порождённом подграфе размер максимального (по размеру) независимого множества равен числу максимальны Из Википедии, свободной энциклопедии
Тривиально совершенный граф — это граф со свойством, что в каждом его порождённом подграфе размер максимального (по размеру) независимого множества равен числу максимальных клик[1][2]. Тривиально совершенные графы первым изучал Волк[3][4], но название дал Голумбик[2]. Голумбик писал, что «это название было выбрано ввиду тривиальности доказательства, что такие графы являются совершенными.» Тривиально совершенные графы известны также как графы сравнимости деревьев[3][4], древовидные графы сравнимости[5] и квазипороговые графы[6].
Построение тривиально совершенного графа из вложенных интервалов и из отношения достижимости в дереве
Тривиально совершенные графы имеют несколько других эквивалентных описаний:
Они являются графами сравнимостидеревьев из теории порядков[англ.]. То есть пусть T — частичный порядок, такой, что для любого t ∈ T множество {s ∈ T: s < t} является вполне упорядоченным с отношением < и T обладает наименьшим элементом r. Тогда граф сравнимости порядка T тривиально совершенен и любой тривиально совершенный граф может быть сформирован таким образом[7][8].
Они являются графами, которые можно представить как интервальные графы множества вложенных промежутков. Множество промежутков имеет свойство вложенности, если для любых двух промежутков из множества они либо не пересекаются, либо один из них содержится в другом[11].
Они являются графами, которые одновременно являются хордальными графами и кографами[12][13]. Это следует из описания хордальных графов как графов без порождённых циклов длины четыре и больше и кографов как графов без порождённых путей с четырьмя вершинами (P4).
Они являются графами, одновременно являющимися кографами и интервальными графами[12][13].
Они являются графами, которые могут быть образованы, начиная с графов с одной вершиной, с помощью двух операций — несвязное объединение двух меньших тривиально совершенных графов и добавления новой вершины, смежной всем вершинам меньшего тривиально совершенного графа[6][14]. Эти операции соответствуют образованию нового леса путём несвязного объединения двух меньших лесов и образованию дерева путём соединения нового корня с корнями всех деревьев леса.
Они являются графами, в которых для любого ребра uvокрестности вершин u и v (включая сами u и v) вложены — одна окрестность должна быть окрестностью другой[13].
Пороговые графы — это в точности те графы, которые являются одновременно тривиально совершенными и являются дополнением тривиально совершенных графов (тривиально совершенных кографов)[17][18].
Чу[19] описывает простой алгоритм линейного времени для распознавания тривиально совершенных графов, основанный на лексикографическом поиске в ширину. Когда алгоритм LexBFS удаляет вершину v из первого множества в очереди, алгоритм проверяет, что все оставшиеся соседи вершины v принадлежат тому же множеству. Если нет, один из запрещённых порождённых подграфов может быть построен из v. Если проверка успешна для всех v, то граф тривиально совершенен. Алгоритм можно модифицировать для проверки за линейное время, является ли граф дополнением тривиально совершенного графа.
Определение, получается ли граф общего вида после удаления k рёбер тривиально совершенным графом, является NP-полной задачей[20], фиксированно-параметрически разрешимой[21], и она может быть решена за время O(2,45k(m+n))[22].
Cai L.Fixed-parameter tractability of graph modification problems for hereditary properties// Information Processing Letters.— 1996.— Т. 58, вып. 4.— С. 171–176.— doi:10.1016/0020-0190(96)00050-6.
Frank Pok Man Chu.A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements// Information Processing Letters.— 2008.— Т. 107, вып. 1.— С. 7–12.— doi:10.1016/j.ipl.2007.12.009.
Frank Gurski.Characterizations for co-graphs defined by restricted NLC-width or clique-width operations// Discrete Mathematics.— 2006.— Т. 306, вып. 2.— С. 271–277.— doi:10.1016/j.disc.2005.11.014.
James Nastos, Yong Gao.A Novel Branching Strategy for Parameterized Graph Modification Problems// Lecture Notes in Computer Science.— 2010.— Т. 6509.— С. 332–346.
Rubio-Montiel C.A new characterization of trivially perfect graphs// Electronic Journal of Graph Theory and Applications.— 2015.— Т. 3, вып. 1.— С. 22–26.— doi:10.5614/ejgta.2015.3.1.3.
Roded Sharan.Graph modification problems and their applications to genomic research// PhD Thesis, Tel Aviv University.— 2002.
