4551
правка
Радиораскраска в планарных графах: различия между версиями
Материал из WEGA
Радиораскраска в планарных графах (посмотреть исходный код)
Версия от 13:40, 12 апреля 2016
, 12 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 50: | Строка 50: | ||
== Основные результаты == | == Основные результаты == | ||
В работах [5, 6] исследовались задачи нахождения ''минимального порядка диапазона'', ''минимального диапазона'' и ''минимального порядка' для радиораскраски в [[планарный граф|планарном графе]] G. Планарным называется граф, ребра которого могут быть уложены на плоскости без пересечений. Были получены следующие результаты: | В работах [5, 6] исследовались задачи нахождения ''минимального порядка диапазона'', ''минимального диапазона'' и ''минимального порядка'' для радиораскраски в [[планарный граф|планарном графе]] G. Планарным называется граф, ребра которого могут быть уложены на плоскости без пересечений. Были получены следующие результаты: | ||
• Вначале было показано, что количество цветов, используемое при нахождении ''минимального порядка диапазона'' для радиораскраски графа G, отличается от хроматического числа квадрата этого графа – <math>\chi (G^2) \;</math>. В частности, оно может быть больше <math>\chi (G^2) \;</math>. | • Вначале было показано, что количество цветов, используемое при нахождении ''минимального порядка диапазона'' для радиораскраски графа G, отличается от хроматического числа квадрата этого графа – <math>\chi (G^2) \;</math>. В частности, оно может быть больше <math>\chi (G^2) \;</math>. | ||
