Кіріспе

Графикте барлық ұзын циклдерде акорды бар

Граф теориясының математикалық саласында хордалық граф – төрт немесе одан көп түйінді барлық циклдарында акорды бар граф, яғни циклдың өзіне жатпайтын, бірақ циклдың екі түйінін қосатын қабырға. Басқаша айтқанда, графтың әрбір индукцияланған циклында дәл үш түйін болуы керек. Хордалық графтарды кемшіліксіз жою реті бар графтар, әрбір минималды бөлгіші клика болатын графтар және ағаштың тармақтарының қиылысу графиктері ретінде де сипаттауға болады. Олар кейде қатаң тізбектік графтар немесе үшбұрыштау графтары деп те аталады: графтың хордалық толықтырылуы әдетте сол графтың үшбұрыштауы деп аталады. Хордалық графтар – кемел графтардың ішкі жиыны. Оларды сызықтық уақытта тануға болады және графты бояу сияқты басқа граф кластарында қиын болатын бірнеше мәселелерді хордалық графтар үшін полиномиалдық уақытта шешуге болады. Кез келген графтың ағаш ені оны қамтитын хордалық графтардағы кликалардың өлшемімен сипатталады.

Кемелсіз жою және тиімді тану

Графиктегі толық жою реті – графтың төбелерінің реті, мұнда әрбір v төбесі үшін v және v-ден кейін келетін v-нің көршілері бірлік құрайды. Граф тек қана толық жою реті болса ғана шындыққа келтірілген граф деп аталады. (осыны да қараңыз) Шындыққа келтірілген графиктің толық жою реті лексикографиялық ендік бірінші іздеу деп аталатын алгоритмді пайдаланып тиімді түрде табылуы мүмкін. Бұл алгоритм графтың төбелерін жиындар тізбегіне бөліп сақтайды; бастапқыда бұл тізбек барлық төбелері бар бір жиыннан тұрады. Алгоритм қайта-қайта бұрын таңдалмаған төбелері бар тізбектегі ең ерте жиыннан v төбесін таңдайды және әрбір S жиынын екі кіші жиынға бөледі, біріншісі S-дегі v-нің көршілерінен, екіншісі көрші емес төбелерден тұрады. Бұл бөлу процесі барлық төбелер үшін орындалған кезде, жиындар тізбегінде әрбір жиында бір төбе болады, бұл толық жою ретінің керісіне сәйкес келеді. Бұл лексикографиялық ендік бірінші іздеу процесі де, реттіліктің толық жою реті ме екенін тексеру процесі де сызықтық уақытта орындалуы мүмкін болғандықтан, шындыққа келтірілген графтарды сызықтық уақытта тануға болады. Шындыққа келтірілген графтардағы графтық сэндвич мәселесі NP-толық, ал шындыққа келтірілген графтардағы зондтық граф мәселесі полиномиалдық уақыт күрделілігіне ие. Шындыққа келтірілген графиктің барлық толық жою реттерінің жиынтығын антиматроидтың негізгі сөздері ретінде модельдеуге болады; осы антиматроидтармен байланыстыны белгілі бір шындыққа келтірілген графиктің барлық толық жою реттерін тиімді тізімдеу алгоритмінің бөлігі ретінде пайдаланыңыз.

Максималды кликалар және графиктің бояуы

Кемелсіз жою ретінің тағы бір қолданылуы – көп уақытта хордалық графтың ең үлкен кликасын табу, ал жалпы графтар үшін осы мәселе NP-толық. Жалпы алғанда, хордалық графта тек сызықтық санымен максималды кликалар болуы мүмкін, ал хордалық емес графтарда олардың саны экспоненциалды болуы мүмкін. Бұл хордалық графтар класының кликаларының саны аз екенін көрсетеді. Хордалық графтың барлық максималды кликаларын тізімдеу үшін, кемелсіз жою ретін табыңыз, әр төбе v үшін v-нің кейінгі орналасқан көршілерімен бірге v-ге сәйкес клика құрыңыз және нәтижеде алынған кликалардың әрқайсысы максималды екенін тексеріңіз. Хордалық графтардың кликалық графтары – дуалды хордалық графтар. Ең үлкен максималды клика – максималды клика, және хордалық графтар кемелді болғандықтан, осы кликаның өлшемі хордалық графтың хроматикалық санына тең. Хордалық графтар өте жақсы реттеледі: оптималды бояуды кемелсіз жою ретінің керісі бойынша төбелерге ашкөз бояу алгоритмін қолдану арқылы алуға болады. Хордалық графтың хроматикалық полиномын есептеу оңай. Кемелсіз жою ретін табыңыз. -ның сол ретте кейін орналасқан көршілерінің саны болсын. Мысалы, . Хроматикалық полином тең. (Соңғы көбейткіш жай ғана x, сондықтан x полиномды бөледі, бұл қажет.) Бұл есептеудің хордалылыққа байланысты екені анық.

Ең аз бөлгіштер

Кез келген графта, төбелердің бөлгіші – оларды жойғанда қалған графтың байланысы үзілген төбелер жиыны; егер оның бөлгіш болатын дұрыс ішкі жиыны болмаса, бөлгіш минималды болып саналады. Теорема бойынша, хордалық графтар – әрбір минималды бөлгіші клика болатын графтар; Дирак хордалық графтардың толық екенін дәлелдеу үшін осы сипаттаманы пайдаланды. Хордалық графтар отбасы индуктивті түрде, төбелері бос емес үш кіші жиынға – A, S және B – бөлінетін графтар ретінде анықталады, мұнда A ∪ S және S ∪ B екеуі де хордалық индукцияланған кіші графтарды құрайды, S – клика, ал A-дан B-ге қарай ребролар жоқ. Яғни, олар кликалық бөлгіштер арқылы кішірек кіші графтарға рекурсивті түрде жіктелетін графтар. Осы себепті хордалық графтар кейде жіктемелі графтар деп те аталады.

Ағаштардың қиылысу графиктері

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

Кіші сыныптар

Интервалдық графиктер – жол графиктерінің кіші ағаштарының қиылысу графиктері, ағаштардың ерекше жағдайы. Сондықтан, олар хордалық графтардың кіші тобы болып табылады. Бөлінген графиктер – хордалық графтар және хордалық графтардың толықтырулары болып табылатын графиктер. n шексіздікке жақындағанда, n төбелі хордалық графтардың бөлінген графтарға жақындасатынын көрсетті. Птолемейлік графтар – хордалық және қашықтық мұрагерлік графтар. Квази-шегілік графтар – хордалық және кографтар болып табылатын Птолемейлік графтардың кіші класы. Блок-графиктер – Птолемейлік графтардың тағы бір кіші класы, онда кез келген екі максималды кликада ортақ төбе саны бірден аспайды. Арнайы түрі – жел терісі графтары, онда әрбір клика жұбы үшін ортақ төбе бірдей болады. Қатты хордалық графтар – хордалық графтар, оларда индукцияланған кіші граф ретінде n күн (n ≥ 3) болмайды. Мұнда n күн – бұл n төбелі хордалық граф G және G-дегі Гамильтондық циклдің қабырғаларына іргелес n екінші дәрежелі төбелер жиыны. K-ағаштар – барлық максималды кликалар мен барлық максималды кликаларды бөлетін хордалық графтар. Аполлондық желілер – хордалық максималды жазық графтар немесе эквивалентті жазық 3-ағаштар. Максималды сыртқы жазық графтар – 2-ағаштардың кіші класы болып табылады, сондықтан олар да хордалық болып табылады.

Жоғары сыныптар

Хордалық графтар — жақсы белгілі кемелді графтардың кіші тобы. Хордалық графтардың басқа да жоғары деңгейдегі кластарына әлсіз хордалық графтар, коп-уин графтары, тақ тесіксіз графтар, жұп тесіксіз графтар және Мейниел графтары жатады. Хордалық графтар — бұл тақ тесіктен де, жұп тесіктен де бос графтар (графтар теориясындағы тесіктер туралы қараңыз). Кез келген хордалық граф — тұншықтырылған граф, ондағы әрбір шеткі цикл үшбұрыш болады, себебі шеткі циклдар — индуцирленген циклдардың ерекше жағдайы. Тұншықтырылған графтар — хордалық графтар мен максималды жазық графтардың кликалық қосындысы арқылы құрылатын графтар. Сондықтан, тұншықтырылған графтарға максималды жазық графтар да кіреді.

Хордалық толығымен және ағаштың ені

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