Укладка графа: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Укладка графа''' (''Embedding of a graph, evaluation of a graph'') - 1) для некоторого пространств...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Укладка графа''' (''Embedding of a graph, evaluation of a graph'') - | '''Укладка графа''' (''[[Embedding of a graph]], [[evaluation of a graph]]'') - | ||
1) для некоторого пространства <math>L</math> такое отображение графа | 1) для некоторого пространства <math>L</math> такое отображение [[граф|графа]] | ||
в точки и жордановы кривые этого пространства, что различным | в точки и жордановы кривые этого пространства, что различным | ||
вершинам соответствуют различные точки, а кривые, | [[вершина|вершинам]] соответствуют различные точки, а кривые, | ||
соответствующие различным ребрам, пересекаются только в | соответствующие различным [[ребро|ребрам]], пересекаются только в | ||
инцидентных этим ребрам вершинах; | [[инцидентность|инцидентных]] этим ребрам вершинах; | ||
2) допустимая нумерация вершин | 2) допустимая нумерация вершин | ||
графа, минимизирующая некоторый функционал. | графа, минимизирующая некоторый функционал. | ||
См. также ''Плоский граф, Тороидальный граф, Укладка дерева, Укладка уграфа.'' | ==См. также == | ||
''[[Плоский граф]], [[Тороидальный граф]], [[Укладка дерева]], [[Укладка уграфа]].'' | |||
==Литература== | ==Литература== | ||
[Лекции], | [Лекции], | ||
Версия от 10:41, 7 февраля 2010
Укладка графа (Embedding of a graph, evaluation of a graph) - 1) для некоторого пространства [math]\displaystyle{ L }[/math] такое отображение графа в точки и жордановы кривые этого пространства, что различным вершинам соответствуют различные точки, а кривые, соответствующие различным ребрам, пересекаются только в инцидентных этим ребрам вершинах;
2) допустимая нумерация вершин графа, минимизирующая некоторый функционал.
См. также
Плоский граф, Тороидальный граф, Укладка дерева, Укладка уграфа.
Литература
[Лекции],
[Оре],
[Евстигнеев/85]