Алгоритм поиска избыточных ребер в графе или дереве

Question

Существует ли установленный алгоритм поиска избыточных ребер в графе?

Например, я хотел бы обнаружить, что a-> d и a-> e являются избыточными, а затем избавиться от них, например так:

=>

Редактировать: Strilanc был достаточно хорош, чтобы читать мои мысли для меня. Слово «избыточный» было слишком сильным, так как в приведенном выше примере ни a-> b, ни a-> c не считаются избыточными, а a-> d является.

Answer 1

Вы хотите вычислить наименьший граф, который поддерживает достижимость вершин.

Это называется транзитивным сокращением графика. Статья в Википедии должна помочь вам начать правильный путь.

Answer 2

Несколько способов атаковать это, но сначала вам нужно будет определить проблему немного точнее. Во-первых, у вас есть ациклический и направленный график: всегда ли это будет правдой?

Далее вам нужно определить, что вы подразумеваете под "избыточным ребром". В этом случае вы начинаете с графа, который имеет два пути a-> c: один через b и один прямой. Из этого я делаю вывод, что под «избыточным» вы подразумеваете нечто подобное. Пусть G = - граф, с V набором вершин и E & sube; V & times; V множество ребер. Похоже, вы определяете все ребра от v _i до v _j короче самого длинного ребра как "избыточные". Поэтому проще всего было бы использовать поиск в глубину, перечислять пути, а когда вы найдете новый, более длинный, сохраните его как лучший кандидат.

Хотя я не могу представить, для чего ты этого хочешь. Ты можешь сказать?

Answer 3

Проверьте это: Минимальное связующее дерево

Answer 4

Подграф данного графа, который не содержит «лишних ребер», называется « остовным деревом » этого графа. Для любого данного графа возможно несколько связующих деревьев.

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

Answer 5

У меня была похожая проблема, и я решил ее так:

Моя структура данных состоит из словаря dependends, от идентификатора узла до списка узлов, которые зависят от него (т. Е. Его последователи в DAG). Обратите внимание, что это работает только для DAG - это ориентированный ациклический граф.

Я не подсчитал точную сложность этого, но он поглотил мой график на несколько тысяч за долю секунды.

_transitive_closure_cache = {}
def transitive_closure(self, node_id):
    """returns a set of all the nodes (ids) reachable from given node(_id)"""
    global _transitive_closure_cache
    if node_id in _transitive_closure_cache:
        return _transitive_closure_cache[node_id]
    c = set(d.id for d in dependents[node_id])
    for d in dependents[node_id]:
        c.update(transitive_closure(d.id))  # for the non-pythonists - update is update self to Union result
    _transitive_closure_cache[node_id] = c
    return c

def can_reduce(self, source_id, dest_id):
    """returns True if the edge (source_id, dest_id) is redundant (can reach from source_id to dest_id without it)"""
    for d in dependents[source_id]:
        if d.id == dest_id:
            continue
        if dest_id in transitive_closure(d.id):
            return True # the dest node can be reached in a less direct path, then this link is redundant
    return False

# Reduce redundant edges:
for node in nodes:      
    dependents[node.id] = [d for d in dependents[node.id] if not can_reduce(node.id, d.id)]

Answer 6

Я думаю, что самый простой способ сделать это, на самом деле представить, как это будет выглядеть в реальной работе, представьте, если у вас есть суставы, как

(A-> B) (B-> C) (A-> C), представьте, что расстояние между соседними графами равно 1, поэтому

(A-> B) = 1, (B-> C) = 1, (A-> C) = 2.

Таким образом, вы можете удалить сустав (A-> C).

Другими словами, минимизируйте.

Это всего лишь моя идея, как я мог бы подумать об этом с самого начала. В сети есть различные статьи и источники, вы можете посмотреть их и глубже.

Ресурсы, которые вам помогут:

Алгоритм удаления избыточных ребер в двойном графе недвоичного CSP

Структура данных графа и основные алгоритмы графа

Google Книги, Об обнаружении как минимум двух подключенных подграфов

Сокращение графика

Избыточные деревья для предварительно запланированного восстановления в произвольных графах с избыточными вершинами или краями