Граф Петерсена
 | |
| Автор |
|
|---|---|
| Ряд | Серия лекций Австралийского математического общества |
| Предмет | Петерсена График |
| Издатель | Издательство Кембриджского университета |
Дата публикации | 1993 |
«График Петерсена» — математическая книга о графе Петерсена и его применении в теории графов . Она была написана Дереком Холтоном и Джоном Шиханом и опубликована в 1993 году издательством Кембриджского университета в седьмом томе серии лекций Австралийского математического общества.
Темы
[ редактировать ]
Граф Петерсена — неориентированный граф с десятью вершинами и пятнадцатью ребрами, обычно изображаемый в виде пентаграммы внутри пятиугольника , с соответствующими вершинами, прикрепленными друг к другу. Он обладает множеством необычных математических свойств и часто используется в качестве контрпримера к гипотезам теории графов. [1] [2] В книге эти свойства используются как предлог для освещения нескольких сложных тем теории графов, где этот граф играет важную роль. [1] [3] Он хорошо иллюстрирован и включает как открытые проблемы по обсуждаемым темам, так и подробные ссылки на литературу по этим проблемам. [1] [4]
После вводной главы вторая и третья главы посвящены раскраске графов , истории теоремы о четырех цветах для плоских графов , ее эквивалентности трехреберной раскраске плоских кубических графов , снаркам (кубическим графам, не имеющим таких раскрасок), и гипотеза У. Т. Тутта о том, что каждый снарк имеет граф Петерсена в качестве минора графа . Еще две главы посвящены тесно связанным темам: идеальным паросочетаниям (наборам ребер, которые могут иметь один цвет при 3-раскраске ребер) и потокам, не имеющим нигде нуля ( двойственная концепция раскраски планарных графов). Граф Петерсена снова появляется в другой гипотезе Тутте: когда граф без мостов не имеет графа Петерсена в качестве минора, он должен иметь нигде ненулевой 4-поток. [3]
Шестая глава книги посвящена клеткам — наименьшим регулярным графам, в которых нет циклов короче заданной длины. Граф Петерсена является примером: это наименьший 3-регулярный граф без циклов длиной менее 5. Глава седьмая посвящена гипогамильтоновым графам , графам, которые не имеют гамильтонова цикла через все вершины, но имеют циклы через каждую вершину. множество всех вершин, кроме одной; граф Петерсена является наименьшим примером. Следующая глава посвящена симметриям графов и типам графов, определяемым их симметриями, включая дистанционно-транзитивные графы и сильно регулярные графы (примером которых является граф Петерсена). [3] и графы Кэли (которыми это не является). [1] Книга завершается последней главой, посвященной разным темам, слишком маленьким для отдельных глав. [3]
Аудитория и прием
[ редактировать ]В книге предполагается, что читатели уже имеют некоторое представление о теории графов. [3] Он может быть использован в качестве справочного материала для исследователей в этой области. [1] [2] или в качестве основы углубленного курса теории графов. [2] [3]
Хотя Карстен Томассен называет книгу «элегантной», [4] а Робин Уилсон оценивает его экспозицию как «в целом хорошую». [2] рецензент Чарльз Х.К. Литтл придерживается противоположной точки зрения, придираясь к редактированию, некоторым математическим обозначениям и неспособности обсудить решетку целочисленных комбинаций идеальных паросочетаний, в которой количество копий графа Петерсена в " «кирпичики» определенного разложения графа играют ключевую роль в вычислении размерности. [1] Рецензент Ян Андерсон отмечает поверхностность некоторых ее изложений, но заключает, что книга «удается дать захватывающий и восторженный взгляд» на теорию графов. [3]
Ссылки
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б с д и ж Литтл, Чарльз Х.К. (1994), «Обзор графа Петерсена », Mathematical Reviews , MR 1232658
- ↑ Перейти обратно: Перейти обратно: а б с д Уилсон, Робин Дж. (январь 1995 г.), «Обзор графа Петерсена », Бюллетень Лондонского математического общества , 27 (1): 89–89, doi : 10.1112/blms/27.1.89
- ↑ Перейти обратно: Перейти обратно: а б с д и ж г Андерсон, Ян (март 1995 г.), «Обзор графа Петерсена », The Mathematical Gazette , 79 (484): 239–240, doi : 10.2307/3620120 , JSTOR 3620120
- ↑ Перейти обратно: Перейти обратно: а б Томассен, К. , «Обзор графа Петерсена », zbMATH , Zbl 0781.05001