Кіріспе

Алгебралық граф теориясындағы функция. Хроматикалық полином – математиканың алгебралық граф теориясы саласында зерттелетін граф полиномы. Ол бояудың мүмкін санының түстер санына тәуелділігін көрсетеді және бастапқыда Джордж Дэвид Биркофф төрт түстің мәселесін зерттеу үшін анықтаған. Кейіннен Хаслер Уитни мен В. Т. Тютте оны Тютте полиномына жалпылады, осылайша оны статистикалық физиканың Поттс моделімен байланыстырды.

Тарих

Джордж Дэвид Биркофф 1912 жылы төрт түстің теоремасын дәлелдеуге тырысып, жазықтық графтар үшін ғана хроматикалық полиномды енгізді. Егер G графигін k түспен дұрыс бояудың мүмкіндіктерінің санын білдірсе, онда барлық жазықтық графтар үшін көрсету арқылы төрт түстің теоремасын дәлелдеуге болады. Осылайша ол полиномдардың түбірлерін зерттеуге арналған талдау және алгебраның қуатты құралдарын комбинаторлық бояу мәселесіне қолдануды жоспарлады. Хаслер Уитни 1932 жылы Биркоффтың полиномын жазықтық жағдайынан жалпы графтарға кеңейтті. 1968 жылы Рональд К. Рид, қандай полиномдар кейбір графтардың хроматикалық полиномдары болып табылады деген сұрақ қойды, бұл сұрақ әлі де ашық күйде және хроматикалық эквивалентті графтар тұжырымын енгізді. Бүгінде хроматикалық полиномдар алгебралық граф теориясының маңызды объектілерінің бірі болып табылады.

Анықтама

G графигі үшін оның (тура) төбелік k түстеуінің санын есептейді. Басқа жиі қолданылатын белгілер: , , немесе . Кез келген k ≥ 0 бүтін санында есептелгенде , -қа тең болатын бірегей полином бар; оны G графигінің хроматикалық полиномы деп атайды.

Мысалы, 3 төбесі бар жол графигін k түспен бояу үшін, бірінші төбеге k түстің кез келгенін, екінші төбеге қалған түстердің кез келгенін, ал үшінші төбеге екінші төбе таңдаған түстен өзгеше түстің кез келгенін таңдауға болады. Сондықтан, -ның k түстеуінің саны. x айнымалы үшін (қажетті түрде бүтін сан емес), бізде бар. (Түстерді ауыстыру арқылы немесе G графигінің автоморфизмдері арқылы ғана ерекшеленетін түстеулер де әртүрлі деп есептеледі.)

Хроматикалық балама

Екі графтың хроматикалық эквивалентті екені айтылады, егер олардың хроматикалық полиномдары бірдей болса. Изоморфты графтардың хроматикалық полиномдары бірдей, бірақ изоморфты емес графтар хроматикалық эквивалентті болуы мүмкін. Мысалы, n төбесі бар барлық ағаштардың хроматикалық полиномдары бірдей. Атап айтқанда, бұл 4 төбесі бар тырнақ графтері мен жол графтерінің хроматикалық полиномдары. Граф, егер оның хроматикалық полиномы бойынша, изоморфизмге дейін анықталса, хроматикалық жағынан бірегей болып табылады. Яғни, егер G хроматикалық жағынан бірегей болса, онда G мен H изоморфты екенін білдіреді. Барлық циклдық графтар хроматикалық жағынан бірегей.

Санаттауы

Хроматикалық полиномиал Хованов гомологиясымен тығыз байланысты гомология теориясы арқылы категорияланады.

Тиімді алгоритмдер

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

Жою қысқарту

Делециялы жиырылу қайталануы хроматикалық полиномиалды есептеудің жою-қысылу алгоритмі деп аталатын әдісін ұсынады. Бірінші түрінде (минус белгісімен) қайталану бос графтар жиынымен аяқталады. Екінші түрінде (плюс белгісімен) ол толық графтар жиынымен аяқталады. Бұл көптеген графтарды бояу алгоритмдерінің негізін құрайды. Компьютерлік алгебра жүйесі Mathematica-ның Combinatorica пакетіндегі ChromaticPolynomial функциясы, граф тығыз болса екінші қайталануды, ал граф сирек болса бірінші қайталануды қолданады. Ең нашар жағдайда кез келген формуланың орындалу уақыты Фибоначчи сандарының қайталану қатынасына сәйкес келеді, сондықтан ең нашар жағдайда алгоритм n төбесі және m қабырғасы бар граф үшін полиномдық фактор ішінде уақыт ішінде орындалады. Талдау кіріс графтың өрілетін ағаштары санының полиномдық коэффициентіне дейін жақсартылуы мүмкін. Іс жүзінде, кейбір рекурсивті шақырулардан аулақ болу үшін тармақталу және шектеу стратегиялары, сондай-ақ граф изоморфизмін қабылдамау қолданылады, ал орындалу уақыты төбе жұптарын таңдау үшін қолданылатын эвристикаға байланысты.

Куб әдісі

Графтарды түстерге табиғи геометриялық тұрғыдан қарауға болады, себебі графтың түсі – әрбір төбесіне натурал сандарды тағайындау арқылы, бүтін сандар торшасындағы вектор болып табылады. Екі төбе бір түспен боялса, бұл түс вектордағы сәйкес координаталардың теңдігімен анықталады, сондықтан әр қабырға гипержазықтықпен байланыстырылуы мүмкін. Белгілі бір граф үшін мұндай гипержазықтықтар жиынтығы оның графикалық аранжировкасы деп аталады. Графтың дұрыс түсі – бұл тыйым салынған гипержазықтықтардан қашатын тордағы нүктелер. Егер түстер санымен шектелсек, онда тордағы нүктелер текшеге сыяды. Осы контексте, хроматикалық полином графикалық аранжировкадан қашатын текшедегі тор нүктелерінің санын есептейді.