McMullen C. / Макмаллен К. - The Four-Color Theorem and Basic Graph Theory / Теорема о четырех красках и основы теории графов [2020, PDF, ENG]

The Four-Color Theorem and Basic Graph Theory / Теорема о четырех красках и основы теории графов
Год издания: 2020
Автор: McMullen C. / Макмаллен К.
Жанр или тематика: Научно-популярная монография
Издательство: Zishka Publishing
ISBN: 978-1-941691-09-0
Язык: Английский
Формат: PDF/EPUB
Качество: Издательский макет или текст (eBook)
Интерактивное оглавление: Да
Количество страниц: 482 (pdf)
Тираж: отсутствует
Описание:
This book will take you on a tour of the four-color theorem and related concepts from graph theory. Numerous illustrations are provided to help you visualize important ideas. Concepts are explained in clear, simple terms. No prior knowledge of graph theory is assumed.
Following is a sample of what you will find in this book:
‒ what the four-color theorem is;
‒ a novel explanation for why the four-color theorem holds (Chapter 27);
‒ the reason for working with graphs instead of maps;
‒ what triangulation is and the reason behind it;
‒ visual examples of Kempe chains and Kempe’s attempted proof;
‒ the three-edges theorem: a simplified approach to the four-color theorem;
‒ cool concepts like “quadrilateral switching” and “vertex splitting”;
‒ the distinction between planar graphs and nonplanar graphs;
‒ how to determine if a graph is a maximal planar graph or not;
‒ Euler’s formula and its relation to maximal planar graphs;
‒ explanations of Kuratowski’s theorem and Wagner’s theorem;
‒ complete graphs and complete bipartite graphs;
‒ a survey of a few named graphs such as the Fritsch and Errera graphs;
‒ how some maximal planar graphs can be trivially colored;
‒ a simple algorithm for four-coloring a maximal planar graph (Chapters 22 and 24);
‒ counting how many ways a graph can be colored using no more than four colors;
‒ comparing the coloring of a graph to a logic puzzle;
‒ Hamiltonian cycles and polygon forms of maximal planar graphs;
‒ what a separating triangle is and how to use it.
May you enjoy this tour of the four-color theorem and basic graph theory.
(Перевод)
В этой книге вы познакомитесь с теоремой о четырех красках и связанными с ней понятиями из теории графов. Для визуализации важных идей в книге приведены многочисленные иллюстрации. Понятия объясняются в понятных, простых терминах. Никаких предварительных знаний теории графов не предполагается.
Из этой книги вы узнаете:
‒ что такое теорема о четырех красках;
‒ новое объяснение того, почему теорема о четырех красках справедлива (глава 27);
‒ причина работы с графами вместо карт;
‒ что такое триангуляция и для чего она нужна;
‒ наглядные примеры цепочек Кемпа и попытка доказательства Кемпа;
‒ теорема о трехреберных графах: упрощенный подход к теореме о четырех красках;
‒ классные понятия, такие как "четырехугольное переключение" и "расщепление вершин”;
‒ различие между планарными и непланарными графами;
‒ как определить, является ли граф максимальным планарным графом или нет;
‒ формула Эйлера и ее отношение к максимальным планарным графам;
‒ объяснения теоремы Куратовского и теоремы Вагнера;
‒ полные графы и полные двудольные графы;
‒ обзор нескольких графов, получивших имена, таких как графы Фрича и Эрреры;
‒ как некоторые максимальные планарные графы могут быть тривиально окрашены;
‒ простой алгоритм для окрашивания в 4 цвета максимального планарного графа (главы 22 и 24);
‒ подсчет количества способов окрашивания графа с использованием не более четырех цветов;
‒ сравнение раскраски графа с логической головоломкой;
‒ гамильтоновы циклы и полигональные формы максимальных планарных графов;
‒ что такое разделительный треугольник и как им пользоваться.
Пусть вам понравится этот тур по теореме о четырех красках и основам теории графов.