0
ответов
Алгоритм для нахождения общего количества связанных наборов в матрице
Я хотел знать, какой алгоритм мне следует применить здесь. Подойдет ли ДФС? Дана двумерная матрица. Найдите общее количество связанных множеств в этой матрице. Связанный набор может быть определен как группа ячеек...
вопрос задан: 30 June 2012 08:05
0
ответов
Для чего используются сильно связанные компоненты?
Я нашел несколько алгоритмов, объясняющих, как находить компоненты сильной связности в ориентированном графе, но ни один из них не объясняет, зачем вам это нужно. Каковы некоторые применения сильно...
вопрос задан: 26 June 2012 17:19
0
ответов
найти такую точку, что максимальное расстояние до любой точки в наборе точек P минимизировано
Учитывая набор точек в 2d-пространстве P, где Pi = (Xi, Yi), мне нужно найти целевую точку T такую, чтобы максимальное расстояние до любого Pi было минимальным. T не обязательно должен существовать в P, и его можно определить...
вопрос задан: 24 May 2012 15:09
0
ответов
Оптимизация векторизованного кода для смежности графа
Я пишу код машинного обучения в MATLAB, и я представляю граф с матрицей смежности A и кластеризацией графа с матрицей Z, определяемой следующими способами. A: a_ij равно 1 ...
вопрос задан: 2 May 2012 13:59
0
ответов
Алгоритм аппроксимации для варианта TSP, фиксированное начало и конец в любом месте, кроме начальной точки + РАЗРЕШЕНО многократное посещение каждой вершины
ПРИМЕЧАНИЕ :В связи с тем, что поездка не заканчивается в том же месте, где она началась и также тот факт, что каждую точку можно посетить более одного раза, пока я все равно посещаю их все, это не совсем...
вопрос задан: 27 April 2012 22:14
0
ответов
Теория графов: разделение графа
У меня возникла проблема. У меня есть граф из n узлов, который я хочу разбить на два подграфа из x узлов и nx узлов с условием, что количество оставшихся ребер максимизируется (или минимизируется...
вопрос задан: 17 April 2012 15:05
0
ответов
Список библиотек C++ для теории графов [закрыто]
Я собираюсь начать научный проект об автоматах и теории графов, и я ищу библиотеку графов, которая поддерживает такие функции, как:направленный/ненаправленный графики проверка изоморфизма графов (, т.е. есть...
вопрос задан: 16 April 2012 14:55
0
ответов
Как найти круговые связи в графе с помощью Python и Networkx?
Предположим, у меня есть следующий граф: A -> B
B -> C
C -> D
C -> A Какой самый простой способ найти, что A -> B -> C -> A является круговым отношением? Есть ли такая функция, уже построенная ...
вопрос задан: 11 April 2012 19:33
0
ответов
Алгоритм обхода всех ребер в графе
В качестве личного пасхального проекта я пытаюсь внедрить тестирование на основе моделей на работе. У меня есть граф, реализованный на питоне, и мне нужно обойти все ребра/выполнить все переходы графа, в ...
вопрос задан: 6 April 2012 11:49
0
ответов
Итеративный алгоритм связных компонентов
У меня есть двудольный граф, и я ищу наиболее эффективный итеративный способ разделить его на связанные компоненты. Моя рекурсивная версия начала переполнять стек на больших наборах данных. Я...
вопрос задан: 5 April 2012 19:29
0
ответов
Можно ли выполнить рейтинг страниц без всего набора данных?
Извините, если это глупо, но я просто подумал, что должен попробовать. Скажем, у меня есть огромный граф (например, 100 миллиардов узлов). Neo4J поддерживает 32 миллиарда, а другие поддерживают более или менее то же самое, ...
вопрос задан: 3 April 2012 00:19
0
ответов
Обновить минимальное остовное дерево с модификацией ребра
Граф (ребра с положительным весом )с MST Если какое-то ребро e изменено на новое значение, как лучше всего обновить MST, не переделывая его полностью. Я думаю, что это можно сделать за линейное время....
вопрос задан: 30 March 2012 07:51
0
ответов
Можно ли хранить графы в hbase? если да, то как вы моделируете базу данных для поддержки структуры графа?
Я экспериментировал с использованием графиков для анализа больших данных. Это работает отлично и очень весело, но мне интересно, что делать, когда данных становится все больше и больше? Дайте мне знать, если есть…
вопрос задан: 26 March 2012 01:54
0
ответов
Найти минимальный разрез в графе так, чтобы заданные вершины были несвязными
Некоторое время назад я читал об общем алгоритме минимального разреза, который берет на вход граф и удаляет минимальное количество ребер так, чтобы остались две несвязные компоненты. Сейчас я работаю над ...
вопрос задан: 21 February 2012 16:20
0
ответов
Ожидаемое количество ребер, необходимое для создания связного графа, если вершины соединяются случайным образом?
Мы случайным образом выбираем две вершины и соединяем их.
Итак, каково ожидаемое количество ребер в графе, когда он станет соединенным? Я попытался решить ее с помощью индукции, но не смог найти ответа.
...
вопрос задан: 1 February 2012 10:23
0
ответов
Сгенерировать DAG из poset, используя строго функциональное программирование.
Вот моя проблема: у меня есть последовательность S из (непустого но, возможно, не разные) наборы s_i, и для каждого s_i необходимо знать, сколько наборов s_j в S (i ≠ j) являются подмножествами s_i. Мне также нужен инкрементный ...
вопрос задан: 12 January 2012 17:18
0
ответов
Каковы некоторые альтернативы pagerank?
Это строго связано с алгоритмом графа (не SEO или что-то еще). Мне интересно, есть ли другие алгоритмы, которые используют только структуру графа (не контент, как ...
вопрос задан: 8 January 2012 22:51
0
ответов
Как удалить все связанные узлы в направленном графе с помощью networkx?
Я не совсем уверен в правильности терминологии моего вопроса, поэтому просто объясню, что я хочу сделать. У меня есть направленный граф, и после удаления узла я хочу, чтобы все независимо связанные с ним ...
вопрос задан: 8 January 2012 20:51
0
ответов
Создание графа с краями разного цвета в системе Mathematica
Я хочу создать граф (теория графов), где определенные ребра имеют другой цвет, чем другие ребра, что будет использоваться для выделения пути в графе от одной вершины к другой. Вот некоторые ...
вопрос задан: 2 January 2012 22:12
0
ответов
Алгоритм Дейкстры, похоже, не работает, мое понимание должно быть ошибочным
Вот моя интерпретация того, как алгоритм Дейкстры, описанный в Википедии, будет работать с приведенным ниже графом. Сначала он отмечает кратчайшее расстояние до всех соседних узлов, поэтому A получает 1, а C получает ...
вопрос задан: 21 December 2011 23:29
0
ответов
Обнаружение цикла в связном списке: исчерпывающая теория
Это НЕ задача об обнаружении цикла в связном списке с помощью знаменитого метода Зайца и Черепахи. В методе зайца и черепахи у нас есть указатели, работающие со скоростью 1x и 2x, чтобы определить ...
вопрос задан: 18 December 2011 12:12
0
ответов
Рекомендации по использованию теории графов в машинном обучении? [закрыто]
Я много узнал об использовании графиков для машинного обучения, просматривая видео Кристофера Бишопса (http://videolectures.net/mlss04_bishop_gmvm/). Мне это показалось очень интересным, и я посмотрел несколько ...
вопрос задан: 12 December 2011 15:37
0
ответов
Каково значение слова "ldquo; из разных цепочек вершин"? в этом алгоритме ближайшего соседа?
Следующий псевдокод взят из первой главы онлайновой предварительной версии Руководства по разработке алгоритмов (стр. 7 из этого PDF). Пример ошибочного алгоритма, но я все еще очень хочу ...
вопрос задан: 27 November 2011 03:08
0
ответов
Алгоритм разделения и покорения для деревьев
Я пытаюсь написать алгоритм разделения и покорения для деревьев. Для шага разделения мне нужен алгоритм, который разбивает заданный неориентированный граф G=(V,E) с n узлами и m ребрами на поддеревья по ...
вопрос задан: 19 November 2011 11:17
0
ответов
Линейный алгоритм времени для создания сильно связного графа
У нас есть слабо ациклический орграф. Также нам дано множество A, содержащее вершины G с нулевой начальной степенью, и множество B, содержащее вершины с нулевой исходящей степенью. (размер A меньше, чем ...
вопрос задан: 17 November 2011 23:29
0
ответов
Как преобразовать неориентированный граф в DAG?
На странице Wiki написано Any unirected Граф можно превратить в группу DAG, выбрав общий порядок его вершин и сориентируя каждое ребро от более ранней конечной точки в порядке к более поздней конечной точке. ...
вопрос задан: 14 November 2011 21:53
0
ответов
Нахождение связанных компонентов графа матрицы смежности
У меня есть случайный граф, представленный матрицей смежности в Java, как я могу найти связанные компоненты (подграфы) в этом графе? Я нашел BFS и DFS, но не уверен, что они подходят, или ...
вопрос задан: 14 November 2011 16:22
0
ответов
Преобразование неориентированного графа в дерево
Для неориентированного графа, в котором каждый узел имеет декартову координату в пространстве, имеющую общую форму дерева, существует ли алгоритм для преобразования графа в дерево и нахождения подходящего ...
вопрос задан: 6 November 2011 05:09
0
ответов
Классификация краев в DFS
В соответствии с книгой (Введение в алгоритм), в dfs края классифицируются как 4 вида: Край дерева, если в кромке (u,v), v сначала обнаруживается, то (u, v) - это
край дерева.
Back Edge, if ......, v is ...
вопрос задан: 25 October 2011 14:09
0
ответов
Можно ли добавить вес / вероятность к узлу в теории графов (используя networkx)
Я использую networkx (библиотеку для Python для работы с графами). У меня в основном есть узлы с разными ребрами, но я хочу увидеть, как будет выглядеть путь, если бы он использовал узлы, которые были наиболее связаны. Я ...
вопрос задан: 21 October 2011 02:48