График Петерсена - The Petersen Graph

Эта статья о книге. Для графика см. Граф Петерсена.

График Петерсена это книга по математике о Граф Петерсена и его приложения в теория графов. Он был написан Дереком Холтоном и Джоном Шиханом и опубликован в 1993 г. Издательство Кембриджского университета как том 7 в их серии лекций Австралийского математического общества.

Темы

В Граф Петерсена

Граф Петерсена - это неориентированный граф с десятью вершинами и пятнадцатью ребрами, обычно изображаемыми как пентаграмма в пределах пятиугольник, с соответствующими вершинами, прикрепленными друг к другу. Он обладает множеством необычных математических свойств и часто используется в качестве контрпример к гипотезам теории графов.[1][2] В книге эти свойства используются как повод для освещения нескольких сложных тем теории графов, в которых этот граф играет важную роль.[1][3] Он хорошо иллюстрирован и включает как открытые проблемы по обсуждаемым темам, так и подробные ссылки на литературу по этим проблемам.[1][4]

После вводной главы вторая и третья главы посвящены раскраска графика, история теорема четырех цветов для планарные графы, его эквивалентность 3-кромочная окраска плоских кубические графы, то язвы (кубические графы, не имеющие такой раскраски), и гипотеза В. Т. Тутте что у каждого снарка есть граф Петерсена как граф минор. Еще две главы посвящены тесно связанным темам, идеальное соответствие (наборы ребер, которые могут иметь один цвет в трехкратной раскраске) ​​и нигде-нулевые потоки (в двойная концепция к раскраске планарного графа). Граф Петерсена снова появляется в другой гипотезе Тутте, что когда безмостовой граф не имеет графа Петерсена в качестве второстепенного, он должен иметь нигде-нулевой 4-поток.[3]

Глава шестая книги касается клетки, наименьший регулярные графики без циклов короче заданной длины. Граф Петерсена является примером: это наименьший 3-регулярный граф без циклов длины короче 5. Глава седьмая находится на гипогамильтоновы графы, графы, не имеющие Гамильтонов цикл через все вершины, но у которых есть циклы через каждый набор всех вершин, кроме одной; граф Петерсена - самый маленький пример. Следующая глава посвящена симметрии графов, и типы графов, определяемые их симметрией, включая дистанционно-транзитивные графы и сильно регулярные графы (из которых граф Петерсена является примером)[3] и Графики Кэли (из которых это не так).[1] Книга заканчивается последней главой, посвященной разным темам, слишком маленькой для отдельных глав.[3]

Аудитория и прием

Книга предполагает, что читатели уже знакомы с теорией графов.[3] Его можно использовать как справочник для исследователей в этой области,[1][2] или как основу продвинутого курса теории графов.[2][3]

Несмотря на то что Карстен Томассен описывает книгу как "элегантную",[4] и Робин Уилсон оценивает его экспозицию как "в целом хорошо",[2] рецензент Чарльз Х.С. Литтл придерживается противоположной точки зрения, находя недостатки в его копировании, в некоторых его математических обозначениях и в неспособности обсудить решетку целочисленных комбинаций идеальных совпадений, в которой количество копий графа Петерсена в " кирпичики »определенной декомпозиции графа играют ключевую роль в вычислении размерности.[1] Рецензент Ян Андерсон отмечает поверхностность некоторых статей, но заключает, что книга «дает захватывающий и восторженный взгляд» на теорию графов.[3]

использованная литература

  1. ^ а б c d е ж Литтл, Чарльз Х. К. (1994), "Обзор График Петерсена", Математические обзоры, Г-Н  1232658
  2. ^ а б c d Уилсон, Робин Дж. (Январь 1995 г.), "Обзор График Петерсена", Бюллетень Лондонского математического общества, 27 (1): 89–89, Дои:10.1112 / blms / 27.1.89
  3. ^ а б c d е ж г Андерсон, Ян (март 1995 г.), "Обзор График Петерсена", Математический вестник, 79 (484): 239–240, Дои:10.2307/3620120, JSTOR  3620120
  4. ^ а б Томассен, К., "Обзор График Петерсена", zbMATH, Zbl  0781.05001