Кіріспе
Алгебралық түрде график байланысын кодтау
графиктің Тютте полиномиалы
the Tutte polynomial of a graph
Тютте полиномиалы, сондай-ақ дихромат немесе Тютте–Уитни полиномиалы деп аталады, ол график полиномиалы. Бұл граф теориясында маңызды рөл атқаратын екі айнымалыдағы полиномиал. Ол кез келген бағытталмаған график үшін анықталады және график қалай байланысқандығы туралы ақпаратты қамтиды. Бұл полиномияның маңыздылығы оның қамтитын ақпараттан туындайды. Алғашқыда алгебралық граф теориясында график бояуы және нөлдік ағынға қатысты есептерді жалпылау ретінде зерттелгенімен, ол түйін теориясынан Джонс полиномиалы және статистикалық физикадан Поттс моделінің бөлу функциялары сияқты басқа ғылымдардан алынған бірнеше белгілі мамандануларды қамтиды. Бұл сонымен қатар теориялық компьютерлік ғылымдағы бірнеше маңызды есептеу проблемаларының көзі болып табылады. Тютте полиномиалының бірнеше эквивалентті анықтамалары бар. Ол негізінен Уитнидің рангілік полиномиалына, Тюттенің өзінің дихроматикалық полиномиалына және Фортуин–Кастелейнның қарапайым түрлендірулер бойынша кездейсоқ кластерлік моделіне тең. Бұл негізінен белгілі бір мөлшердегі жиектер жиынтығының және байланысты компоненттердің санын анықтайтын туынды функция, матроидтарға тікелей жалпылау ретінде қолданылады. Бұл сонымен қатар өшіру-жайлау рекурсиясы арқылы анықталатын ең жалпы график инварианты. Граф теориясы және матроид теориясы туралы көптеген оқулықтар осы полиномиалға арналған жеке тарауларды қамтиды.
The importance of this polynomial stems from the information it contains about Though originally studied in algebraic graph theory as a generalization of counting problems related to graph coloring and nowhere zero flow, it contains several famous other specializations from other sciences such as the Jones polynomial from knot theory and the partition functions of the Potts model from statistical physics. It is also the source of several central computational problems in theoretical computer science. The Tutte polynomial has several equivalent definitions. It is essentially equivalent to Whitney’s rank polynomial, Tutte’s own dichromatic polynomial and Fortuin–Kasteleyn’s random cluster model under simple transformations. It is essentially a generating function for the number of edge sets of a given size and connected components, with immediate generalizations to matroids. It is also the most general graph invariant that can be defined by a deletion–contraction recurrence. Several textbooks about graph theory and matroid theory devote entire chapters to it.
(0,2)
G графигінің берік байланысқан бағыттарының санын есептейді.
(2,2)
– бұл G графигінің жиектерінің саны, мұнда – жиектер саны.
Сенімділік полиномы
, Тютте полиномы желі теориясында зерттелетін барлық терминалдық сенімділік полиномына толыққанды түрленеді. Қосылған G графы үшін p ықтималдығымен барлық қабырғаларды жойыңыз; бұл кездейсоқ қабырғалардың бұзылуына ұшыраған желіні моделеуге арналған. Онда сенімділік полиномы – p-ге қатысты полином түріндегі функция, ол G графындағы кез келген екі төбе арасындағы байланыстың қабырғалардың бұзылуынан кейін сақталу ықтималдығын көрсетеді. Тютте полиномымен байланыс келесідей беріледі:
Дихроматикалық көптік
Тютте сонымен қатар хроматикалық полиномияның екі айнымалыға кеңейтілген түрін, графтың дихроматикалық полиномиясын анықтады. Ол былай беріледі:
where is the number of connected components of the spanning subgraph (V,A). This is related to the corank nullity polynomial by
The dichromatic polynomial does not generalize to matroids because k(A) is not a matroid property: different graphs with the same matroid can have different numbers of connected components.
мұнда (V,A) аралық субграфтың байланысты компоненттерінің саны. Бұл коранк-нөлдік полиноммен байланысты. Дихроматикалық полиномиал матроидтарға жалпыланбайды, себебі k(A) матроидтың қасиеті емес: бірдей матроидқа ие әртүрлі графтарда байланысты компоненттердің саны әртүрлі болуы мүмкін.
where is the number of connected components of the spanning subgraph (V,A). This is related to the corank nullity polynomial by
The dichromatic polynomial does not generalize to matroids because k(A) is not a matroid property: different graphs with the same matroid can have different numbers of connected components.
Мартин полиномы
Бағытталған 4-реттеулі графтың Мартин полиномы Пьер Мартин 1977 жылы анықталды. Ол, егер G жазықтық граф болса және оның бағытталған медианалық графы болса, онда
Гаусс жоюы
Кейбір шектеулі жағдайларда Тютте полиномиалы полиномиалдық уақытта есептелуі мүмкін, себебі Гаусс жоюы матрицалық операцияларды – детерминантты және Пфаффианды – тиімді есептейді. Бұл алгоритмдердің өзі алгебралық графтар теориясы мен статистикалық механиканың маңызды нәтижелері болып табылады. Бұл байланысты графтың аралықтағы ағаштарының санына тең. Бұл, G графының Лаплас матрицасының ең үлкен негізгі субматрицасының детерминанты ретінде полиномиалдық уақытта есептелуі мүмкін, бұл алгебралық графтар теориясының Кирхгоффтың матрица-ағаш теоремасы ретінде белгілі ерте нәтижесі. Сол сияқты, велосипедтік кеңістіктің өлшемі Гаусс жою арқылы полиномиалдық уақытта есептелуі мүмкін. Жазық графтар үшін Айсинг моделінің бөлініс функциясы, яғни гиперболадағы Тютте полиномиалы, Пфаффиан түрінде берілуі мүмкін және FKT алгоритмі арқылы тиімді есептелуі мүмкін. Бұл идеяны Фишер, Кастелейн және Темперли жазық торлы модельдің димерлік жабындарының санын есептеу үшін дамытты.
computable in polynomial time as the determinant of a maximal principal submatrix of the Laplacian matrix of G, an early result in algebraic graph theory known as Kirchhoff’s Matrix–Tree theorem. Likewise, the dimension of the bicycle space at can be computed in polynomial time by Gaussian elimination. For planar graphs, the partition function of the Ising model, i. e., the Tutte polynomial at the hyperbola , can be expressed as a Pfaffian and computed efficiently via the FKT algorithm. This idea was developed by Fisher, Kasteleyn, and Temperley to compute the number of dimer covers of a planar lattice model.
Марков тізбегі Монте-Карло
Марков тізбегі Монте-Карло әдісін қолдану арқылы Тютте полиномын оң тармағы бойынша кез келген дәлдікпен жуықтауға болады, бұл ферромагниттік Исинг моделінің бөліну функциясына баламалы. Бұл, Исинг моделі мен графтардағы сәйкестіктерді санау арасындағы тығыз байланысты пайдаланады. Джеррум мен Синклердің бұл маңызды нәтижесінің негізі – кіріс графтың сәйкестіктері күйлер болатын Марков тізбегін құру. Тізбектің өтулері кездейсоқ жиектерді таңдау және сәйкестікті оған сәйкес өзгерту арқылы анықталады. Нәтижедегі Марков тізбегі жылдам араласады және "жетілдірілген кездейсоқтыққа" ие сәйкестіктерге әкеледі, оларды кездейсоқ сынама алу арқылы бөліну функциясын қалпына келтіру үшін қолдануға болады. Алынған алгоритм – толық полиномиалдық уақыттағы кездейсоқ жуықтау схемасы (fpras).
Дәл есептеу
Егер x және y екеуі де теріс емес бүтін сандар болса, мәселе #P класына жатады. Жалпы бүтін сандар жұптары үшін Тютте полиномиалы теріс мүшелерді қамтиды, бұл мәселені GapP күрделілік класына жатқызады, ол #P-нің азайту операциясы бойынша жабық классы. Рационалдық координаталарды қарастыру үшін #P-нің рационалдық аналогын анықтауға болады. Кез келген мән үшін, дәл есептеудің есептеу күрделілігі екі классқа жатады. Егер мәселе гипербола бойында жатпаса немесе полиномиалдық уақытта есептелетін нүктелердің бірі болмаса, ол #P қиын болады. Егер мәселе жазық графтар класына шектелсе, гипербола бойындағы нүктелер де полиномиалдық уақытта есептелуі мүмкін. Барлық басқа нүктелер, тіпті екі бөлікті жазық графтар үшін де, #P қиын болып қалады. Жазық графтар үшін дихотомия туралы еңбегінде Вертиган (қорытындысында) осы нәтиже ең көп дегенде үш дәрежелі төбелері бар графтарға шектеу қойылғанда да сақталады дейді, тек нөлдік Z3 ағындарын есептемейтін және полиномиалдық уақытта есептелетін нүктеден басқа. Бұл нәтижелерде бірнеше маңызды ерекше жағдайлар бар. Мысалы, Исинг моделінің бөлініс функциясын есептеу мәселесі жалпы жағдайда #P қиын, тіпті Онсагер мен Фишердің белгілі алгоритмдері оны жазық торлар үшін шешеді. Сондай-ақ, Джонс полиномиалының есептелуі #P қиын. Соңында, жазық графтың төрт түспен боялуының санын есептеу #P толық, бірақ шешімдік мәселе төрт түс теоремасы бойынша тривиальды. Керісінше, жазық графтар үшін үш түспен боялу санын санау #P толық екенін көру оңай, өйткені шешімдік мәселе парсимониус азайту арқылы NP толық екені белгілі.
The computational complexity of exactly computing falls into one of two classes for any The problem is #P hard unless lies on the hyperbola or is one of the points
in which cases it is computable in polynomial time. If the problem is restricted to the class of planar graphs, the points on the hyperbola become polynomial time computable as well. All other points remain #P hard, even for bipartite planar graphs. In his paper on the dichotomy for planar graphs, Vertigan claims (in his conclusion) that the same result holds when further restricted to graphs with vertex degree at most three, save for the point , which counts nowhere zero Z3 flows and is computable in polynomial time. These results contain several notable special cases. For example, the problem of computing the partition function of the Ising model is #P hard in general, even though celebrated algorithms of Onsager and Fisher solve it for planar lattices. Also, the Jones polynomial is #P hard to compute. Finally, computing the number of four colorings of a planar graph is #P complete, even though the decision problem is trivial by the four color theorem. In contrast, it is easy to see that counting the number of three colorings for planar graphs is #P complete because the decision problem is known to be NP complete via a parsimonious reduction.
Тақырыбы
Қай нүктелерге жақсы жуықтау алгоритмі қолданылатыны туралы сұрақ жан-жақты зерттелген. Полиномдық уақытта нақты есептеуге болатын нүктелерден басқа, белгілі жалғыз жуықтау алгоритмі – Джеррум мен Синклердің FPRAS-ы, ол y > 0 үшін «Изинг» гиперболасындағы нүктелерге қатысты жұмыс істейді. Егер кіріс графтары тығыз мысалдармен шектелсе, яғни дәрежесі болса, онда x ≥ 1, y ≥ 1 жағдайында FPRAS бар. Нақты есептеуге қарағанда жағдай осылай жақсы түсінілмесе де, жазықтықтың кең аудандарының жуықтау қиын екені белгілі.