Найти максимальное число параллельных ребер в многонаправленном графе

Question

Учитывая ориентированный граф G, который допускает параллельные ребра, каков эффективный алгоритм для поиска максимального числа параллельных ребер в G?

Answer 1

Fitst, вам нужно изменить свое определение матрицы инцидентности, поскольку то, что у вас есть, не может представлять направленные (мульти) графы. Изменение может быть довольно тривиальным, например, A (i, j) = 1 / -1 / 0, если ребро j входит / уходит / не связано с вершиной i Википедия .

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

Answer 2

Наивным решением является итерация по всем парам узлов в графе и подсчет количества ребер для каждой пары.Однако многие реальные графы редки - у каждого узла есть только несколько соседей по отношению к общему количеству узлов в графе.Поэтому более разумным решением было бы сделать следующее:

import networkx as nx

# Build a sample graph:
G = nx.MultiDiGraph()
G.add_edges_from([('a', 'b'),('b', 'c'),('c', 'd'), ('b', 'c'), ('b', 'c'), ('a', 'b')])

max = 0
arg_max = ()
for source in G.nodes():
    for target in G.neighbors(source):
        n = G.number_of_edges(source, target)
        if n > max:
            max = n
            arg_max = (source, target)

print('max # of edges = {}, for nodes: {}'.format(max, arg_max))

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