Тема номер 5 „Независими комплекти, покритие, щракване“ (3 часа)
5.1 Независими декори и клики
5.1.1Независими комплекти и покрития
5.1.1.1В много приложни задачи се изисква да се намери в краен набор от обекти максималната система от обекти, които не са двойно несвързани помежду си, или да се избере минималната система от обекти, свързани с всички останали. Формулирането на такива проблеми на езика на теорията на графовете води до концепциите за независимост и покритие.
Много върхове графиката се извиква независим (или вътрешно стабилен), ако няма два върха от това множество са съседни. С други думи, ако SÍVG и С независимо в графиката G, след това генерираният подграф G (S) празно е. Очевидно е, че в този случай S'ÍS, тогава С '- също независим набор.
Извиква се независим набор максимум, ако не е подходящо подмножество на някакъв друг независим набор. Нарича се най-големият независим набор по отношение на мощността най-великия.
Една от чисто ежедневните интерпретации на концепцията за независимост е следната. Определен човек иска да организира годишнина с максимален брой гости от своите познати. В стремежа си да направи юбилейната вечер приятна, той трябва да организира всичко така, че хората, които симпатизират един на друг, да присъстват на тази вечер. Тъй като отношението на "съчувствие" не е преходно, той ще трябва да намери броя на независимостта, за да постигне целта броят на неговите приятели. Тази графика е структурирана по следния начин. Върховете му са познати на героя на деня. Два върха са съседни, ако съответните познати не симпатизират един на друг. Лесно е да се разбере, че номерът на независимостта на тази графика представлява максималния контингент от поканени, които героят на деня може да си позволи.
Например, добре познатият проблем на осем дами, който е свързан с името на К. Гаус, намалява до намирането на най-големия независим набор от върхове в графика.
Проблемът с осемте кралици: изисква се да се подредят най-голям брой дами на шахматната дъска, така че те да не се атакуват помежду си. Очевидно може да има не повече от осем такива дами, тъй като не трябва да има две от тях в едно досие или ранг. Едно от решенията на проблема с осем дами е показано на фигура 5.1.
Броят на върховете в най-големия независим набор от графиката G Наречен броя на независимостта (брой вътрешна стабилност, разхлабеност или брой на горната опаковка) от тази графика и се обозначава с α0 (G).
Например за графиката G, показано на фигура 5.2, α0 (G) = 4, набор от върхове , и са най-големите независими, и - максимално независим набор, който не е най-големият.
Теорема. За всяка графика G неравенството е вярно
,
и равенството се спазва, ако графиката G - завършен (припомнете си, че графиката е пълна, ако някой от нейните върхове е в съседство).