Топологические методы построения рисунка графа

Abstract

RU: В данной работе рассматривается математическая модель для построения рисунка графа с минимальным числом пересечений. Представлена схема выполнения этапов построения топологического рисунка непланарного графа. Рассмотрена математическая модель перехода от топологического рисунка графа к геометрическому рисунку используя силовую модель, представляющую ребра графа как пружины с заданным модулем упругости. UK: У даній роботі розглядається математична модель для побудови рисунка графа з мінімальним числом перетинів. Представлена схема виконання етапів побудови топологічного малюнка непланарного графа. Розглянута математична модель переходу від топологічного малюнка графа до геометричного малюнка використовуючи силову модель, що представляє ребра графа як пружини з заданим модулем пружності. EN: In this work a mathematical model for the construction drawing of a graph with the minimum number of intersections is presented. The construction of picture of graph is executed in a few stages, in the beginning is maximally planar sugraph for a nonplanar count, on the second stage the construction of picture of graph is produced, with the minimum number of intersections in relation to selected maximally planar sugraph. After the construction of picture of graph with the minimum number of intersecting ribs, the task of breaking up of picture of graph decides on the minimum number of non-overlapping planar subsets. Next the process of transition from the topological picture of the graph is further executed with the revolved tops to the geometrical picture. For the geometrical image of picture of graph on a plane it is required to find the coordinates of every top of graph. For this purpose as a power model, presenting the ribs of count as springs with the set module of resiliency, serves as a mathematical model of transition from the topological picture of graph to the geometrical picture, thus, tops, belongings the selected cycle (to the rim), are hardly fastened. And then every rib of graph appears the vector of force straight proportional his length.