Гамильтон циклінің көпмүшесі - Hamiltonian cycle polynomial

Математикада Гамильтон циклінің көпмүшесі туралы n×n-матрица - матрицаның жазбаларындағы көпмүшелік, ретінде анықталады

${ displaystyle operatorname {ham} (A) = sum _ { sigma in H_ {n}} prod _ {i = 1} ^ {n} a_ {i, sigma (i)}}$

қайда ${ displaystyle H_ {n}}$ жиынтығы n-ауыстыру дәл бір циклге ие.

Бұл алгебралық нұсқа, бірқатар жағдайда, а бар екенін анықтауға пайдалы Гамильтон циклі ішінде бағытталған граф.

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

Ішінде (Knezevic & Cohen (2017) ) бұл көрсетілді

${ displaystyle operatorname {ham} (A) = sum _ {J subseteq {2, dots, n }} det (-A_ {J}) operatorname {per} (A _ { bar {) J}})}$

қайда ${ displaystyle A_ {J}}$ субматрицасы болып табылады ${ displaystyle A}$ жолдары мен бағандары арқылы келтірілген ${ displaystyle A}$ индекстелген ${ displaystyle J}$, және ${ displaystyle { bar {J}}}$ толықтауыш болып табылады ${ displaystyle J}$ жылы ${ displaystyle {1, dots, n }}$, ал бос субматриканың детерминанты 1-ге теңестірілген.

Осыған және Борчардттың жеке ерекшеліктеріне байланысты сингулярлы емес үшін n×n Коши матрицасы ${ displaystyle C (x, y)}$ ${ displaystyle operatorname {ham} (C (x, y)) = { det} (- D_ {1} ^ {2} C ^ {* 2} (x, y) D_ {2} ^ {2} + I _ {/ 1}) оператор атауы {det} (C (x, y))}$ қайда ${ displaystyle D_ {1}, D_ {2}}$ матрицалар құрайды ${ displaystyle D_ {1} C (x, y) D_ {2}}$ унитарлық (нақты өрісте немесе ақырлы сипаттамалық өрісте немесе күрделі сандар өрісінде ортогоналды), ${ displaystyle C ^ {* 2} (x, y)}$ - бұл Хадамар (кіру әдісі бойынша) квадраты ${ displaystyle C (x, y)}$, және ${ displaystyle I _ {/ 1}}$ сәйкестілік n×n-1, индекстерді 0-ге ауыстыратын матрица.

2 сипаттамасының өрісінде теңдік ${ displaystyle operatorname {ham} (A) = sum _ {J subseteq {2, dots, n }} det (-A_ {J}) operatorname {per} (A _ { bar {) J}})}$ айналады ${ displaystyle operatorname {ham} (A) = sum _ {J subseteq {2, dots, n }} det (A_ {J}) det (A _ { bar {J}}) }$ сондықтан кез-келген унитарлы матрицаның Гамильтон циклының полиномын есептеу үшін полиномдық уақытты алуға мүмкіндік береді ${ displaystyle U}$ (яғни солай ${ displaystyle U ^ {T} U = I}$ қайда ${ displaystyle I}$ сәйкестілік n×n-матрица), өйткені мұндай өрісте унитарлы матрицаның әрбір миноры оның алгебралық комплементімен сәйкес келеді: ${ displaystyle operatorname {ham} (U) = { det} ^ {2} (U + I _ {/ 1})}$ қайда ${ displaystyle I _ {/ 1}}$ сәйкестілік n×n- матрица, индекстерді енгізу арқылы 1,1. 0-ге ауыстырылады. Демек, полиномдық уақытты сипаттамалық өрістен диграф доғаларына салмақ тағайындау мүмкін болса, оның салмақталған іргелес матрицасын унитарлы етеді және нөлге тең емес гамильтон циклына ие болады. онда диграф Гамильтондық болады. Сондықтан Гамильтон циклінің есебі көпмүшелік уақыттағы осындай графиктерде есептелінеді.

2 сипаттамасында, ан-дың Гамильтон циклінің көпмүшесі n×n-матрица нөлге тең, егер n > 2k, мұндағы k - оның дәрежесі немесе егер ол еріксіз болса және n > 1.

Сонымен қатар, ерікті сақинада ${ displaystyle R}$ оның сипаты кез-келген қисық-симметриялы үшін тіпті табиғи сан емес n×n-матрица ${ displaystyle A}$ формальды айнымалы қуат дәрежесі бар ${ displaystyle varepsilon}$ ${ displaystyle U ( varepsilon) = sum _ {n = 0} ^ { infty} U_ {n} varepsilon ^ {n}}$ бұл унитарлы n×n-матрица аяқталды ${ displaystyle R сол жақта ( varepsilon оң жақта)}$ және ${ displaystyle U_ {0} = I}$, ${ displaystyle U_ {1} = A}$, кез келген үшін ${ displaystyle U ( varepsilon)}$ осы шарттарды қанағаттандыру ${ displaystyle operatorname {ham} (A)}$ коэффициентіне тең ${ displaystyle n}$- қуат ${ displaystyle varepsilon}$ қуат сериясында ${ displaystyle operatorname {ham} (U ( varepsilon))}$. Және кез-келген сақина үшін ${ displaystyle R}$ диагоналі болған кезде де дәл сипаттамаға сәйкес келеді ${ displaystyle A ^ {2}}$ 2-ге еселік болып табылады. Бұл дегеніміз, компьютердің дейін ${ displaystyle n}$- қуат ${ displaystyle varepsilon}$, унитарлы Гамильтон циклының көпмүшесі n×n-қандай да бір сипаттамалық сақинаның формальды айнымалы бойынша шексіз кеңеюінің үстіндегі матрица (міндетті түрде жай емес) ${ displaystyle varepsilon}$ Бұл #${ displaystyle _ {q}}$P-аяқталды егер болса ${ displaystyle q}$ 2 емес және а-ның Гамильтон циклінің көпмүшесін есептейді ${ displaystyle k}$- жартылай унитарлы матрица (яғни n×n-матрица ${ displaystyle V}$ осындай ${ displaystyle operatorname {rank} (V ^ {T} V-I ,) = k}$) 2 сипаттамасының кез-келген сақинасының осындай кеңеюі а #${ displaystyle _ {2}}$P-аяқталды кез келген проблема ${ displaystyle k}$ > 0 (өйткені кез келген ${ displaystyle k}$-жарты унитарлы матрицаны жою арқылы унитарлы матрицадан алуға болады ${ displaystyle k}$ жолдар және ${ displaystyle k}$ бағандар). Үшін ${ displaystyle k = 1}$ соңғы мәлімдеме # ретінде қайта тұжырымдалуы мүмкін${ displaystyle _ {2}}$Берілген унитар үшін есептеудің толықтығы n×n-матрица ${ displaystyle U}$ 2 сипаттамасының өрісі бойынша n×n-матрица ${ displaystyle H (U)}$ кімдікі мен,j-ші жазба - алынған матрицаның Гамильтон циклының көпмүшесі ${ displaystyle U}$ оның жолдары мен бағандарын кез-келген ауыстыру картасымен ауыстыру арқылы мен дейін 1 және j дейін 2 содан кейін оны алып тастаңыз 1- қатар және 2-nd баған (яғни сәйкес салмақты диграфтың Гамильтондық патектерінің доға салмақтары көбейтінділерінің қосындысы j дейін мен) үшін мен ≠ j және нөл үшін мен = j. Бұл матрица матрица теңдеуін қанағаттандырады ${ displaystyle U (H (U)) ^ {T} = H (U) U ^ {T}}$, ал ${ displaystyle operatorname {ham} left ({ begin {matrix} U & {Ua} a ^ {T} & 0 end {matrix}} right) = (a_ {1} ^ {2} +. .. + a_ {n} ^ {2}) operatorname {ham} (U)}$ қайда ${ displaystyle a}$ n-вектор болып табылады.

Сонымен қатар, 2-сипаттамада Гамильтон циклінің көпмүшелігінің инвариантты матрицалық сығымдары бар екендігін (детерминант үшін инвариантты болып табылатын Гаусс модификациясына ішінара ұқсас) ие екендігін ескерген жөн. ${ displaystyle operatorname {ham} (X) = 0}$ кез келген үшін т×т-матрица ${ displaystyle X}$ үш бірдей қатардың болуы немесе, егер ${ displaystyle t}$ > 2, i, j индекстерінің жұбы, оның i-ші және j-ші жолдары бірдей, ал i-ші және j-ші бағандары бірдей болады.

Егер матрицада индекстері бар екі тең жол болса мен және j содан кейін біреуін кез келген үшіншіге қосу бұл көпмүшені 2 сипаттамасында өзгертпейді, бұл Гаусс стилінде оның барлық жазбаларын жоюға мүмкіндік береді мен-ден басқа баған мен,мен-ші және j,мен- үшінші (егер олар нөлге тең болмаса) және оны алып тастаңыз мен- баған және j- үшінші қатар (жоғарыда сипатталған тәсілмен) - онда бастапқы матрицаның Гамильтон циклінің көпмүшесі жаңасының осы көпмүшесіне бастапқыға көбейтілгенге тең болады j,мен- кіру.

Сондай-ақ, 2 сипаттамасында және екіден көп қатарлы матрицалар үшін Гамильтон циклының көпмүшесін қосу арқылы өзгертпейді мен-ге дейінгі баған j- матрицадағы үшіншісі, онда мен-ші және j-ші қатарлар бірдей, әсіресе сәйкестікті береді

${ displaystyle det (D + D ^ {- 1}) оператор атауы {ham} сол ({ бастау {матрица} V&A B&U соңы {матрица}} оң) = оператор атауы {ham} сол ({ begin {matrix} V & V + D & A V + D ^ {- 1} & V + D ^ {- 1} + D & A B & B & U end {matrix}} right)}$

үшін n×n-матрица ${ displaystyle U}$, м×м-матрицалар ${ displaystyle V}$ және қиғаш ${ displaystyle D}$, м×n-матрица ${ displaystyle A}$ және n×м-матрица ${ displaystyle B}$.

Бұл сәйкестіктің іс бойынша шектеуі ${ displaystyle U}$ унитарлы, ${ displaystyle VD + DV ^ {T} + AA ^ {T} = I + D ^ {2}}$ және ${ displaystyle BD = UA ^ {T}}$, қайда ${ displaystyle I}$ сәйкестілік м×м-матрица, құрайды (2м+n)×(2м+n) -матрица теңдіктің оң жағындағы унитарлы және оның Гамильтон циклінің есептелетін полиномы, сондықтан көпмүшелік уақыт бойынша жоғарыда келтірілген унитарлы матрицаның Гамильтон циклі полиномына арналған формуланы жалпылайды. Сонымен қатар, X, Y матрицалары үшін 2 сипаттамасында ${ displaystyle operatorname {ham} left ({ begin {matrix} X&Y Y&X end {matrix}} right)}$ - X, Y-тің матрицасының Гамильтониялық циклінің полиномына көбейтілген, Y, i-тің кіруінің барлық тең емес i, j индекстерінің үстіндегі қосындысының квадраты. мен-ші қатар және j- баған (жоғарыда сипатталған тәртіппен). Демек, жоғарыдағы A = B және U = V теңдіктерін қойып, Гамильтон циклінің көпмүшесі көпмүшелік уақытта есептелетін унитарлы матрицалар класының тағы бір кеңеюін аламыз.

Жоғарыда аталған қысу түрлендірулерінен басқа, 2 сипаттамасында келесі қатынас матрицаның Гамильтон циклының көпмүшелері және оның ішінара кері күші үшін де жарамды (үшін ${ displaystyle A_ {11}}$ және ${ displaystyle A_ {22}}$ төрт бұрышты, ${ displaystyle A_ {11}}$ болу төңкерілетін ):

${ displaystyle operatorname {ham} left ({ begin {matrix} A_ {11} & A_ {12} A_ {21} & A_ {22} end {matrix}} right) = { det} ^ {2} солға (A_ {11} оңға) оператор атауы {ham} солға ({ бастау {матрица} A_ {11} ^ {- 1} және A_ {11} ^ {- 1} A_ {12} A_ {21} A_ {11} ^ {- 1} және A_ {22} + A_ {21} A_ {11} ^ {- 1} A_ {12} end {matrix}} right)}$

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

Демек, полиномдық уақытта орындалатын және 2 сипаттамасында Гамильтон циклының көпмүшесін сақтайтын матрицалық қысу операторларының әртүрлілігі бар, олардың тізбекті қолданылуы транспозалық трансформациямен бірге (операторлар матрицаны бүтін қалдырған сайын қолданылады) әр матрица үшін қысуды жабу операторы ретінде анықтауға болатын белгілі бір шек. Матрица кластарына қолданылған кезде, сол оператор бір класты екінші класта салыстырады. Бұл дәлелденгендей (Knezevic & Cohen (2017) ), егер қысуды жабу операторы унитарлы матрицалар класын барлық квадрат матрицалар жиынтығына сипаттаманың шексіз өрісі 2 бойынша бейнелейтін болса, онда Гамильтон циклінің көпмүшесі осы сипаттаманың кез-келген өрісі бойынша полиномдық уақытта есептелетін болады, бұл теңдікті білдіреді.RP = NP.

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

• Кнезевич, Анна; Коэн, Грег (2017), Соңғы сипаттамадағы тұрақты заттар туралы кейбір фактілер, arXiv:1710.01783, Бибкод:2017arXiv171001783K.

• Коган, Григорий (1996), «3 сипаттамалық өрістер бойынша тұрақты есептеу: қайда және неге қиын болады», Информатика негіздеріне арналған 37-ші жыл сайынғы симпозиум (FOCS '96): 108–114, дои:10.1109 / SFCS.1996.548469, ISBN  0-8186-7594-2

• Коэн, Грег (2010), Гамильтондық ыдыраудың 2 графикалық жиек жиынтығының және осыған ұқсас бөлімдерінің модулін 2 есептеудің полиномдық уақытына арналған жаңа алгебралық әдістемесі, arXiv:1005.2281, Бибкод:2010arXiv1005.2281C