ГРАФА УКЛАДКА


ГРАФА УКЛАДКА

графа вложение,- отображение вершин и ребер графа соответственно в точки и непрерывные кривые нек-рого пространства такое, что вершины, инцидентные ребру, отображаются в концы кривой, соответствующей этому ребру. Правильной укладкой наз. укладка, при к-рой разным вершинам соответствуют различные точки, а кривые, соответствующие ребрам (исключая их концевые точки), не проходят через точки, соответствующие вершинам, и не пересекаются. Любой граф допускает правильную укладку в трехмерное пространство. Граф, допускающий правильную укладку на плоскости, наз. плоским. Существуют неплоские графы, напр, графы и (см. Граф плоский, рис. 1). Наименьший род двумерной ориентируемой поверхности, на к-рой граф Gдопускает правильную укладку, наз. родом графа G. Установлено, в частности, что


где - полный граф с вершинами, - наименьшее целое число, не меньшее ;


где - полный граф двудольный;


где есть n-мерный куб. Толщиной графа G наз. наименьшее число его плоских подграфов, объединение к-рых дает граф G. Установлено, в частности, что


(возможно с несколькими исключениями).

Изучаются также другие числовые характеристики, связанные с Г. у., напр, число скрещиваний - наименьшее число пересечений ребер, с к-рым можно уложить данный граф на данной поверхности; крупность - наибольшее число непересекающихся по ребрам неплоских подграфов в данном графе и др. Рассматриваются также укладки на неориентируемых поверхностях. Вложение графа в n-мерную целочисленную решетку - это отображение в данную решетку, при к-ром вершины отображаются в различные узлы решетки, а ребра идут по линиям решетки.

Задачи об укладках графов на поверхностях и вложениях их в решетки возникают при автоматизированном проектировании ЭВМ, при проектировании коммуникаций ы т. д.

Лит.: [1] Харари Ф., Теория графов, пер. с англ., М., 1973; [2] Теория графов. Покрытия, укладки, турниры, сб. переводов, М., 1974, с. 82 -159. В. Б. Алексеев.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "ГРАФА УКЛАДКА" в других словарях:

  • Укладка — Укладка: Укладка (волос) Укладка парашюта Корзина  укладка разного вида, сплетённая из прутьев, из стеблей, соломы, коры, кореньев, драни и прочего Укладка пути (трамвайных, ж/д линий, асфальта и т. п.) Укладка кабеля Укладка… …   Википедия

  • ГРАФА РАСКРАСКА — приписывание цветов вершинам и (или) ребрам графа, обладающее определенными свойствами. Правильная вершинная (реберная) раскраска это раскраска вершин (ребер) графа, при к рой любые смежные вершины (ребра) окрашены в разные цвета. Правильную… …   Математическая энциклопедия

  • ГРАФ ПЛОСКИЙ — планарный граф, граф, допускающий правильную укладку на плоскости (см. Графа укладка). Иными словами, граф G наз. плоским, если он может быть изображен на плоскости так, что вершинам соответствуют различные точки плоскости, а линии,… …   Математическая энциклопедия

  • ГРАФОВ ТЕОРИЯ — область дискретной математики, особенностью к рой является геометрич. подход к изучению объектов. Основной объект Г. т. граф и его обобщения. Первые задачи Г. т. были связаны с решением математических развлекательных задач и головоломок (задача о …   Математическая энциклопедия

  • ГРАФОВ ЧИСЛОВЫЕ ХАРАКТЕРИСТИКИ — функции, заданные на множестве графов и принимающие значения из нек рого множества чисел. Ниже приведен ряд Г. ч. х. и их наиболее употребительные обозначения. Наиболее простыми Г. ч. х. являются число вершин и число ребер (дуг) графа G.… …   Математическая энциклопедия

  • ФАКТОРИЗАЦИЯ — в теории графов разложение графа на непересекающиеся по ребрам остовные подграфы специального вида. В общем случае фактор есть остовный подграф, обладающий заданным свойством. Примером такого свойства является регулярность подграфа. Регулярный… …   Математическая энциклопедия

  • ДЕРЕВО — в теории графов связный неориентированный граф G, не содержащий циклов. Д. не имеет кратных ребер и петель. Являясь простейшими связными графами, Д. служат хорошими моделями для рассмотрения различных вопросов теории графов. Любое Д. с пвершинами …   Математическая энциклопедия

  • Гамма-алгоритм — Гамма алгоритм  алгоритм плоской укладки графа и проверки его на планарность. Содержание 1 Определения 2 Алгоритм 3 Реализация …   Википедия

  • Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С …   Википедия

  • Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.