граф, для которого найдется такая инъекция на плоскость, что вершины отображаются в точки, ребра отображаются в кривые, соединяющие образы инцидентных им вершин, и эти кривые не имеют общих точек, кроме конечных (на рисунке образ плоского смешанного графа)
Определение 1
Проверка планарности графа — это проверка возможности отображения данного графа на...
Это означает, что формирование рисунка плоского графа и визуализация его изображения считаются одними...
Проверка планарности графа
Предположим, что имеется произвольный граф G....
Данное представление планарного графа именуется плоским изображением графа, как на рисунке выше....
Необходимо заметить, что известны структуры, являющиеся общими для всех плоских изображений графа.
Рассматривается алгоритм проверки графа на планарность с одновременным построением математических структур для описания топологического рисунка плоского графа. Такими математическими структурами являются изометрические циклы и вращение вершин графа. Показано, что система изометрических циклов графа индуцирует вращение вершин для описания топологического рисунка плоского графа. В отличие от классических алгоритмов проверки планарности, например алгоритма Хопкрофта Тарьяна, полученный в результате работы алгоритма топологический рисунок используется для визуализации плоского графа. Вычислительная сложность алгоритма определяется как O(m2), где m количество рёбер графа.
Доказано, что если G — планарный граф обхвата не менее 31, то (^дихроматическое число Xp,q(G) не превышает 2р + (А — 1)(2д — 1) при А ^ 5. С другой стороны, показано, что существуют плоские графы произвольного обхвата со сколь угодно большим А, для которых Xp,q ^ 2p + 1 + (А — 2)q.
преобразование плоскости (пространства), переводящее каждую точку P в такую точку P′, лежащую на луче OP , что OP̅ · OP̅′ = c, где O — фиксированная точка (центр, или полюс инверсии) и c ≠ 0 — постоянная (коэффициент, или степень инверсии)
максимальный связный подграф данного графа
аксиальный вектор
