Велика енциклопедия на нефт и газ

Брой - независимост

Ако краен граф с n върхове има малък брой ребра, то неговият номер на независимост трябва да се очаква да бъде относително голям. [16]

Първият въпрос е еквивалентен на определяне на броя на доминирането на топовете на дъската n X n X n, а вторият е еквивалентен на определяне на броя на независимостта. [17]

Вземайки предвид класическото равенство от теорията на графовете: a0 p p cXj p, стигаме до извода, че е необходимо само да се споменат проблемите на изброяването на графики с даден номер на независимост на върха Po и дадено число px. Изброяването на графики по тези параметри изглежда интуитивно по-лесно от изброяването на графики с дадени номера на покритие; това обаче не следва от горното равенство. [18]

Нека G е произволна графика, двустранна или не, v (G) числото на независимостта на ръба (или, в друга терминология, числото на двойката комбинация) на графиката G, m (C) върхът, покриващ числото, a (G) номерът на независимостта на върха и p (G) е броят на капака на ръба. [19]

Важно е веднага да се отбележи, че в случая с числото на независимостта има значителна разлика между получаването на горните и долните оценки. Долната граница за числото на независимостта означава съществуването на независим набор от върхове с достатъчно голям размер. Един от начините да се намери такава долна граница е да се даде алгоритъм, който генерира голям (макар и не непременно най-големият) независим набор във всяка графика. Такъв алгоритъм често се нарича евристичен за проблема с пакетирането на върхове. [20]

За най-малките стойности на n, 2, 3, 4 лесно се проверява директно. Когато даден ръб е премахнат от графиката, номерът на независимостта може да се увеличи само с един. [21]

За най-малките стойности на n1, 2, 3, 4 лесно се проверява директно. Когато даден ръб е премахнат от графиката, номерът на независимостта може да се увеличи само с един. [22]

Набор от върхове на графика G се нарича независим, ако няма два от тях в съседство. Най-големият брой върхове в такива множества се нарича номер на независимостта на върха на графиката G и се обозначава с P0 (G) или pc. G) p/2 тогава и само ако G има 1-фактор. [23]

Всяка шахматна фигура може да бъде свързана с графика, чиито върхове са разположени на всички 64 квадрата на дъската, а ръбовете съответстват на ходовете на тази фигура. Сега е лесно да се види, че първият ни проблем е да определим числото на независимостта на графиката на дадена фигура, а вторият проблем е да определим доминантното число. [24]

Тогава, образно казано, плътна графика вероятно ще има по-голямо число на кликата и по-ниско число на независимост, докато рядката графика най-вероятно ще има обратната връзка между тези числа. [25]

Набор от върхове (ръбове) се нарича независим, ако няма два съседни елемента. Числото на независимостта на ръба (3r се определя по подобен начин. Броят на върховете, покриващи a на графика G, е най-малкият брой върхове, покриващи всички ръбове на графиката; броят на покритието на ръбовете al на графиката G се определя по подобен начин . [26]

Набор от върхове (ръбове) се нарича независим, ако няма два съседни елемента. Номерът на независимостта на ръба p се определя по подобен начин. Броят на върховете, покриващи a на графиката G, е най-малкият брой върхове, които покриват всички ръбове на графиката; броят на покритието на ръба в графика G се определя по подобен начин. [27]

Заключваме този раздел, като разглеждаме друга от еквивалентните двустранни теореми за съвпадение, също дължащи се на Кьониг (вж. Припомнете си, че покритие на ръба на графика G е съвкупността от ръбове, покриващи (в съвкупност) всеки връх в G, и че p ( G е най-малката от мощностите на кориците на границите на графика G. Както и преди, a (G) означава числото на независимостта (върха). Идентичностите на Gallai (вж. 1.0.1 и 1.0.2), заедно с теоремата на Кьониг, позволяват да установим лесно следния резултат. [28]

Установената връзка между чисто математически обекти - графики и проблеми за шахматни фигури, както видяхме, е съвсем естествена, което обяснява голямата популярност на шахматните термини и проблеми в литературата по теория на графовете. Много графични задачи, които са много сложни в общия случай, могат да бъдат решени за графики на шахматни фигури. Точно такъв е случаят с проблемите на независимостта и господството на шахматната дъска HI. По-долу ще намерим числата за независимост и доминиране за графиките на всички шахматни фигури и следователно ще решим и двата ни проблема за тях. [29]

Сега нека очертаем идеята на алгоритъма, който трябва да разгледаме. На първо място, трябва да опишем две локални конфигурации, така че ако се появи някоя от тях, лесно можем да намалим проблема до една по-малка графика. Бъбреците на такива локални конфигурации и намаляването на размерите могат да се извършват за полиномно време и следователно такова намаляване води до алгоритъм за време-полином. Читателят трябва да отбележи, че свеждането на този проблем до намирането на броя на независимостта на две по-малки графики е доста тривиално. Това намаляване обаче води до алгоритъм с експоненциално време за изпълнение, тъй като читателят може лесно да провери. [тридесет]