Число пересечений (теория графов)
-
Определение и свойства числа пересечений
- Число пересечений графа – это минимальное количество пересечений ребер на рисунке графа.
- Число пересечений связано с хроматическим числом и является NP-трудной задачей.
-
История и исследования
- Проблема была впервые сформулирована в 1930 году и связана с планированием и геометрией.
- Хилл и Эрнест вывели гипотетическую формулу для числа пересечений, которая была подтверждена для некоторых значений p.
- Альбертсон предположил, что полный граф Kn имеет минимальное число пересечений среди всех n-хроматических графов.
-
Кубические графы и соединения по ширине деления пополам
- Известны наименьшие кубические графы с определенным числом пересечений.
- Ширина деления пополам – это минимальное количество ребер, которое нужно удалить, чтобы разделить вершины на два множества.
-
Сложность и приближенность
- Определение числа пересечений является NP-сложной задачей, но существуют эффективные алгоритмы для некоторых фиксированных констант k.
- Существуют эвристические алгоритмы для аппроксимации числа пересечений на графах ограниченной степени.
-
Неравенство числа пересечений и его применение
- Для неориентированного графа с e ребрами и n вершинами число пересечений всегда не меньше 29n-e.
- Неравенство числа пересечений используется в геометрии инцидентности и доказательстве теорем.
-
Вариации числа пересечений
- Существуют различные варианты числа пересечений, включая число прямолинейных пересечений и локальное число пересечений.
-
Дополнительные ресурсы
- Существуют проекты, такие как “Число прямолинейных пересечений”, для сбора дополнительных данных о числе пересечений.
Полный текст статьи: