Что такое базовый механизм для определения того, является ли простой цикл (который не пересекается) длины 4 в неориентированном графе - PullRequest
Новая
       28

Что такое базовый механизм для определения того, является ли простой цикл (который не пересекается) длины 4 в неориентированном графе

0 голосов
/ 31 декабря 2018

Дан простой неориентированный граф с вершинами в формате списка ребер.Возврат: для каждого графа выведите «1», если он содержит простой цикл (то есть цикл, который не пересекает себя) длины 4 и «-1» в противном случае.Я не понимаю основной механизм, умножая граф (в матрице смежности) сам по себе, тогда мы знаем, содержит ли граф квадратный цикл через недиагональные элементы> 1.

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

# graph is in edge list format
# 4 5
# 3 4
# 4 2
# 3 2
# 3 1
# 1 2

def adjacency_matrix(g):
    keys = sorted(g.keys())
    size = len(keys)
    m = [[0] * size for i in range(size)]
    for a, b in [(keys.index(a), keys.index(b)) for a, row in g.items()   
    for b in row]:
        m[a][b] = 0 if (a == b) else 1
    return m

def square_existence(graph):
    adjacency_matrix(graph)
    matrix = np.dot(graph, graph)
    size = len(matrix)
    return any([i != j and matrix[i][j] > 1 for j in range(size) for i in 
    range(size)])

Результат равен 1, что означает, что он содержит квадратный цикл.

...