Древесная ширина графа: различия между версиями

Альтернативное определение древесной ширины дается в терминах хордальных графов. Граф G = (V, E) является хордальным в том и столько том случае, если любой цикл длины не менее 4 содержит хорду, т.е. дугу между двумя непоследовательными вершинами цикла. Древесная ширина графа G не превышает значения k в том и только том случае, если G является подграфом хордального графа H, имеющего максимальную клику размером не более k.

Также можно дать еще одно определение в терминах упорядочения вершин. Пусть я – перестановка (в данном контексте называемая схемой исключения) вершин G = (V, E). Повторить следующий шаг для i = 1, ..., : : ; j Vj: взять вершину ж (i), превратить множество ее соседей в клику, а затем исключить v. Ширина ж равна максимуму по всем вершинам той же степени после ее исключения. Древесная ширина G равна минимальной ширине по всем схемам исключения.