Интервальная размерность графа: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
м +шаблон: некорректные викиссылки в сносках |
Kenpav (обсуждение | вклад) Нет описания правки |
||
Строка 1:
[[Файл:Boxicity.svg|thumb|300px|Граф пересечений прямоугольников с интервальной размерностью два]]
В [[Теория графов|теории графов]] '''интервальная размерность графа''' — это [[Инвариант графа|инвариант графа]], введённый
Интервальная размерность графа — это минимальная [[Размерность пространства|размерность]], в которой заданный граф может быть представлен в виде [[Граф пересечений|графа пересечений]] {{не переведено 5|Гиперпрямоугольник|гиперпрямоугольников||box (shape)}} (то есть многомерных прямоугольных параллелепипедов) с параллельными осям рёбрами. То есть должно существовать один-к-одному соответствие между [[Вершина (теория графов)|вершинами]] графа и множеством гиперпрямоугольников, таких, что прямоугольники пересекаются тогда и только тогда, когда существует ребро, соединяющее соответствующие вершины.
| |||