Деякі граничні теореми про планарні графи, карти ознак та їх узагальнення

Abstract

У задачах моделювання необхідно оцінити можливість створення простого графа перед конструюванням його графічного зображення. Запропоновано метод «конструктивної побудови графів», доведено теореми про граничну кількість можливих зв’язків, що не перетинаються, для N елементів (вузлів) на площині та інших поверхнях. Доведено аналогічні теореми про розфарбування.

В задачах моделирования необходимо оценить возможность создания простого графа до конструирования его графического представления. Предложен метод «конструктивного построения графа», доказаны теоремы о предельном числе возможных непересекающихся связей для графов с N узлами на плоскости и на других поверхностях. Доказаны аналогичные теоремы о раскраске.

In problems of modeling it is necessary to evaluate the possibility of creation of a simple graph prior to construction of its graphic representation. The method of constructive drawing of graph is suggested and the theorems of boundary number of possible non-crossed links for graphs with N nodes located on plane and on other surfaces are proved. Analogous theorems about color filling are proved, too.