Кіріспе

Нақты сандар түзуіндегі интервалдардың қиылысу графигі

Графтар теориясында интервалдық граф — нақты түзудегі интервалдар жиынынан құрылған, әр интервал үшін бір төбе және интервалдары қиылысатын төбелер арасында қабырғасы бар бағытталмаған граф. Бұл интервалдардың қиылысу графигі. Интервалдық графтар — хордалық графтар және толық графтар. Оларды сызықтық уақытта тануға болады, сондай-ақ осы графтардағы оңтайлы түс беру немесе ең ірі кликаны сызықтық уақытта табуға болады. Интервалдық графтарға барлық дұрыс интервалдық графтар кіреді, олар бірлік интервалдар жиынынан ұқсас түрде анықталады. Бұл графтар тағамдық тізбектерді модельдеу үшін және бір-бірімен қабаттаспайтын уақытта орындалатын міндеттердің ішкі жиынын таңдау қажет болатын кестелеу мәселелерін зерттеу үшін қолданылған. Басқа қолданыстар: ДНҚ картасындағы тұтас кіші тізбектерді құрастыру және уақыттық қорытындылар.

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

Берілген графтың интервалдық граф екенін анықтау, оның ең үлкен кликаларының тәртібін іздеу арқылы, төбелерді қамту бойынша тізбектелгендік қағидасын сақтау арқылы жасалуы мүмкін. Көптеген белгілі алгоритмдер осылай жұмыс істейді, бірақ интервалдық графтарды олардың кликаларын пайдаланбастан сызықтық уақытта тануға да болады. Түпнұсқа сызықтық уақытты тану алгоритмі күрделі PQ ағаш дерек құрылымына негізделген, бірақ граф интервалдық граф болып табылады, егер және тек ол хордалы болса және оның толықтырылуы салыстырылатын граф болса, онда лексикографиялық ендігіне бірінші іздеуді қолдану арқылы мәселені қарапайым шешуге болатынын көрсетті. 6-реттік LexBFS алгоритмін қолдана отырып, ұқсас тәсіл сипатталған.

Графтардың туысқан отбасылары

Интервалдық графиктерді АТ-еркін хордалық графиктер ретінде сипаттау арқылы, интервалдық графиктер күшті хордалық графиктер болып табылады, демек олар кемелді графиктер. Олардың толықтырулары салыстырылатын графиктер класына жатады, ал салыстырылатын қатынастар – интервалдық реттердің өзі. Граф интервалдық граф болса және тек қана ол хордалық болса және оның толықтыруы салыстырылатын граф болса, онда граф және оның толықтыруы екеуі де интервалдық графтар болып табылады, егер және тек қана граф екіге бөлінген граф және пермутация граф болса. Кез келген екі интервалдың өзара қиыспайтын немесе біріне бірі ішкі жиын болып табылатын интервалдық бейнесі бар интервалдық графиктер тривиальды кемелді графиктер болып табылады. Графтың бұрыштық саны ең көп дегенде бір болса, ғана ол интервалдық граф болып табылады; кез келген графтың бұрыштық саны – бірдей төбелер жиынындағы интервалдық графтардың ең аз саны, олардың жиектерінің қиылысы болып табылады. Шеңбер доғаларының қиылыс графтары – интервалдық графтарды қамтитын шеңберлік доға графтарын құрайды. Трапециялық графиктер, трапециялардың қиылыстары, олардың параллель қабырғалары бірдей екі параллель түзуде жатса, сондай-ақ интервалдық графтардың жалпылама түрі болып табылады. Қосылған үшбұрышсыз интервалдық графиктер – дәл қазгүл ағаштары.

Дұрыс интервалдық графиктер

Дұрыс интервалдық графиктер — интервалдық графиктер, онда ешбір интервал басқа интервалды толығымен қамтып жатпайды; бірлік интервалдық графиктер — интервалдық графиктер, онда әрбір интервалдың ұзындығы бірлікке тең. Қайталанбайтын интервалдармен бірлік интервалдық бейнелеу міндетті түрде дұрыс интервалдық бейнелеу болып табылады. Кез келген дұрыс интервалдық бейнелеу бірлік интервалдық бейнелеу бола бермейді, бірақ кез келген дұрыс интервалдық график бірлік интервалдық график болып табылады, және керісінше. Кез келген дұрыс интервалдық график тырнақсыз график болып табылады; керісінше, дұрыс интервалдық графиктер — дәл тырнақсыз интервалдық графиктер. Дегенмен, интервалдық график емес тырнақсыз графиктер де бар. Егер ешбір интервал басқа интервалдардан көп қамтылмаса, онда интервалдық график дұрыс деп аталады. Бұл түсінік дұрыс интервалдық графиктер туралы идеяны кеңейтеді, сондықтан 0 дұрыс интервалдық график те дұрыс интервалдық график болып табылады. Егер ешбір интервал басқа интервалдарды көп қамтып жатпаса, онда интервалдық график дұрыс емес деп аталады. Бұл түсінік дұрыс интервалдық графиктер туралы идеяны кеңейтеді, сондықтан 0 дұрыс емес интервалдық график те дұрыс интервалдық график болып табылады. Егер бір-біріне енген интервалдардың тізбегі болмаса, онда интервалдық график енгізілген график деп аталады. Бұл дұрыс интервалдық графиктердің жалпылама түрі, өйткені 1 енгізілген интервалдық графиктер — дәл дұрыс интервалдық графиктер.

Қолданбалар

Интервалдық графиктердің математикалық теориясы RAND корпорациясының математика бөлімінің зерттеушілері тарапынан, қолдану мақсатында әзірленді, оның ішінде Питер С. Фишберн сияқты жас зерттеушілер, Алан С. Таккер және Джоэл Э. Коэн сияқты студенттер, сондай-ақ Делберт Фулкерсон және (қайта келіп тұратын қонақ) Виктор Кли сияқты жетекшілер болды. Коэн интервалдық графиктерді популяциялық биологияның математикалық модельдеріне, әсіресе тағамдық тізбектерге қолданды. Интервалдық графиктер операциялық зерттеулер және жоспарлау теориясында ресурстарды бөлу мәселелерін бейнелеу үшін қолданылады. Бұл қолданыстарда әрбір интервал белгілі бір уақыт аралығында ресурсқа (мысалы, таратылған есептеу жүйесінің өңдеу блогы немесе сынып бөлмесі) жасалған сұранысты көрсетеді. График үшін максималды салмақты тәуелсіз жиынтық мәселесі – қақтығыстарсыз қанағаттандырылатын сұраныстардың ең жақсы жиынтығын табу мәселесін білдіреді. Қосымша ақпарат алу үшін интервалдық жоспарлауға қараңыз. Интервалдық графиктің оңтайлы түспен бояуы – мүмкіндігінше аз ресурстарды қолдана отырып, барлық сұраныстарды қамтитын ресурстарды тағайындауды білдіреді; оны сол жақ шеткі нүктелері бойынша сұрыпталған интервалдарды бояйтын ашкөз түспен бояу алгоритмі арқылы көп уақытта табуға болады. Басқа да қолданыстар: генетика, биоинформатика және компьютерлік ғылым. Интервалдық графикті бейнелейтін интервалдар жиынтығын табу ДНК картасындағы тұтас кіші тізбектерді құрастырудың бір жолы ретінде де қолданылуы мүмкін. Интервалдық графиктер уақыттық ойлауда маңызды рөл атқарады.

Интервалды аяқтау және жолдың ені

Егер G кездейсоқ график болса, G графигінің интервалдық толықтыруы – сол төбелер жиынындағы, G графигін кіші график ретінде қамтитын интервалдық график. Интервалдық толықтырудың параметрленген нұсқасы (k қосымша қабырғалары бар интервалдық суперграфикті табу) параметрленген түрде шешіледі, және одан әрі, параметрленген субекспоненциалдық уақытта шешіледі. Интервалдық графиктің жол ені оның ең ірі кликасының өлшемінен (немесе, эквивалентті түрде, оның түс санынан бір кем) кем, ал кез келген G графигінің жол ені, оны кіші график ретінде қамтитын интервалдық графиктің ең кіші жол енімен тең болады.