Cтраница 3
В шестой главе исследуются оптимизационные задачи на графах, такие как задачи разбиения, размещения, раскраски вершин графов, нахождения пути коммивояжера, построения деревьев Штейнера, трассировки соединений, построения клик, независимых подмножеств, покрывающих деревьев, определения планарности и изоморфизма графов. Для решения указанных задач применяются различные методы ЭМ. Рассмотрены нечеткие модифицированные алгоритмы их решения. Описаны итерационные методы парных и групповых перестановок, методы последовательного приближения, релаксации, поиска в глубину и ширину, направленного перебора и другие, а также эвристики, использующие различные методы статистической оптимизации. Эти эвристики представлены методами отжига, генетического поиска и их модификациями. Применяется группировка сильно связанных вершин в кластеры с дальнейшим сбором этих кластеров в заданные части разбиения, а также использование фрактальных множеств для группирования сильно связанных вершин. Рассмотрены последовательный ГА разбиения, алгоритм разбиения графов на части на основе модифицированной агрегации фракталов. Проанализировано использование итерационного разбиения гиперграфа и ГА дихотомического разбиения графа. При решении проблем разбиения графов на части рассмотрены задачи группирования элементов, обладающих одинаковыми свойствами. [31]
Любой 3-связный планар-ный граф имеет в точности две укладки на плоскости. Одна укладка получается из другой с помощью одновременного изменения порядка всех дуг, инцидентных каждой вершине, на обратный порядок. Сопоставим этим укладкам направление: одна укладка - по часовой стрелке, другая - против часовой стрелки. Граф G вкладывается в плоскость таким образом, чтобы одна копия каждого графа имела укладку по часовой стрелке, а другая копия этого графа имела укладку против часовой стрелки. Теперь к укладке графа G применяется алгоритм разбиения. [32]