Вложение графа в решетку

Анотація

К задаче оптимального вложения взвешенного по ребрам графа в прямоугольную решетку сводится ряд технических задач размещения связанных между собой объектов, например, элементов РЭА. Сведение ее к задаче квадратичного назначения [1] не учитывает симметрии решетки: вершины графа располагаются горизонтальными и вертикальными рядами (строками и столбцами). При использовании ортогональной метрики верно следующее утверждение: для фиксированных наборов вершин в строках оптимальное расположение вершин в строках не зависит от порядка следования строк…