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

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.