Добавленное ребро
Cтраница 1
 |
Матрица примыканий для полного взвешенного графа. [1] |
Добавленное ребро не является третьим, выходящим из какой-либо одной вершины. [2]
Один из недостатков алгоритма ближайшего соседа состоит в том, что последнее добавленное ребро ( ведущее из последнего города назад в начальный город) может оказаться очень длинным. [3]
Любая гамильтонова цепь графа С с концевыми вершинами х1 и х2 может рассматриваться как гамильтонова цепь, проходящая через вершины графа О с добавленными ребрами ( хг, X) и ( х2, х), х, х 6 X. [4]
Дополним граф G п ребрами, каждое из которых соединяет две вершины нечетной степени так, чтобы каждая такая вершина была инцидентна одному из добавленных ребер. Пусть F обозначает множество добавленных ребер. Тогда G - ( V, EUF) является связным эйлеровым графом и, следовательно, EUF образует цикл. Если ребра F ( множество F не содержит смежных ребер) удалить, то цикл распадается на п цепей, которые покрывают G и имеют в качестве граничных точек 2 / г вершин нечетной степени. Следовательно, реберные разделения, о которых говорилось в формулировке теоремы, существуют. [5]
Тогда в силу теоремы 1.48 и того факта, что В не содержит вырожденных мостов ( см. теорему 1.51), каждая вершина из множества 5 инцидентна одному из добавленных ребер. [6]
Требуется найти гиперсеть 5 ( PS, WS; Ф) такую, чтобы со ( 5) kai ( PS) и выполнялось условие ( 11), где WS - ( У, R U U), a U - множество добавленных ребер. Причем при добавлении очередного ребра емкости ребер WS пересчитываются. [7]
Добавление любого ребра ( х х) из О, не принадлежащего Т, к ребрам дерева Т приводит к образованию точно одного ( простого) цикла, состоящего из ребер остова Т, лежащих на ( единственной) цепи из x в х, и только что добавленного ребра. Так как в графе О имеется т ребер, п - 1 из которых лежат в Т, то число всех циклов, построенных таким способом, равно т - п 1, что совпадает с цикломатическим числом графа С. [8]
Добавление любого ребра ( xi: xs) из G, не принадлежащего Т, к ребрам дерева Т приводит к образованию точно одного ( простого) цикла, состоящего из ребер остова Т, лежащих на ( единственной) цепи из X ] в Х, и только что добавленного ребра. Так как в графе G имеется т ребер, п - 1 из которых лежат в Г, то число всех циклов, построенных таким способом, равно т - п 1, что совпадает с цикломатическим числом графа G. [9]
Дополним граф G п ребрами, каждое из которых соединяет две вершины нечетной степени так, чтобы каждая такая вершина была инцидентна одному из добавленных ребер. Пусть F обозначает множество добавленных ребер. Тогда G - ( V, EUF) является связным эйлеровым графом и, следовательно, EUF образует цикл. Если ребра F ( множество F не содержит смежных ребер) удалить, то цикл распадается на п цепей, которые покрывают G и имеют в качестве граничных точек 2 / г вершин нечетной степени. Следовательно, реберные разделения, о которых говорилось в формулировке теоремы, существуют. [10]
Для выполнения данного технологического процесса необходимо четыре станка. Загрузка оборудования может осуществляться по любой компоненте мультираскраски. При возникновении ситуаций, влекущих за собой появление дополнительных ребер на графе зацеплений, загружается оборудование согласно той компоненте, по которой спектра вершин, коин-цидентных добавленному ребру, различны. [11]
Один ( не очень существенный) недостаток изложенного алгоритма для построения минимального стягивающего дерева состоит в предположении, что с самого начала у нас уже есть по крайней мере одно стягивающее дерево. С другой стороны, если сначала нужно построить стягивающее дерево, то стягивающее дерево с минимальной стоимостью получается почти без дополнительных усилий. Очевидный метод получения какого-либо стягивающего дерева состоит в построении множества его ребер таким образом, чтобы на каждом шаге прибавлялось по одному ребру и проверялось, не образует ли добавленное ребро цикл с ребрами, уже включенными в множество. Какие изменения нужно внести в этот алгоритм для того, чтобы гарантировать получение минимального стягивающего дерева. Ответ на этот вопрос дает следующий алгоритм. [12]
Многокомпонентную А - раскраску графа G называют минимальной мулътираскраской, если К равно предквазиплотности графа. При минимальной мультираскраске графа зацеплений модель, отображающая технологический процесс с точки зрения оборудования, определяет оптимальные решения независимо от появления на графе зацепления дополнительных ребер, поскольку всегда найдется компонента мультираскраски, по которой спектры вершин, коинцидентных добавленному ребру, различны. При этом предквазиплотность исходного графа определяет минимальное число станков, которое гарантирует выполнение технологического процесса в условиях возможного появления дополнительных ограничений вследствие непредвиденных ситуаций. [13]
Страницы: 1