Графа укладка

графа вложение,- отображение вершин и ребер графа соответственно в точки и непрерывные кривые нек-рого пространства такое, что вершины, инцидентные ребру, отображаются в концы кривой, соответствующей этому ребру. Правильной укладкой наз. укладка, при к-рой разным вершинам соответствуют различные точки, а кривые, соответствующие ребрам (исключая их концевые точки), не проходят через точки, соответствующие вершинам, и не пересекаются. Любой граф допускает правильную укладку в трехмерное пространство. Граф, допускающий правильную укладку на плоскости, наз. плоским. Существуют неплоские графы, напр, графы [img: http://localhost:8080/file/010429-69.jpg] и [img: http://localhost:8080/file/010429-70.jpg] (см. Граф плоский, рис. 1). Наименьший род двумерной ориентируемой поверхности, на к-рой граф Gдопускает правильную укладку, наз. родом [img: http://localhost:8080/file/010429-71.jpg] графа G. Установлено, в частности, что [img: http://localhost:8080/file/010429-72.jpg] где [img: http://localhost:8080/file/010429-73.jpg] - полный граф с [img: http://localhost:8080/file/010429-74.jpg] вершинами, [img: http://localhost:8080/file/010429-75.jpg] - наименьшее целое число, не меньшее [img: http://localhost:8080/file/010429-76.jpg]; [img: http://localhost:8080/file/010429-77.jpg] где [img: http://localhost:8080/file/010429-78.jpg] - полный граф двудольный; [img: http://localhost:8080/file/010429-79.jpg] где [img: http://localhost:8080/file/010429-80.jpg] есть n-мерный куб. Толщиной [img: http://localhost:8080/file/010429-81.jpg] графа G наз. наименьшее число его плоских подграфов, объединение к-рых дает граф G. Установлено, в частности, что [img: http://localhost:8080/file/010429-82.jpg] (возможно с несколькими исключениями). Изучаются также другие числовые характеристики, связанные с Г. у., напр, число скрещиваний - наименьшее число пересечений ребер, с к-рым можно уложить данный граф на данной поверхности; крупность - наибольшее число непересекающихся по ребрам неплоских подграфов в данном графе и др. Рассматриваются также укладки на неориентируемых поверхностях. Вложение графа в n-мерную целочисленную решетку - это отображение в данную решетку, при к-ром вершины отображаются в различные узлы решетки, а ребра идут по линиям решетки. Задачи об укладках графов на поверхностях и вложениях их в решетки возникают при автоматизированном проектировании ЭВМ, при проектировании коммуникаций ы т. д.