Хроматичен полином - Голямата енциклопедия на нефта и газа, статия, страница 2

Хроматичен полином

Докажете, че G е дърво с n върха тогава и само ако Pa ( K) k ( k - 1); изведете от това, че даденият полином може да бъде хроматичен полином на повече от една графика. Възможно ли е да се намери полином, който да отговаря на условията на ex. [16]

Съотношението / ( Г) / ( Г) / ( Г) се нарича отношение на Тамма. Ако хроматичният полином се замени с полином / ( Γ) ( - 1) k Xr, където Y ( Γ) е броят на върховете на графиката Γ, тогава такъв полином ще удовлетворява отношението на Тата. Необходимо е само правилно да се разбере свиването на реброто в отношението Tatta. При такова свиване могат да се появят множество ръбове. И ако свием един от простите ръбове, тогава останалите се превръщат в бримки. [18]

Дужин отбеляза, че хроматичният полином Xm ) ( 0 α α на пресечните точки F ( D) е претеглена система. [20]

От тази връзка, по-специално, следва, че Xp ( 0 е полином. Наистина, тази връзка последователно редуцира изчисляването на хроматичен полином до графики с по-малък брой ръбове и по този начин до изчисляването на хроматичен полином на графика без ръбове изобщо. [22]

Ясно е, че всеки две изоморфни графики имат един и същ хроматичен полином. Въпреки това, често множество неизоморфни графики също споделят един и същ хроматичен полином. [23]

Тута, например, неговата обширна теория за изброяване на равнинни обекти и хроматични полиноми на карти, неговата теорема за Хамилтоновите цикли в четирисвързани равнинни графи, хипотезата за 5 потока (виж раздел. Извикването на второстепенни елементи поставя началото на изследването (наред с много други обекти и проблеми) на хипотезата за пълно квазиподреждане на набор от графики чрез връзката, която е непълнолетно лице (вижте забележка 1 в сек. Търсения,че преследването в тази посока от Seymour и Robertson (бивш студент на проф. Tutta) изглежда обещава интересни резултати. Някои от тези (и други) теми може да осигурят обширен материал за следващия том, ако професор Тат или някой, тясно свързан с него в идеологически смисъл, реши да напише такава книга. [24]

По очевидни причини MC(A) се нарича хроматичен полином на графиката G. Ако нямаме лесен начин за изчисляване на стойностите на μ, тогава намирането на полинома MC(A) се превръща в трудна задача. Хроматичните полиноми са въведени от Birkhoff и Lewis [2], докато изучават проблема с четирите цвята. Добре е да повторите някои от доказателствата на Рийд, използвайки свойствата на u-функцията. [27]

В тази глава, след дефиниране на оцветяването на графика и нейното хроматично число, ние представяме доказателството на теоремата за петте цвята и след това обсъждаме хипотезата за четирите цвята. Ние изучаваме тясната връзка между хомоморфизмите и оцветяването. Главата завършва с описание на свойствата на хроматичния полином. [28]

Проблемът за описване на графики, които имат един и същ хроматичен полином, остава нерешен. По-общ нерешен проблем е да се намери необходимо и достатъчно условие полиномът да бъде хроматичен. Например полиномът t - 3 / 3 3 2 има всички известни свойства на хроматичен полином, но не е хроматичен. [29]

Лесно е да се изведе от горното доказателство, че ако графът G има n върха, тогава степентана полинома PQ ( k) е равно на n, тъй като на всяка стъпка не се появяват нови върхове. Освен това, тъй като конструкцията, която описахме, генерира само един пълен граф с n върха, коефициентът на k е равен на единица. G, и че знаците на коефициентите се редуват. Ако изобщо нямаме цветове, тогава не можем да оцветим графиката и следователно постоянният член на хроматичния полином трябва да е равен на нула. [тридесет]