Индуцирана графика и индуцирана RO ширина на проблема
Нека въведем понятиятаиндуцирана графикаииндуцирана ширина(индуцирана ширина) на проблема с RO, които са важни за прилагането на структурни методи за решаване на проблеми с RO. Индуцираната ширина се определя от гледна точка на графиката на ограниченията на RO проблема.
Използваме концепцията за подреждане на графика или RO проблем.
Дефиниция 10.4. Нека разгледаме графика или проблем на UR, където .Подрежданетоза графика или PR проблем се нарича биекция.
Подреждането съответства на върховете или променливите, разглеждани в ред. Когато две променливи са свързани в графика чрез ребро, понякога е полезно първата променлива, която е по-рано в реда, да се представи като "родител", а втората като "син" на първия връх.
Преди да дефинираме индуцираната ширина, въвеждаме по-проста концепцияширинана графика.
Дефиниция 10.5. Нека е граф и нека е някакъв ред на върховете на този граф.Ширинатана връх за това подреждане е броят на върховете, свързани към и предхождащи го в това подреждане (т.е. броят на родителите). Ширината на графа за подреждане е максималната ширина на всички върхове за това подреждане. И накрая, ширината на графиката е минималната ширина за всички подреждания. Например едно дърво има ширина 1, а пълната върхова графа има ширина. Нека въведем следните определения:
Определение 10.6. Широчината на проблем с RO за дадено подреждане е ширината на неговата графика на ограничения за това подреждане, а ширината на PR се определя като ширината на неговата графика на ограничения.
Нека въведем концепцията за индуцирана графа по отношение на даден ред.
Дефиниция 10.7. При дадена графика и подреждане индуцираната графа се дефинира като графика с минимален набор от ребра, така че и ако , , , и , тогава.
Индуцираният граф може да бъде изграден с едно преминаване чрез обработка на върховете на оригиналния граф в обратен ред; тоест първо свързваме родителите на последния връх, след това родителите на предпоследния връх и т.н.
Дефиниция 10.8. Индуцираната ширина на графика по отношение на подреждане е ширината на индуцираната графа по отношение на това подреждане.
Индуцираната ширина на графика е нейната минимална индуцирана ширина за всички подреждания.
Индуцираната ширина на PR проблем по отношение на подреждане е индуцираната ширина на неговата ограничителна графика по отношение на това подреждане, а индуцираната ширина на PR проблем е индуцираната ширина на неговата ограничителна графика. Синоним на индуцирана ширина е дървовидна ширина (вижте раздел 8.5.3).
Известно е, че даденият RO проблем за даден ред може да бъде решен във времева експоненциала на индуцираната ширина по отношение на този ред.
Хордални графики
Графът се наричахордален, ако всеки цикъл с дължина 4 има хорда.
Много трудни проблеми с графики се решават лесно на хордови графики. Изчисляването на индуцираната ширина е доста лесно за хордови графики. Например, намирането на всички максимални клики в графика, което е NP-пълен проблем на общи графики, е лесно да се направи за хордови графики. Тази задача (намиране на максимални клики в хордови графики) се улеснява чрез използване на процедурата за подрежданеmax-cardinality.
Подрежданетоmax-cardinality[7]на графиката подрежда върховете, като се започне от първия, съгласно следното правило: първият връх се избира произволно. След това се избира следващият връх, свързан с максималния брой вече подредени върхове и т.н. Могапоказват, че подреждането по максимална кардиналност може да се използва за разпознаване на хордови графики. А именно, един граф е акордален тогава и само ако, в подреждането по максимална кардиналност, всеки връх заедно със своите предци образува клика. Така могат да се изброят всички максимални клики, съответстващи на всеки връх (чрез записване на наборите, състоящи се от всеки връх и неговите родители, и след това определяне на максималния размер на кликата). Обърнете внимание, че хордовият граф има най-много клики, състоящи се от върхове и техните предци.
Също така, когато се използва подреждането на максималната кардиналност на акордална графика, подредената графика е идентична на индуцираната й графика и следователно нейната ширина е равна на индуцираната й ширина. Справедлива
Твърждение. Ако е индуцирана графика на графика за някакъв ред, тогава графиката е акордална.