Описание тега graph-theory

Описание тега Вопросы с тегом
Граф - это математическая структура, которая содержит набор вершин или "узлов" и набор ребер, соединяющих пары вершин. Графы могут быть неориентированными или направленными, ребра могут быть направлены от одной вершины к другой.
5 ответов

Количество различных ациклических путей от A[a,b] до A[c,d]?

Я пишу решатель Сокобана для развлечения и практики, он использует простой алгоритм (что-то вроде BFS с небольшой разницей). Теперь я хочу оценить его время работы ( O и Omega). но нужно знать, как рассчитать количество ациклических путей от одной в…
23 мар '10 в 14:56
2 ответа

Обеспечиваемая планарность блок-схем

У меня есть вопрос: есть ли ссылка (например, бумага) с доказательством плоскостности макетов блок-схем? Кто-нибудь может предложить алгоритм генерации схем (планарных) макетов? Я знаю, что есть некоторые инструменты кода для блок-схемы, но я не зна…
15 мар '10 в 05:37
7 ответов

Какая самая простая и эффективная структура данных для построения ациклических зависимостей?

Я пытаюсь построить последовательность, которая определяет порядок уничтожения объектов. Можно предположить, что циклов нет. Если объект A использует объект B во время его (A) строительства, то объект B должен быть доступен во время уничтожения объе…
11 авг '09 в 16:08
0 ответов

Остовное дерево с ровно a1+a2=n ребрами

Этот вопрос очень похож на этот: остовное дерево с ровно k краями Это не тот же вопрос! - Как видите, ответ на вопрос выше не тот (к моему Q).... У нас есть связанный, неориентированный граф G=(V,E) с краями, каждый из которых либо красный, либо син…
20 май '15 в 12:19
3 ответа

Хранение полного графа в РСУБД

У меня есть несколько типов объектов, каждый со своими полями, которые хранятся в отдельных таблицах.Каждая запись в такой таблице может быть связана с нулем или несколькими записями в другой таблице, т. Е. Связана с записями из разных типов объекто…
28 сен '08 в 15:30
2 ответа

Топологическая сортировка с группировкой

Итак, в топологической сортировке в зависимости от входных данных обычно есть несколько правильных решений, для которых порядок "графа" может быть "обработан", так что все зависимости располагаются перед "зависимыми" от них узлами. Тем не менее, я и…
01 ноя '10 в 21:16
1 ответ

Случайное размещение вершин в jgraph

Я создал приложение с помощью jgraph для визуализации. У меня есть пара проблем, касающихся этого. 1: мне нужно изменить имена вершин в соответствии с атрибутом объекта вершины. Когда я запускаю приложение с настройками по умолчанию, имена вершин пе…
11 май '13 в 12:08
1 ответ

Решение взвешенного сетевого потока с использованием Neo4J

У меня есть двудольный график (заметки парня и девушки), где узлы связаны с взвешенными ребрами (насколько совместима пара девушка-парень), и каждый узел имеет емкость 5 (каждый парень / девушка может быть сопоставлен с 5 людьми противоположного Пол…
30 окт '14 в 21:46
1 ответ

В алгоритме минимального разреза Каргера устранение самоконтроля в графе

Я пытаюсь реализовать алгоритм Каргера для нахождения минимального разреза графа. Ключевой частью является contract метод, который выполняет однократное сокращение. Вот моя реализация (с "тестом"): import pytest import random class Graph(object): de…
16 авг '17 в 22:23
15 ответов

Когда целесообразно использовать поиск в глубину (DFS) по сравнению с поиском в ширину (BFS)?

Я понимаю разницу между DFS и BFS, но мне интересно знать, когда практичнее использовать один поверх другого? Может ли кто-нибудь привести примеры того, как DFS превзойдет BFS и наоборот?
26 июл '10 в 07:24
1 ответ

Маркировка графа, в которой два цикла делят не более одной вершины

Доброе утро. Мой друг дал мне интересную проблему с графиком, которая описана ниже. Для простого графа, в котором два цикла делят не более одной вершины, как пометить ребра неотрицательным вещественным числом так, чтобы для каждой вершины сумма мето…
15 май '13 в 03:53
1 ответ

Самый быстрый способ определить, будет ли прямоугольный граф разделен, если узел удален

Я работаю над атмосферным симулятором для видеоигры, и проблема, с которой я столкнулся, заключается в том, что мне нужен дешевый (во время обработки) способ, чтобы определить, является ли граф узлов в прямоугольной сетке (каждый узел подключен до ч…
25 май '15 в 00:57
1 ответ

Эквивалентное поддерево

У меня есть два дерева. Узел дерева определяется как class Node{ String treeId; String type; //Each node has type which has fixed value. For example, its color: RED, BLANK, GREEN Set<Node> children; String ref; //The ref is a string and allowe…
05 июн '14 в 14:26
1 ответ

Извлечение подграфа по узлам

Я пытаюсь найти подходы для извлечения подграфа на основе узлов. У нас есть большой граф (направленный или нет), и у нас есть список узлов, которые мы хотим извлечь из графов, но мы хотим извлечь также промежуточные узлы... Когда мы смотрим на извле…
28 ноя '13 в 20:37
3 ответа

Как сжать повторяющиеся ветви в ориентированном графе?

Я много работаю с ориентированными графами, полученными из дампов кучи Java-программ. Их характеризует то, что они содержат много повторяющихся паттернов. Я хотел бы найти способ сжатия таких шаблонов, сохраняя при этом основную структуру графика. Н…
16 дек '09 в 14:03
0 ответов

Значение мусора в выводе графика

Я иду и пытаюсь отладить каждую строку этого кода, но не могу понять, почему один узел имеет значение мусора, а все остальные работают. У меня есть ощущение, что это связано с моей функцией печати графика. В зависимости от того, как я изменю свою фу…
03 ноя '18 в 20:18
0 ответов

Соединение прямых и косвенных взаимодействий с использованием теории графов

У меня есть 2 типа взаимодействий. Прямые взаимодействия, в которых направление взаимодействия известно, и косвенные взаимодействия, в которых направление взаимодействия неясно. Я создал ориентированный граф для прямых взаимодействий и неориентирова…
01 авг '18 в 13:39
1 ответ

Расширение максимального соответствия двудольного графа

Предположим, что есть два таких графика: Мы стремимся найти совпадающие соответствия между двумя графами. И теперь мы используем метод, чтобы вычислить сходство двух узлов между двумя графами. w(A,1) означает сходство узла A с левого графа между узл…
27 ноя '15 в 02:37
1 ответ

Ненормализованные оценки центральности в NetworkX

Привет, я пытаюсь получить оценку центральности от NetworkX. Однако в последнем обновлении, т.е.NETworkX 2.1, функция выглядит следующим образом: nx.loseness_centrality(G, u=None, distance=None, wf_improved=True, reverse=False) Однако в NetworkX 1.9…
03 май '18 в 02:38
0 ответов

Понимание обнаружения сообщества Infomap

Мне нужно понятное описание алгоритма обнаружения сообщества Infomap. Я читал газеты, но мне было не ясно. Мои вопросы: Как в принципе работает алгоритм? При чем тут случайные прогулки? Что такое уравнение карты и в чем (очевидно) разница с оптимиза…
30 янв '18 в 18:57