Я пытаюсь написать скрипт, который генерирует случайные графы, и мне нужно знать, может ли ребро в взвешенном графе иметь значение 0. на самом деле имеет смысл, что 0 можно использовать как вес ребра, но я работал с графиками в последние несколько дней, и я никогда не видел пример этого....
Для заданного взвешенного неориентированного графа G: Какие условия должны выполняться, чтобы для G было несколько минимальных остовных деревьев? Я знаю, что MST уникален, когда все веса различны, но вы не можете полностью изменить это утверждение. Если на графике есть несколько ребер с одинаковым...
Если взвешенный граф GGG имеет два разных минимальных остовных дерева T1=(V1,E1)T1=(V1,E1)T_1 = (V_1, E_1) и T2=(V2,E2)T2=(V2,E2)T_2 = (V_2, E_2) , то верно ли, что для любого ребра eee в E1E1E_1 число ребер в E1E1E_1 с таким же весом, что и eee (включая само eee ), равно числу ребер в E2E2E_2 с...
Какой алгоритм вы бы использовали, чтобы найти кратчайший путь графа, который вложен в евклидову плоскость, чтобы путь не содержал каких-либо самопересечений (во вложении)? Например, на графике ниже вы хотите перейти от . Обычно такой алгоритм, как алгоритм Дейкстры, выдает такую...
На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные letвыражения, например так: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then {...
Предположим, у меня есть ориентированный граф с весами ребер, взятыми из диапазона где - константа. Если я пытаюсь найти кратчайший путь, используя алгоритм Дейкстры , как я могу изменить алгоритм / структуру данных и повысить сложность времени до ?K O ( | V | + | E | )[1,…,K][1,…,K][1,\dots,...
Я столкнулся со следующей проблемой: Для заданного ориентированного ациклического графа с вещественными весами ребер и двумя вершинами s и t вычислим минимальный срез st. Для общих графиков это NP-сложный, поскольку можно просто уменьшить максимальный срез до него, просто изменив вес ребер...
В настоящее время я читаю некоторые статьи о комковании цепей Маркова и не вижу разницы между цепью Маркова и простым ориентированным взвешенным графом. Например, в статье « Оптимальное сосредоточение в пространстве состояний в цепях Маркова» они дают следующее определение CTMC (непрерывной цепи...