Хордалдың аяқталуы - Chordal completion

Жылы графтар теориясы, математика бөлімі, а аккордты аяқтау берілген бағытталмаған граф G Бұл аккордтық график, сол шың жиынтығында G подограф ретінде аккордтың минималды аяқталуы аккордтық аяқталу болып табылады, сондықтан жиекті алып тастау арқылы құрылған кез-келген график аккордты аяқтау болмайды. A аккордтың минималды аяқталуы бұл мүмкіндігінше аз шеттері бар аккордтық аяқтау.

Аккордтың аяқталуының басқа түрі, оның өлшемін кішірейтеді максималды клик алынған аккордтық графикте кеңдік туралы G. Хордалдың аяқталуы бірнеше басқа графикалық кластарды сипаттау үшін де қолданылуы мүмкін, оның ішінде AT-сыз графиктер, тырнақсыз AT-сыз графиктер және ографтар.

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

Графиктің хордалды аяқталуы кейде үшбұрыш деп аталады,[1] бірақ бұл термин графикалық теория тұрғысынан да екіұшты, өйткені ол максималдыға да сілтеме жасай алады жазықтық графиктер.

Байланысты граф отбасылары

График G болып табылады AT жоқ график егер оның барлық минималды аккордтық аяқталуы болса ғана аралық графиктер. G Бұл тырнақсыз AT-сыз график, егер оның барлық минималды аккордтық аяқталуы тиісті интервалды графиктер болса ғана. Және G Бұл карта егер оның барлық минималды аккордтық аяқталуы болса ғана маңызды емес графиктер.[1]

График G бар кеңдік ең көп дегенде к егер және егер болса G кем дегенде бір аккордтық аяқталуы бар, оның максималды клик мөлшері ең көп дегенде к + 1. Онда бар жол ені ең көп дегенде к егер және егер болса G кем дегенде бір аккордтың аяқталуы бар, бұл максималды клик өлшемімен интервалды график к + 1. Онда бар өткізу қабілеттілігі ең көп дегенде к егер және егер болса G кем дегенде бір аккордтық аяқталуы бар, бұл максималды максималды өлшемі бар дұрыс интервалды график к + 1.[2] Және бар ағаштың тереңдігі к егер ол кем дегенде бір аккордты аяқтаса ғана, бұл ең үлкен графиктің өлшемі бар тривиальды график. к.[3]

Қолданбалар

Аккордты аяқтаудың бастапқы қолданылуы Компьютерлер және қиындықтар қамтиды Гауссты жою үшін сирек матрицалар. Гауссты жою процесінде матрицаның бастапқыда нөлге тең болатын, бірақ кейін нөлге айналатын коэффициенттерін толтыру мүмкіндігін азайту керек, өйткені бұл коэффициенттердің мәндерін есептеу қажеттілігі алгоритмді баяулатады. Сирек нөлдер үлгісі симметриялық матрица бағытталмаған графикамен сипатталуы мүмкін (оның матрицасы бар) матрица ); толтырылған матрицадағы нөлдердің өрнегі әрқашан аккордтық график болып табылады, кез-келген минималды аккордтың аяқталуы осылайша толтыру үлгісіне сәйкес келеді. Егер графиктің аккордтық аяқталуы берілсе, онда осы толтырылу үлгісіне жету үшін Гаусс элиминациясы орындалатын қадамдардың ретін, алынған аккорд графигінің жою ретін есептеу арқылы табуға болады. Осылайша, минималды толтыру мәселесін аккордты аяқтаудың минимумына балама ретінде қарастыруға болады.[4] Осы қосымшада, жазықтық графиктер екі өлшемді ақырлы элементтер жүйесін шешуде пайда болуы мүмкін; бұл жазықтық бөлгіш теоремасы әрбір жазықтық график n шыңдар ең көп дегенде аккордпен аяқталады O(n журнал n) шеттері.[5]

Тағы бір қосымша келеді филогения, эволюциялық ағаштарды қалпына келтіру мәселесі, мысалы генетикалық мутацияға ұшыраған организмдер ағаштары немесе ежелгі қолжазбалар жиынтығы ағаштары бір-бірінен жазба қателіктеріне көшірілген. Егер әрбір генетикалық мутация немесе скриптивті қателік тек бір рет болады деп есептесе, а мінсіз филогения, қандай да бір ерекше сипаттамаға ие түрлер немесе қолжазбалар әрдайым байланысты кіші ағашты құрайтын ағаш. Қалай Бунеман (1974) сипаттайды, мінсіз филогенияның болуын аккордты аяқтау мәселесі ретінде модельдеуге болады. Біреуі «қабаттасқан график» салады G онда шыңдар атрибуттық мәндер болып табылады (түрдің немесе қолжазбаның кейбір сипаттамалары үшін нақты таңдау), ал шеттері кем дегенде бір түрмен бөлінетін атрибуттық мәндер жұбын білдіреді. Графиктің шыңдары болуы мүмкін түрлі-түсті түстердің жалпы саны филогенияны алу үшін қолданылатын сипаттамалар санына тең болатындай етіп, әрбір атрибут мәні болатын сипаттамалардың сәйкестігі бойынша. Сонда мінсіз филогения бар және бар болса ғана болады G бояуды құрметтейтін аккордтық аяқтауға ие.[6]

Есептеудің күрделілігі

Ретінде тізімделгенімен ашық мәселе 1979 жылғы кітапта Компьютерлер және қиындықтар,[7] аккордты аяқтаудың минималды есебінің есептеу күрделілігі (деп те аталады минималды толтыру проблема) тез шешілді: Яннакакис (1981) болуын көрсетті NP аяқталды.[8] Егер минималды аккордтың аяқталуы қосылса к графиктің шеттері G, содан кейін ең көп дегенде аккордты аяқтауды табуға болады 8к2 полиномдық уақытта жиектер қосылды.[9] Оңтайлы жиынтығын табу мәселесі к қосу шеттерін а арқылы шешуге болады тіркелген параметрлі алгоритм, уақыттағы көпмүше график өлшемінде және субэкпоненциалк.[10]

The кеңдік (аккордтың аяқталуының минималды өлшемі) және жолдың ені мен ағаштың тереңдігін қоса алғанда, сәйкес параметрлерді есептеу үшін NP аяқталады, және (егер P = NP болмаса) көпмүшелік уақытта олардың оңтайлы мәндерінің тұрақты коэффициентіне жуықтауға болмайды; дегенмен, жуықтау алгоритмдері олар үшін логарифмдік жуықтау коэффициенттері белгілі.[11]

Минималды толтыру және кеңейту проблемаларын шешуге болады экспоненциалды уақыт. Дәлірек айтқанда n-текс сызбасы, уақыты O(1.9601n).[12]

Әдебиеттер тізімі

  1. ^ а б Парра, Андреас; Шефлер, Петра (1997), «Хордальды графикалық ендірулердің сипаттамалары және алгоритмдік қосымшалары», Графиктер мен комбинаторлық оңтайландыру бойынша Твенттің 4-ші семинары (Enschede, 1995), Дискретті қолданбалы математика, 79 (1–3): 171–188, дои:10.1016 / S0166-218X (97) 00041-3, МЫРЗА  1478250.
  2. ^ Каплан, Хаим; Шамир, Рон (1996), «Жолдың кеңдігі, өткізу қабілеті және аяқталу мәселелері кішігірім квалификацияланған интервалды графиктерге сәйкес келеді», Есептеу бойынша SIAM журналы, 25 (3): 540–561, дои:10.1137 / S0097539793258143, МЫРЗА  1390027.
  3. ^ Эппштейн, Дэвид (15 қараша, 2012), Графикалық параметрлер және суперграфтардағы клиптер.
  4. ^ Роуз, Дональд Дж. (1972), «Сызықтық теңдеулердің сирек позитивті анықталған жүйелерінің сандық шешімінің графикалық-теориялық зерттеуі», Графика теориясы және есептеу, Academic Press, Нью-Йорк, 183–217 бет, МЫРЗА  0341833.
  5. ^ Чунг, Ф.Р. К.; Мумфорд, Дэвид (1994), «Пландық графиктердің хордальдық комплектілері», Комбинаторлық теория журналы, B сериясы, 62 (1): 96–106, дои:10.1006 / jctb.1994.1056, МЫРЗА  1290632.
  6. ^ Бунеман, Питер (1974), «Қатты схемалардың сипаттамасы», Дискретті математика, 9 (3): 205–212, дои:10.1016 / 0012-365X (74) 90002-8, МЫРЗА  0357218.
  7. ^ Гари, Майкл Р.; Джонсон, Дэвид С. (1979), Компьютерлер және қиындықтар: NP-толықтығы теориясының нұсқаулығы, Фриман В., ISBN  0-7167-1045-5, [АШЫҚ4], б. 286; жаңарту, б. 339.
  8. ^ Яннакакис, Михалис (1981), «Минималды толтыруды есептеу NP-аяқталды», SIAM журналы алгебралық және дискретті әдістер туралы, 2 (1): 77–79, CiteSeerX  10.1.1.128.192, дои:10.1137/0602010, hdl:10338.dmlcz / 140775, МЫРЗА  0604513.
  9. ^ Натанзон, Ассаф; Шамир, Рон; Sharan, Roded (2000), «Минималды толтыру есебінің полиномдық жуықтау алгоритмі», Есептеу бойынша SIAM журналы, 30 (4): 1067–1079, дои:10.1137 / S0097539798336073, МЫРЗА  1786752.
  10. ^ Фомин, Федор V .; Villanger, Yngve (2013), «Subexponential параметрленген алгоритм минималды толтыру», Есептеу бойынша SIAM журналы, 42 (6): 2197–2216, arXiv:1104.2230, дои:10.1137 / 11085390X, МЫРЗА  3138120.
  11. ^ Бодлаендер, Ханс Л.; Гилберт, Джон Р .; Хафстейнссон, Хальмтыр; Kloks, Ton (1995), «енін, жолдың енін, фронтальды және ең қысқа жою ағашын жуықтау», Алгоритмдер журналы, 18 (2): 238–255, дои:10.1006 / jagm.1995.1009, МЫРЗА  1317666.
  12. ^ Фомин, Федор V .; Крач, Дитер; Todinca, Ioan (2004), «Кеңдік пен минималды толтырудың дәл (экспоненциалды) алгоритмдері», Автоматика, тілдер және бағдарламалау: 31-ші халықаралық коллоквиум, ICALP 2004, Турку, Финляндия, 12-16 шілде, 2004 ж., Информатикадағы дәрістер, 3142, Springer-Verlag, 568-580 бб, дои:10.1007/978-3-540-27836-8_49.