Кіріспе

Графтардағы байланысты емес төбелер

Графтар теориясында тәуелсіз жиын, тұрақты жиын, коклика немесе антиклика – графтың төбелерінің жиыны, олардың екеуі де жапсарлас емес. Яғни, бұл – кез келген екі төбе үшін, оларды байланыстыратын қабырға жоқ болатын төбелер жиыны. Басқаша айтқанда, графтың әрбір қабырғасының бір ұшы ғана А жиынында болады. Жиын тәуелсіз болу үшін, графтың толықтырылымында клика болуы керек және керісінше. Тәуелсіз жиынның өлшемі – оның құрамындағы төбелер саны. Тәуелсіз жиындар "ішкі тұрақты жиындар" деп те аталады, ал "тұрақты жиын" – оның қысқартылған түрі. Максималды тәуелсіз жиын – кез келген басқа тәуелсіз жиынның нақты кіші жиыны емес тәуелсіз жиын. Максималды тәуелсіз жиын – берілген граф үшін ең үлкен мүмкін болатын тәуелсіз жиын. Бұл өлшем тәуелсіздік саны деп аталады және әдетте α символымен белгіленеді. Мұндай жиынды табу мәселесі максималды тәуелсіз жиын мәселесі деп аталады. Бұл күшті NP-қиын мәселе. Осылайша, графтың максималды тәуелсіз жиынын табуға тиімді алгоритмнің болуы екіталай. Кез келген максималды тәуелсіз жиын сонымен қатар максималды болады, бірақ керісінше тұжырым дұрыс емес.

Басқа график параметрлерімен қатынасы

Жинақ егер және тек егер графтың толықтыруында клика болса ғана тәуелсіз болады, сондықтан екі түсінік бір-бірін толықтырады. Шындығында, үлкен кликалары жоқ жеткілікті үлкен графтарда үлкен тәуелсіз жиынтықтар болады, бұл Рамзи теориясында зерттелетін тақырып. Жинақ тәуелсіз, егер оның толықтыруы төбелік жабу болса. Демек, ең үлкен тәуелсіз жиынтықтың мөлшері мен ең кішкентай төбелік жабудың мөлшері графтың төбелерінің санына тең. Графтың төбелік бояуы оның төбелік жиынтығының тәуелсіз ішкі жиынтықтарға бөлінуіне сәйкес келеді. Осылайша, төбелік бояу үшін қажетті ең аз түстер саны, хроматикалық сан, графтың төбелерінің санының тәуелсіз санға қатынасынан кем болмайды. Жекеленген төбелері жоқ екібөлікті графта, ең үлкен тәуелсіз жиынтықтағы төбелер саны ең кішкентай жиектік жабудағы жиектер санына тең; бұл Кёниг теоремасы.

Ең үлкен тәуелсіз жиын

Басқа тәуелсіз жиынның нағыз ішкі жиыны емес тәуелсіз жиын максимал деп аталады. Мұндай жиынтар үстемдік ететін жиындар болып табылады. Кез келген графта ең көп дегенде 3n/3 максимал тәуелсіз жиын бар, бірақ көптеген графтарда одан да аз. n төбелі циклдік графтардағы максимал тәуелсіз жиындардың санын Перрин сандары көрсетеді, ал n төбелі жол графтарындағы максимал тәуелсіз жиындардың санын Падован тізбегі көрсетеді. Сондықтан, екі сан да 1.324718-нің дәрежелеріне пропорционалды, яғни пластикалық қатынасқа.

Нақты алгоритмдер

Максималды тәуелсіз жиынтық мәселесі NP-қиын. Дегенмен, оны әрбір төбелік кіші жиынтығын қарастырып, оның тәуелсіз жиынтық екенін тексеруге бағытталған қарапайым толық іздеу алгоритмімен берілетін O(n²2ⁿ) уақытынан тиімдірек шешуге болады. 2017 жылдан бастап, ол полиномдық кеңістікті пайдалана отырып O(1.1996n) уақытында шешілуі мүмкін. Ең жоғары дәрежесі 3 болатын графтармен шектелген жағдайда, оны O(1.0836n) уақытында шешуге болады. Көптеген графтар кластары үшін максималды салмақты тәуелсіз жиынтықты полиномдық уақытта табуға болады. Мысалы, тырнақсыз графтар, P5-еркін графтар және толық графтар. Хордалық графтар үшін максималды салмақты тәуелсіз жиынтықты сызықтық уақытта табуға болады. Модульдік декомпозиция – максималды салмақты тәуелсіз жиынтық мәселесін шешу үшін пайдалы құрал; кографтардағы сызықтық уақыт алгоритмі осыған қатысты негізгі мысал болып табылады. Таржан сипаттағандай, клик-бөлгіштер де маңызды құралдардың бірі. Кёниг теоремасы екі бөлікті графтарда екі бөлікті сәйкестендіру алгоритмін қолдану арқылы максималды тәуелсіз жиынтықты полиномдық уақытта табуға болатынын көрсетеді.

Тарату алгоритмдері

Жалпы алғанда, ең үлкен тәуелсіз жиынтық мәселесін полиномиалдық уақыт ішінде тұрақты факторға жуықтау мүмкін емес (егер P = NP болмаса). Шындығында, жалпы жағдайда Max Independent Set Poly-APX толық болып табылады, яғни ол полиномиалдық факторға жуықталатын кез келген мәселедей қиын. Дегенмен, шектеулі графтар кластары үшін тиімді жуықтау алгоритмдері бар.

Жазық графиктерде

Жазық графиктерде ең үлкен тәуелсіз жиынтық кез келген c < 1 жуықтау қатынасы бойынша полиномиалдық уақыт ішінде жуықтастырылуы мүмкін; кішілерді алу бойынша жабық графиктер отбасының кез келгені үшін ұқсас полиномиалдық уақытты жуықтау схемалары бар.

Шекаралы градус графиктерінде

Шектелген дәрежелі графтарда, максималды дәрежесінің белгілі бір мәні үшін тұрақты шамалау коэффициенттерімен тиімді шамалау алгоритмдері белгілі; мысалы, әр қадамда графтың ең төмен дәрежелі төбесін таңдап, оның көршілерін жоятын ашкөз алгоритм, максималды дәрежесі Δ графтарда (Δ+2)/3 шамалау коэффициентіне жетеді. Ондай мысалдар үшін шамалаудың қиындық шектері дәлелденді, тіпті 3-реттік және 3 жиекті боялатын графтардағы Максималды тәуелсіз жиын APX-толық.

Интервалды қиылысу графиктерінде

Интервалдық график — түйіндері 1 өлшемді интервалдар (мысалы, уақыт аралықтары) болатын және екі интервалдың арасында егер және тек қана олар қиылысса, жиек болатын график. Интервалдық графиктегі тәуелсіз жиын — бір-бірімен қабаттаспайтын интервалдар жиынтығы. Интервалдық графиктердегі ең үлкен тәуелсіз жиынды табу мәселесі, мысалы, жұмыс жоспарлау контекстінде зерттелді: компьютерде орындалуы керек жұмыстар жиынтығы берілгенде, бір-біріне кедергі келтірмей орындала алатын жұмыстардың ең үлкен жиынтығын табу керек. Бұл мәселені ең ерте мерзімді бірінші кезекте жоспарлау арқылы полиномиал уақытта дәл шешуге болады.

Геометриялық қиылысу графиктерінде

Геометриялық қиылысу графигі – түйіндері геометриялық пішіндер болатын және егер олар қиылысса, екі пішіннің арасында қабырға болатын график. Геометриялық қиылысу графигіндегі тәуелсіз жиын – бұл жай ғана бірімен-бірі қиылыспайтын (үстімелі емес) пішіндердің жиынтығы. Геометриялық қиылысу графиктерінде максималды тәуелсіз жиынды табу мәселесі, мысалы, автоматты түрде белгі қою контекстінде зерттелді: картадағы орналасқан жерлер жиынтығы берілгенде, осы жерлердің жанында максималды, қиылыспайтын тіктөртбұрышты белгілер жиынтығын табу. Қиылысу графиктерінде максималды тәуелсіз жиынды табу әлі де NP-толық мәселе болып табылады, бірақ оны жалпы максималды тәуелсіз жиынды табу мәселесіне қарағанда жақындату оңайырақ. Жақындағы шолуды [атауы] мақаласының кіріспесінде табуға болады.

D-қақазсыз графиктерде

Графиктегі d тырнақ – бұл d+1 төбеден тұратын жиын, олардың біреуі ("орталық") қалған d төбеге қосылған, ал қалған d төбелер бір-бірімен байланысқан емес. d тырнақсыз граф – бұл d тырнақ субграфы жоқ граф. Бос жиыннан басталып, кез келген жаңа төбе қосылғанда, ол жиынның ешбір төбесіне жақын болмаса, алгоритмді қарастырайық. d тырнақсыз графтарда, әрбір қосылған төбе максималды тәуелсіз жиыннан d-1 төбеге дейін жарамсыздық тудырады; сондықтан, бұл қарапайым алгоритм максималды тәуелсіз жиын үшін (d-1) жуықтама алгоритмін қамтамасыз етеді. Шындығында, одан да жақсы жуықтау коэффициенттерін алу мүмкін:

Нейвонер кез келген тұрақты ε>0 үшін d тырнақсыз графтардағы максималды салмақты тәуелсіз жиынға (d/2 – 1/63,700,992 + ε) жуықтамасын табатын полиномиалдық уақыт алгоритмін ұсынды. Циган кез келген ε>0 үшін (d+ε)/3 жуықтамасына жететін квазиполиномиалдық уақыт алгоритмін ұсынды.

Ең үлкен тәуелсіз жиынтықтарды табу

Максималды тәуелсіз жиынтықты табу мәселесін полиномиялық уақыт ішінде қарапайым параллельді ашкөз алгоритммен шешуге болады. Барлық максималды тәуелсіз жиынтықтар O(3ⁿ/₃) = O(1.4423n) уақытында табылады.

Тәуелсіз жиынтықты санау

#IS есептік мәселесі берілген бағытталмаған графтың қанша тәуелсіз жиынтықтарын қамтитынын анықтауды сұрайды. Бұл мәселе шешілмейтін, атап айтқанда, ол ♯P толық, тіпті ең жоғары үш дәрежелі графтар үшін де. Егер NP, RP-ден өзгеше болса, онда бұл мәселенің кездейсоқтандырылған толық полиномиалдық уақытпен жуықтау схемасы (FPRAS) жоқ, яғни ең жоғары дәрежесі алты графтарда да тиімді түрде жуықтау мүмкін емес. Алайда, ең жоғары дәрежесі бес болған жағдайда, толық полиномиалдық уақытпен жуықтау схемасы (FPTAS) бар. #BIS мәселесі, екібөлімді графтардағы тәуелсіз жиынтықты санау, сондай-ақ ♯P толық, тіпті ең жоғары үш дәрежелі графтар үшін де. #BIS-тің FPRAS-қа ие екені белгісіз. Ең үлкен тәуелсіз жиынтықты санау мәселесі де зерттелген.

Қолданбалар

Максималды тәуелсіз жиын және оның толықтырылысы, ең кішкентай төбелік жабу мәселесі, көптеген теориялық мәселелердің есептеу қиындығын дәлелдеуге қатысады. Олар сонымен қатар, нақты әлемдегі оңтайландыру мәселелері үшін пайдалы модельдер болып табылады, мысалы, максималды тәуелсіз жиын – жасалған генетикалық жүйелерді жобалау үшін тұрақты генетикалық компоненттерді анықтауға көмектесетін пайдалы модель.