Бокс - Boxicity

Тік төртбұрыштардың қиылысу графигі, екі бокстылығы бар

Жылы графтар теориясы, бокс Бұл график өзгермейтін, енгізген Фред С. Робертс 1969 ж.

Графиктің қорапшылығы минималды өлшем онда берілген графиканы ан түрінде көрсетуге болады қиылысу графигі ось-параллель қораптар. Яғни, арасында жеке-жеке сәйкестік болуы керек төбелер графаның және жәшіктер жиынтығының, мысалы, егер тиісті шыңдарды қосатын жиек болса, екі қорап қиылысады.

Мысалдар

Суретте алты төбесі бар график және осы графиктің тіктөртбұрыштардың (екі өлшемді қораптар) қиылысу графигі ретінде көрінісі көрсетілген. Бұл графикті кез-келген төменгі өлшемдегі қораптардың қиылысу графигі ретінде ұсынуға болмайды, сондықтан оның қорапшылығы екіге тең.

Робертс (1969) графигі 2 болатынын көрсеттіn жою арқылы пайда болған төбелер тамаша сәйкестік а толық граф 2-деn шыңдар дәл боксизмге ие n: ажыратылған төбелердің әр жұбы бір-біріне жұпқа қарағанда басқа өлшемде бөлінген қораптармен ұсынылуы керек. Өлшемі дәл осы графиктің өрісі n әрқайсысының қалыңдатуы арқылы табуға боладыn қырлары n-өлшемді гиперкуб қорапқа. Осы нәтижелерге байланысты бұл график «деп аталды Робертс графигі,^[1] дегенмен ол жақсы танымал коктейльдер кестесі және оны деп түсінуге болады Туран графигі Т(2n,n).

Басқа графикалық кластармен байланыс

Графиктің боксизмі ең көбі, егер ол ан болса ғана болады аралық график; ерікті графиктің боксизмі G - бұл бірдей шыңдар жиынтығындағы интервалдық графиктердің минималды саны, осылайша интервалдық графиктердің жиектер жиектерінің қиылысы G. Әрқайсысы сыртқы жоспарлау сызбасы ең көп дегенде екеуі,^[2] және әрқайсысы жазықтық график ең көп дегенде үшеуі бар.^[3]

Егер екі партиялы графиктің екі бокстілігі болса, оны жазықтықтағы ось-параллель сызық сегменттерінің қиылысу графигі ретінде ұсынуға болады.^[4]

Adiga, Bhowmick & Chandran (2011) екі жақты графиктің бокстылығы дәлелденді G фактордың 2 факторында болады тапсырыс өлшемі биіктіктің екеуі жартылай тапсырыс берілген жиынтық байланысты G келесідей: минималды элементтер жиыны бір партит жиынтығына сәйкес келеді G, максималды элементтер жиыны екінші партит жиынтығына сәйкес келеді G, және егер сәйкес шыңдар in көршілес болса, екі элементті салыстыруға болады G. Эквивалентті түрде тапсырыс өлшемі биіктікте жартылай тапсырыс берілген жиынтық P ішіндегі боксизмнің 2 факторында болады салыстыру графигі туралы P (бұл екі жақты, өйткені P биіктігі екі).

Алгоритмдік нәтижелер

Көптеген графикалық есептерді басқа графиктерге қарағанда шектелген боксикалы графиктер үшін тиімді шешуге немесе жуықтауға болады; мысалы, максималды проблема шектеулі бокстығы бар графиктер үшін көпмүшелік уақытта шешілуі мүмкін.^[5] Кейбір басқа графикалық есептер үшін тиімді шешім немесе жуықтау табуға болады, егер төмен өлшемді қораптың көрінісі белгілі болса.^[6] Алайда, мұндай ұсынысты табу қиынға соғуы мүмкін: ол солай NP аяқталды берілген графиктің бокстылығы ең көп дегенде берілген мәнге ие екендігін тексеру Қ, тіпті үшін Қ = 2.^[7]Chandran, Francis & Sivadasan (2010) а-да болатын өлшемі бар қораптардың қиылысу графикасы ретінде ерікті графиктердің кескіндерін табудың алгоритмдерін сипаттаңыз логарифмдік факторы максималды дәреже графиктің; бұл нәтиже графиктің бокстылығының жоғарғы шегін қамтамасыз етеді.

Табиғи параметрі қиын болғанына қарамастан, боксизм қозғалмайтын параметр параметрімен анықталған кезде шыңның қақпағы енгізу графигінің нөмірі.^[8]

Шектер

Егер график болса G график бар м шеттері, содан кейін: ${displaystyle box (G) = O ({sqrt {mcdot log (m)}})}$ .^[9]^[10]

Егер график болса G болып табылады к-азғындау (бірге ${displaystyle kgeq 2}$ ) және бар n шыңдар, содан кейін G боксизмге ие ${displaystyle box (G) leq (k + 2) lceil 2elog nceil}$ .^[11]

Егер график болса G толық график жоқ т шыңдар а кәмелетке толмаған, содан кейін ${displaystyle box (G) = O (t ^ {2} log t)}$ ^[12] толық графигі жоқ графиктер бар т шыңдар а кәмелетке толмаған және бокспен ${displaystyle Omega (t {sqrt {log t}})}$ .^[13] Атап айтқанда, кез-келген график G xax boxicity ${displaystyle box (G) = O (mu (G) ^ {2} log mu (G))}$ , қайда ${displaystyle mu (G)}$ дегенді білдіреді Колин де Вердие өзгермейтін туралы G.

Байланысты графикалық инварианттар

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

Ескертулер

^ Мысалы, қараңыз Chandran, Francis & Sivadasan (2010) және Чандран және Сивадасан (2007).
^ Шейнерман (1984).
^ Томассен (1986).
^ Беллантони және басқалар. (1993).
^ Chandran, Francis & Sivadasan (2010) бұл графиктердің полиномдық саны болатындығынан шығатынын ескеріңіз максималды клиптер. Барлық максималды клиптерді тиімді тізімдеу үшін қораптың нақты көрінісі қажет емес.
^ Қараңыз, мысалы, Agarwal, van Kreveld & Suri (1998) және Берман және т.б. (2001) жуықтау үшін максималды тәуелсіз жиынтық тіктөртбұрыштардың қиылысу графиктері үшін және Chlebík & Chlebíková (2005) осы мәселелерді жоғары өлшемдерде жуықтау қаттылығы нәтижелері үшін.
^ Коззенс (1981) қорапты есептеу NP аяқталғанын көрсетеді; Яннакакис (1982) қораптың максимум 3 екенін тексеру тіпті NP-қиын екенін көрсетеді; ақыры Краточвил (1994) 2 боксиканы тану NP-қиын екенін көрсетті.
^ Адига, Читнис және Саурабх (2010).
^ Chandran, Francis & Sivadasan (2010)
^ Esperet (2016)
^ Adiga, Chandran & Mathew (2014)
^ Esperet & Wiechert (2018)
^ Esperet (2016)

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

Адига, Абхиджин; Бхоммик, Диптенду; Chandran, L. Sunil (2011), «Boxicity and Poset Dimension», Дискретті математика бойынша SIAM журналы, 25 (4): 1687–1698, arXiv:1003.2357, дои:10.1137/100786290.
Адига, Абхиджин; Шандран, Л.Сунил; Мэттью, Роджерс (2014), «Кубизм, деградация және қиылысу нөмірі», Еуропалық Комбинаторика журналы, 35: 2–12, arXiv:1105.5225, дои:10.1016 / j.ejc.2013.06.021.
Адига, Абхиджин; Читнис, Раджеш; Saurabh, Saket (2010), «Бокс үшін параметрленген алгоритмдер», Алгоритмдер және есептеу: 21-ші халықаралық симпозиум, ISAAC 2010, Чеджу аралы, Корея, 15-17 желтоқсан 2010 ж., Іс жүргізу, І бөлім (PDF), Информатикадағы дәрістер, 6506, 366–377 б., дои:10.1007/978-3-642-17517-6_33, мұрағатталған түпнұсқа (PDF) 2017-08-30, алынды 2018-01-22
Агарвал, Панкай К.; ван Кревельд, Марк; Сури, Субхаш (1998), «тіктөртбұрыштағы максималды тәуелсіз жиынтық бойынша белгіні орналастыру», Есептеу геометриясының теориясы және қолданылуы, 11 (3–4): 209–218, дои:10.1016 / S0925-7721 (98) 00028-5, hdl:1874/18908.
Беллантони, Стивен Дж .; Бен-Арройо Хартман, Ирит; Пзытыцка, Тереза; Ақтар, Сью (1993), «Тордың қиылысу графикасы және бокс», Дискретті математика, 114 (1–3): 41–49, дои:10.1016 / 0012-365X (93) 90354-V.
Берман, Пиотр; ДасГупта, Б .; Мутукришнан, С .; Рамасвами, С. (2001), «Тік төртбұрыштармен қаптау және орау мәселелерін тиімді алгоритмдеу», J. алгоритмдері, 41 (2): 443–470, дои:10.1006 / jagm.2001.1188.
Шандран, Л.Сунил; Фрэнсис, Мэттью С .; Сивадасан, Навин (2010), «Осьтік параллель қораптарды қолданып, төмен өлшемді графиктердің геометриялық көрінісі», Алгоритмика, 56 (2): 129–140, arXiv:cs.DM/0605013, дои:10.1007 / s00453-008-9163-5, МЫРЗА 2576537, S2CID 17838951.
Шандран, Л.Сунил; Сивадасан, Навин (2007), «Бокс пен кеңдік», Комбинаторлық теория журналы, B сериясы, 97 (5): 733–744, arXiv:математика.CO/0505544, дои:10.1016 / j.jctb.2006.12.004, S2CID 9854207.
Хлебик, Мирослав; Хлебикова, Янка (2005), «қиылысу графиктеріндегі оңтайландыру есептерінің қаттылық қаттылығы г.-өлшемді қораптар », Дискретті алгоритмдер бойынша он алтыншы ACM-SIAM симпозиумының материалдары, 267–276 бет.
Коззенс, М.Б (1981), Интервалды графиктердің жоғары және көп өлшемді аналогтары, Ph.D. диссертация, Ратгерс университеті.
Эсперет, Луи (2016), «Бокс және топологиялық инварианттар», Еуропалық Комбинаторика журналы, 51: 495–499, arXiv:1503.05765, дои:10.1016 / j.ejc.2015.07.020, S2CID 5548385.
Эсперет, Луис; Wiechert, Veit (2018), «Boxicity, poset dimension, және кәмелетке толмаған балалар», Комбинаториканың электронды журналы, 25 (4): # P4.51, arXiv:1804.00850, дои:10.37236/7787, S2CID 119148637.
Краточвил, қаңтар (1994), «Қондырғыштықтың арнайы жазықтық проблемасы және оның NP-толықтығы салдары», Дискретті қолданбалы математика, 52 (3): 233–252, дои:10.1016 / 0166-218X (94) 90143-0.
Квест, М .; Вегнер, Г. (1990), «Графиктерді бокспен сипаттау ≤ 2», Дискретті математика, 81 (2): 187–192, дои:10.1016 / 0012-365X (90) 90151-7.
Робертс, Ф. С. (1969), «Графиктің бокстылығы мен кубтылығы туралы», in Тутте, В. Т. (ред.), Комбинаторикадағы соңғы прогресс, Academic Press, 301–310 бет, ISBN 978-0-12-705150-5.
Шейнерман, Э.Р. (1984), Қиылысу кластары және бірнеше қиылысу параметрлері, Докторлық диссертация, Принстон университеті.
Томассен, Карстен (1986), «Пландық графиктердің аралық кескіндері», Комбинаторлық теория журналы, В сериясы, 40: 9–20, дои:10.1016/0095-8956(86)90061-4.
Яннакакис, Михалис (1982), «Ішінара тапсырыс өлшемі проблемасының күрделілігі», SIAM журналы алгебралық және дискретті әдістер туралы, 3 (3): 351–358, дои:10.1137/0603036.

[1] Мысалы, қараңыз Chandran, Francis & Sivadasan (2010) және Чандран және Сивадасан (2007).

[2] Шейнерман (1984).

[3] Томассен (1986).

[4] Беллантони және басқалар. (1993).

[5] Chandran, Francis & Sivadasan (2010) бұл графиктердің полиномдық саны болатындығынан шығатынын ескеріңіз максималды клиптер. Барлық максималды клиптерді тиімді тізімдеу үшін қораптың нақты көрінісі қажет емес.

[6] Қараңыз, мысалы, Agarwal, van Kreveld & Suri (1998) және Берман және т.б. (2001) жуықтау үшін максималды тәуелсіз жиынтық тіктөртбұрыштардың қиылысу графиктері үшін және Chlebík & Chlebíková (2005) осы мәселелерді жоғары өлшемдерде жуықтау қаттылығы нәтижелері үшін.

[7] Коззенс (1981) қорапты есептеу NP аяқталғанын көрсетеді; Яннакакис (1982) қораптың максимум 3 екенін тексеру тіпті NP-қиын екенін көрсетеді; ақыры Краточвил (1994) 2 боксиканы тану NP-қиын екенін көрсетті.

[8] Адига, Читнис және Саурабх (2010).

[9] Chandran, Francis & Sivadasan (2010)

[10] Esperet (2016)

[11] Adiga, Chandran & Mathew (2014)

[12] Esperet & Wiechert (2018)

[13] Esperet (2016)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]