Разбиение - граф
Cтраница 4
В [87] описывается очень популярный в последнее время метод решения различных дискретных задач оптимизации - метод имитации отжига, являющийся модификацией известного алгоритма Метрополиса. В [87] решается задача о разбиении графа на два подграфа с равным числом вершин и с минимальным числом ребер, соединяющих эти подграфы. [46]
Граф называется связным, если любые две его вершины соединяются хотя бы одной последовательностью ребер, и несвязным в противном случае. Ребро графа, удаление которого приводит к разбиению графа на две несвязные части, называется мостом. Другими словами, мостом называется ребро, соответствующее проходной цепи в гигантской циклизованной макромолекуле. Вершина с этим же свойством называется точкой сочленения. Более общим понятием является / с-сечение - набор таких k мостов и / г-вершин, удаление которых приводит к разбиению графа на две несвязные части. Граф, не, содержащий ни одного / е-сечения, называется / с-неприводимым, а в обратном случае - / с-приводимым. [47]
 |
Два способа распределения девяти процессов на трех узлах. [48] |
На рис. 8.25, а граф разделен следующим образом: узлу 1 назначены процессы А, Е и G, на узле 2 работают процессы В РиН а узлу 3 достались процессы C DnI. На рис. 8.25, б представлен другой вариант разбиения графа на подграфы. При условии, что такой вариант распределения процессов удовлетворяет всем требованиям памяти и процессорной мощности, этот выбор лучше, так как при нем требуется меньший сетевой трафик. [49]
 |
Два способа распределения девяти процессов на трех узлах. [50] |
На рис. 8.25, а граф разделен следующим образом: узлу 1 назначены процессы A EnG, на узле 2 работают процессы B FuH a узлу 3 достались процессы C DnI. На рис. 8.25, б представлен другой вариант разбиения графа на подграфы. При условии, что такой вариант распределения процессов удовлетворяет всем требованиям памяти и процессорной мощности, этот выбор лучше, так как при нем требуется меньший сетевой трафик. [51]
Следует заметить, что с увеличением числа генераций в ГА время решения оптимизационной задачи разбиения повышается, но это повышение незначительное и может быть компенсирование получением множества локально-оптимальных решений. Генетические алгоритмы требуют больших затрат времени, чем алгоритмы парных перестановок и случайного разбиения графов. Но они позволяют получать набор локально-оптимальных решений. [52]
Первый топологический индекс, основанный на теории информации, введен в 1955 - 1956 гг. Рашевским [36] и Трукко [37] на базе группы автоморфизмов графа данного соединения. Так называемый хроматический информационный индекс предложен Мовшови-чем [38] и определен исходя из однозначного разбиения графа G на основе его хроматических классов. Теоретико-информационные индексы, построенные с помощью матрицы расстояний, разработаны Бончевым и Тринайстичем [39]: первый индекс зависит от разбиения полного числа расстояний на классы, а второй - от разбиения полного расстояния. [53]
Можно предположить, что V 4 и что граф G не имеет вершин степени 2, поскольку если V 4 или в G имеется вершина степени 2, то вопрос о трехсвязности решается немедленно. В статье ( Хопкрофт, Тарьян [ 1971 А ]) описан метод разбиения графа на 2-связные компоненты за 0 ( V, E) действий. [54]
В некоторых исследованиях, например, в [173], предлагается при решении задачи разбиения графа на части не минимизировать К ( число связей между частями разбиения), а максимизировать количество связей ( критерий А) внутри частей разбиения. [55]
Страницы: 1 2 3 4