Постановка задачи (У. Кэли, 1878). Можно ли на политико-административной карте раскрасить страны так, чтобы никакие две страны, имеющие общую границу, не были раскрашены одинаковой краской, и чтобы были использованы всего 4 краски (если две страны граничат по точке, то считается, что они не имеют общей границы).
В терминах теории графов эта задача формулируется следующим образом. Дан произвольный полностью неориентированный плоский граф. Можно ли каждую его вершину раскрасить с помощью одной из четырех красок так, чтобы никакие две смежные вершины не были раскрашены в один цвет.
В общем виде эта задача до сих пор не решена. Доказано лишь, что такую раскраску можно осуществить для всех плоских графов с числом вершин, не превышающим 38. Общая теорема доказана для случая любого плоского графа и пяти красок.
Лабиринты
Задача о поиске выхода из лабиринта в терминах теории графов сводится к построению цепи, связывающей две данные вершины связного полностью неориентированного графа.
Деревья и сети
Определение 48. Сетью называют конечный связный орграф без циклов и петель, ориентированный в одном общем направлении от вершины 
к вершине 
.
Определение 49. Вершину называют истоком (входом) сети.
Определение 50. Вершину называют стоком (выходом) сети.
Определение 51. Вершины графа называют узлами сети.
Пример 36.8. У сети, изображенной на рис. 36.10, истоком является вершина 
, а стоком – 
.
Определение 52. Деревом называют сеть, имеющую ровно один исток (рис. 36.11).
Определение 53. Вершину сети , являющуюся истоком, называют корнем дерева.
Замечание. Для всякого дерева полустепень захода корня 
.
Определение 54. Вершины дерева, для которых полустепени исхода равны нулю (
), называют крайними.
Определение 55. Пути от исходной вершины к крайним называют ветвями.
Теорема 10. Число вершин 
и число ребер 
любого дерева связаны равенством 
.
Замечание 1. Всякое дерево является сетью, но не всякая сеть является деревом. У сети может быть несколько истоков, а у дерева – ровно один.
Замечание 2. В экономических приложениях любые графы принято называть сетями, а их вершины – узлами.
Определение 56. Остовным деревом называют граф без циклов, который содержит все вершины исходного графа.
Определение 57. Граф, каждому ребру (дуге) которого присвоено некоторое числовое значение, называют размеченным.
Замечание. Числовое значение в зависимости от смысла задачи может обозначать расстояние, пропускную способность, стоимость, время и т.п.
Понятие о сетях Петри
Определение 58. Сетями Петри называют математические модели дискретных динамических, в том числе информационных, систем, ориентированные на качественный анализ и синтез таких систем (обнаружение блокировок, тупиковых ситуаций и узких мест и др.).
Сеть Петри может быть представлена размеченным орграфом с множеством вершин двух типов (
– конечное множество вершин, называемых переходами, 
– конечное множество вершин, называемых местами), заданной функцией инцидентности вида
и
и начальной разметкой мест 
. Вершины-места изображают кружками, разметку – соответствующим числом точек (фишек) в этих кружках. Вершины-переходы изображают прямоугольниками (рис. 36.12). Сеть функционирует в дискретном времени от разметки к разметке. Смена разметок происходит в результате срабатывания переходов сети. Переход может сработать, если на предшествующем ему месте (входном месте) есть хотя бы одна фишка. Если может сработать несколько переходов, то срабатывает любой из них, следовательно, при одной и той же начальной разметке сеть Петри может порождать различные последовательности срабатываний переходов. Сеть останавливается, если при некоторой разметке не может сработать ни один переход. Последовательности срабатываний переходов называют языком данной сети Петри.
Сети Петри исследуют в двух направлениях. Первое (математическая теория) разрабатывает методы формального анализа их свойств (задачи распознавания тупиковых ситуаций, задачи распознавания эквивалентных по языкам сетей, оценки сложности анализа сетей и др.) Второе – применение сетей как основы дискретных динамических систем в информатике, экономике, цифровой технике и т.п.