«График Петерсена» — математическая книга о графе Петерсена и его применении в теории графов . Она была написана Дереком Холтоном и Джоном Шиханом и опубликована в 1993 году издательством Кембриджского университета в седьмом томе серии лекций Австралийского математического общества.
Граф Петерсена — неориентированный граф с десятью вершинами и пятнадцатью ребрами, обычно изображаемый в виде пентаграммы внутри пятиугольника , с соответствующими вершинами, прикрепленными друг к другу. Он обладает множеством необычных математических свойств и часто используется в качестве контрпримера к гипотезам теории графов. [1] [2] В книге эти свойства используются как предлог для освещения нескольких сложных тем теории графов, где этот граф играет важную роль. [1] [3] Он хорошо иллюстрирован и включает как открытые проблемы по обсуждаемым темам, так и подробные ссылки на литературу по этим проблемам. [1] [4]
После вводной главы вторая и третья главы посвящены раскраске графов , истории теоремы о четырех цветах для плоских графов , ее эквивалентности трехреберной раскраске плоских кубических графов , снаркам (кубическим графам, не имеющим таких раскрасок), и гипотеза У. Т. Тутта о том, что каждый снарк имеет граф Петерсена в качестве минора графа . Еще две главы посвящены тесно связанным темам: идеальным паросочетаниям (наборам ребер, которые могут иметь один цвет при 3-раскраске ребер) и потокам, не имеющим нигде нуля ( двойственная концепция раскраски планарных графов). Граф Петерсена снова появляется в другой гипотезе Тутте: когда граф без мостов не имеет графа Петерсена в качестве минора, он должен иметь нигде ненулевой 4-поток. [3]
Шестая глава книги посвящена клеткам — наименьшим регулярным графам , в которых нет циклов короче заданной длины. Граф Петерсена является примером: это наименьший 3-регулярный граф без циклов длиной менее 5. Глава седьмая посвящена гипогамильтоновым графам , графам, которые не имеют гамильтонова цикла через все вершины, но имеют циклы через каждую вершину. множество всех вершин, кроме одной; граф Петерсена является наименьшим примером. Следующая глава посвящена симметриям графов и типам графов, определяемым их симметриями, включая дистанционно-транзитивные графы и сильно регулярные графы (примером которых является граф Петерсена) [3] и графы Кэли (из которых нет). [1] Книга завершается последней главой, посвященной различным темам, слишком маленьким для отдельных глав. [3]
В книге предполагается, что читатели уже имеют некоторое представление о теории графов. [3] Его можно использовать в качестве справочного пособия для исследователей в этой области, [1] [2] или в качестве основы углубленного курса теории графов. [2] [3]
Хотя Карстен Томассен описывает книгу как «элегантную» [4] , а Робин Уилсон оценивает ее изложение как «в целом хорошее», [2] рецензент Чарльз Х. К. Литтл придерживается противоположной точки зрения, придираясь к редактированию и некоторым математическим обозначениям. , и с его неспособностью обсудить решетку целочисленных комбинаций идеальных паросочетаний, в которой количество копий графа Петерсена в «кирпичиках» определенного разложения графа играет ключевую роль в вычислении размерности. [1] Рецензент Ян Андерсон отмечает поверхностность некоторых статей, но приходит к выводу, что книга «удается дать захватывающий и восторженный взгляд» на теорию графов. [3]