Хроматический многочлен
Cтраница 2
Докажите, что G является деревом с п вершинами тогда и только тогда, когда Ра ( К) k ( k - 1); выведите отсюда, что данный многочлен может быть хроматическим многочленом более чем одного графа. Можно ли найти многочлен, удовлетворяющий условиям упр. [16]
В этой монографии освещается много центральных тем, которые можно рассчитывать найти в книге по теории графов - например, теорема Менгера и потоки в сетях, проблема восстановления, матричная теорема о деревьях, теория факторов ( или паросочетаний) для графов ( созданная в значительной степени самим профессором Таттом), хроматические многочлены, теорема Брукса, теорема Гринберга, пленарные графы, теорема Куратовского. Но это ни в коем случае не еще одна книга по теории графов, ибо излагаемый материал связывается в единое целое глубоко индивидуальным подходом профессора Татта. Кроме того, самые обычные темы преподносятся с некоторыми приятными сюрпризами, такими, как принадлежащая автору изящная теория разложения графов на трехсвязные 3-блоки ( кроме монографии [5], ее ни в какой книге не найдешь), интересный, замечательный подход к электрическим цепям и - быть может, самое примечательное - классификационная теорема для замкнутых поверхностей. Обычно эту теорему относят к топологии, но проф. Татт демонстрирует нам, что она отлично подходит для работы по теории графов - комбинаторная по своей сущности природа рассуждений здесь, действительно, на месте. [17]
Соотношение / ( Г) / ( Г) / ( Г) называют соотношением Tamma. Если хроматический многочлен заменить на многочлен / ( Г) ( - 1) к Хг где У ( Г) - число вершин графа Г, то такой многочлен будет удовлетворять соотношению Татта. Нужно только правильно понимать стягивание ребра в соотношении Татта. При таком стягивании могут появляться кратные ребра. А если мы стягиваем одно из простых ребер, то остальные превращаются в петли. [18]
 |
Граф пересечений.| Две операции над графом. [19] |
Дужин заметил, что хроматический многочлен Хгш) ( 0 ФаФа пересечений F ( D) является весовой системой. [20]
 |
Граф пересечений.| Две операции над графом. [21] |
Из этого соотношения, в частности, следует, что Хр ( 0 - - многочлен. Действительно, это соотношение последовательно сводит вычисление хроматического многочлена к графам с меньшим числом ребер и, тем самым, - к вычислению хроматического многочлена графа вообще без ребер. [22]
Ясно, что каждые два изоморфных графа имеют один и тот же хроматический многочлен. Однако часто несколько неизоморфных графов также имеют один и тот же хроматический многочлен. [23]
Татта, например, его обширную теорию перечисления планарных объектов и хроматические многочлены карт, его теорему о гамиль-тоновых циклах в четырехсвязных планарных графах, гипотезу о 5-потоке ( см. разд. Привлечение миноров создает предпосылки для исследования ( среди многих других объектов и проблем) гипотезы о полном квазиупорядочении множества графов посредством отношения быть минором ( см. замечание 1 в разд. Поиски, ведущиеся в этом направлении Сеймором и Робертсоном ( бывшим студентом проф. Татта), по-видимому, обещают интересные результаты. Некоторые из указанных ( и других) тем могут дать обширный материал для следующего тома, если профессор Татт или кто-либо, тесно связанный с ним в идейном плане, решит написать такую книгу. [24]
 |
Граф пересечений.| Две операции над графом. [25] |
Из этого соотношения, в частности, следует, что Хр ( 0 - - многочлен. Действительно, это соотношение последовательно сводит вычисление хроматического многочлена к графам с меньшим числом ребер и, тем самым, - к вычислению хроматического многочлена графа вообще без ребер. [26]
По очевидным соображениям МС ( А) называют хроматическим многочленом графа G. Если мы не имеем простого способа вычисления значений ц, то нахождение многочлена Мс ( А) становится трудной задачей. Хроматические многочлены были введены Биркгофом и Люисом [2] при исследовании проблемы четырех красок. Хорошим упражнением является повторение некоторых доказательств Рида с использованием свойств ц-функции. [27]
В этой главе после определения раскраски графа и его хроматического числа излагается доказательство теоремы о пяти красках, а затем обсуждается гипотеза четырех красок. Исследуется тесная взаимосвязь между гомоморфизмами и раскрасками. Глава завершается описанием свойств хроматического многочлена. [28]
Остается нерешенной задача описания графов, имеющих один и тот же хроматический многочлен. Более общая нерешенная задача состоит в нахождении необходимого и достаточного условия для того, чтобы многочлен был хроматическим. Например, многочлен t - 3 / 3 З 2 обладает всеми известными свойствами хроматического многочлена, но не является хроматическим. [29]
Из приведенного доказательства легко вывести, что если граф G имеет п вершин, то степень многочлена PQ ( k) равна п, так как на каждом шаге не возникает никаких новых вершин. Более того, поскольку описанная нами конструкция порождает только один полный граф с п вершинами, коэффициент при k равен единице. G, и что знаки коэффициентов чередуются. Если у нас совсем нет красок, то мы не можем раскрасить граф, и поэтому постоянный член хроматического многочлена должен равняться нулю. [30]
Страницы: 1 2 3