4.5 Прочие применения

• Классическая задача о раскраске карт: вершины — страны; рёбра — общие границы. Такой граф, соответствующий карте, планарен, — а значит, по теореме о 4-х красках, всегда χ ≤ 4.

• Расчёт сетей ОКС-7; а именно, раскраска мультиграфа с некоторыми ограничениями нужна при маршрутизации пакетов с учётом равномерной нагрузки.

• Кластерный анализ.

• Решение судоку: 9 цифр судоку — 9 цветов. Вершины графа несовместимости — клетки таблицы. Рёбра между и проводим тогда и только тогда, когда:

x = x', или,

y = y', или,

и .

• Конструирование устройств, где провода, соединённые в одном узле, должны для удобства различения иметь разные цвета.

Список используемой литературы:

1. Математика. Большой энциклопедический словарь. — М.: Большая Российская Энциклопедия. 2000.

2. Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.

3. В. В. Родионов Методы четырехцветной раскраски вершин плоских графов. — М.: КомКнига, 2005.

4. Рингель Г. Теорема о раскраске карт. М.: Мир, 1974.

5. Берж К. Теория графов и её применение. М.: ИЛ, 1962.