Я читаю о проблеме максимального потока здесь . Я не мог понять интуицию, стоящую за остаточным графиком. Почему мы учитываем задние края при расчете потока? Может ли кто-нибудь помочь мне понять концепцию остаточного графа? Как меняется алгоритм в неориентированных...
Если граф GGG связен и не имеет пути длиной больше kkk , докажите, что каждые два пути в GGG длины kkk имеют хотя бы одну общую вершину. Я думаю, что эта общая вершина должна быть в середине обоих путей. Потому что, если это не так, то мы можем иметь путь длиной >k>k>k . Я...
Я ищу O (V + E) алгоритм для нахождения транзитивного сокращения с учетом DAG. То есть удалите как можно больше ребер, чтобы, если бы вы могли достичь v от u, для произвольных v и u вы все еще можете достичь после удаления ребер. Если это стандартная проблема, пожалуйста, укажите мне какое-нибудь...
Я новичок (абсолютный новичок в теории вычислительной сложности), и у меня есть вопрос. Допустим, у нас есть «проблема коммивояжера», решит ли ее следующее применение алгоритмов Дейкстры? Из начальной точки мы вычисляем кратчайшее расстояние между двумя точками. Мы идем к сути. Удаляем исходную...
Я реализовал топологическую сортировку на основе статьи в Википедии, которую я использую для разрешения зависимостей, но она возвращает линейный список. Какой алгоритм я могу использовать, чтобы найти независимые...
Я верю, что это правда, но не смог получить формальное доказательство ни того, ни другого. Но правда ли, что любое минимальное остовное дерево достижимо с помощью алгоритма Крускала? Точно так же это верно для алгоритма Прима? РЕДАКТИРОВАТЬ: Чтобы быть более точным, я хочу знать, если дан MST для...
Направленный граф называется унипатическим, если для любых двух вершин и в графе существует не более одного простого пути из в .uuuvvvG=(V,E)G=(V,E)G=(V,E)uuuvvv Предположим, мне дан унипатический граф такой, что каждое ребро имеет положительный или отрицательный вес, но не содержит циклов...
В настоящее время я читаю введение в алгоритмы и пришел по алгоритму Джонсона, который зависит от того, чтобы убедиться, что все пути положительны. алгоритм зависит от нахождения новой весовой функции (w '), которая является положительной для всех ребер и сохраняет правильность соотношений...
У меня есть очень общий вопрос. Это связано с исследованиями. Я интересуюсь теорией графов. Я прошел курс в этом. Я рассмотрел некоторые темы, связанные с теорией графов, с точки зрения того, чтобы изучать математику, а также изучил некоторые алгоритмы графов. Я собираюсь пройти стажировку в...
Учитывая распределение степеней, как быстро мы можем построить график, который следует заданному распределению степеней? Ссылка или эскиз алгоритма были бы хорошими. Алгоритм должен сообщать «нет», если граф не может быть построен, и любой один пример, если можно построить несколько...
У меня есть проблема, и я думаю, что это NP-трудно, но я не могу доказать это. Вот график слоя, где слой 0 - самый высокий слой, а слой L - самый низкий. Есть некоторые направленное ребро между слоями, где ребро (А, В) указывает на то, что узел А может [крышка] узла В. И когда А может охватывать B,...
Это может граничить с вычислительной когнитивной наукой, но мне любопытно, как процесс, сопровождаемый общими алгоритмами поиска пути (такими как A * ), сравнивается с процессом, который люди используют в различных ситуациях поиска пути (учитывая ту же информацию). Эти процессы...
Я пытаюсь воспроизвести синтетические сети (графики), описанные в некоторых статьях. Утверждается, что модель Барабаси-Альберта использовалась для создания «безмасштабных сетей со степенным распределением степеней, пA( k ) ∝ k- λпA(К)αК-λP_A(k) ∝ k^{-λ} ». пAпAP_A - это распределение вероятностей,...
В задаче о заправке нам даны городов и дороги между ними. Каждая дорога имеет длину, и каждый город определяет цену на топливо. Одна единица дороги стоит одну единицу топлива. Наша цель - добраться от источника до места назначения самым дешевым способом. Наш танк ограничен какой-то ценностью.{ 0 ,...
Существует семейство случайных графов с узлов ( из - за Гилберт ). Каждый возможный край независимо друг от друга вставляется в с вероятностью . Пусть быть числом клик размера в .п О ( п , р ) р Х к к G ( п , р )G ( n , p )G(n,p)G(n, p)NnnG ( n , p )G(n,p)G(n, p)пppИксКXkX_kКkkG ( n , p )G(n,p)G(n,...
В глубине первого дерева есть ребра, определяющие дерево (то есть ребра, которые использовались при обходе). Есть некоторые оставшиеся ребра, соединяющие некоторые другие узлы. В чем разница между поперечной кромкой и передней кромкой? Из википедии: Основываясь на этом остовном дереве, ребра...
На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные 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 {...
Для некоторых графиков алгоритмы поиска DFS и BFS обрабатывают узлы в одном и том же порядке при условии, что они оба начинаются на одном и том же узле. Два примера - графы, которые являются путями, и графы в форме звезды (деревья глубины с произвольным числом детей). Есть ли способ классификации...
Есть ли способ вычислить размер максимального соответствия в невзвешенном двудольном графе более эффективно (например, быстрее), чем вычисление максимального соответствия? Это длинный путь, но часто это интересная проблема, чтобы избежать одноразовых вычислений, подобных этим. мотивация Проблема ,...
Рассмотрим ориентированный граф , на котором можно динамически добавлять края и сделать некоторые конкретные запросы.граммграммG Пример: непересекающееся-множество лесов Рассмотрим следующий набор запросов: arrow(u, v) equiv(u, v) find(u) первый добавляет стрелку к графу, второй решает, если ,...