Когда математик говорит о теории графов, он не имеет в виду «графики», о которых вы узнаете в школе, созданные с помощью электронных таблиц или графического калькулятора. Графы, изучаемые в теории графов, являются моделями сетей.
Что такое графы?
Любую сеть можно смоделировать, используя точки для представления узлов сети (города, компьютеры, сотовые телефоны и т.д.) вместе с линиями для представления соединений между этими узлами (дороги, провода, беспроводные соединения и т.д.).
Эта модель называется графом. Важно помнить, что только на одном узле информация, трафик могут проходить от одного края графа к другому краю. Если мы хотим смоделировать сеть автомагистралей с помощью графика, и две автомагистрали пересекаются в глуши, мы все равно должны разместить узел на этом перекрестке.
Если мы нарисуем график, на котором края пересекаются друг с другом, но узла в этой точке нет, то следует думать, что там есть эстакада без съездов с одного шоссе на другое: дороги пересекаются, но они не соединяются в каком-либо значимом смысле.
Многие вопросы, которые имеют важные реальные приложения, можно смоделировать с помощью графиков. Они не всегда ограничиваются вопросами, которые относятся к сетям. Некоторые вопросы могут быть смоделированы в виде графиков с использованием линий для представления ограничений или некоторых других отношений между ними.
Изучив теорию графов, вы сможете решить следующие задачи:
- Как мы можем найти подходящий маршрут для мусоровозов через конкретный город?
- Существует ли маршрут доставки, которая посещает каждый город в конкретном районе без повторения?
- Имея подборку тем проекта и группу студентов, каждый из которых проявил интерес к некоторым темам, можно ли назначить каждому студенту уникальную тему, интересующую его?
- В городе есть автобусные маршруты, все из которых начинаются и заканчиваются на автовокзале, но с различными расписаниями, некоторые из них пересекаются. Какое наименьшее количество автобусов (и водителей) требуется для того, чтобы иметь возможность пройти все маршруты в соответствии с расписанием?
- Составьте расписание круглогодичного турнира, в котором используется как можно меньше временных слотов.
На некоторые из этих вопросов вы можете ответить только для определенных видов графиков.
Теория графов является относительно «молодой» областью математики. Хотя некоторые из проблем и идей, которые мы будем изучать еще несколько сотен лет, еще в 1930-х годах были собраны вместе и начали развиваться единые исследования в области теории графов.
Теория Рамзи
Теория Рамзи берет свое название от Фрэнка П. Рамзи, британского математика, который умер в 1930 году в трагически юном возрасте 26 лет, когда у него появилась желтуха после операции.
Рамзи был логиком. В результате он рассматривал лемму в одной из своих логических работ под названием «Теорема Рамзи». Его утверждение требует немного теории графов: заданные цветами и фиксированными размерами n1, ... ... nc, существует целое число r = R (n1, ..., ...nc), такое, что для любого окрашивания края полного графа на r вершинах должно быть некое i между 1 и c, чтобы на ni вершинах был полный подграф, все края которого окрашены в цвет i.
Это утверждение не только требовало некоторой теории графов, но и было несколько техническим. Гораздо менее точными словами, которые не требуют столько базовых знаний (но могут вводить в заблуждение в определенных ситуациях), теория Рамзи утверждает, что если структура достаточно большая и содержит интересующее нас свойство, то, как бы мы ни разрезали ее на части, хотя бы одна из частей также должна иметь это свойство.
Одной из основных теорем Теории Рамзи является Теорема Ван дер Вердена. Эта теорема гласит, что для любых двух констант c и n существует постоянная V (c, n), такая, что если брать V (c, n), то должна быть арифметическая прогрессия длины n всех членов, которые окрашены в один цвет.
Пример
Вот небольшой пример теоремы Ван дер Вердена. С двумя цветами и желаемой длиной 3 для арифметической прогрессии, мы можем показать, что V (2, 3) > 8, используя следующую окраску: 3 4 5 6 7 8 9 10.
В случае затруднений мы указываем, что 3, 4, 7 и 8 - черные, а 5, 6, 9 и 10 - серые, другого цвета. Обратите внимание, что при восьми последовательных целых числах разница в трехкратной арифметической прогрессии не может быть больше трех. Для каждой трехкратной арифметической прогрессии с разницей в один, два или три семестра легко проверить, не все ли числа получили один и тот же цвет.
Фактически, V (2, 3) = 9, но доказательство этого требует исчерпывающего тестирования.
В этой статье мы немного коснулись Теории Рамзи, особенно самой Теоремы Рамзи, в контексте Теории графов.