Строение ДСД: набор узлов, объединенных с помощью ссылок. Вид узла: Данные+ссылки на другие узлы. Типы структур: Списки, деревья, графы.
Граф – это набор вершин (узлов) и соединяющих их ребер (дуг).
Направленный граф (ориентированный, орграф) – это граф, в котором все дуги имеют направления.
Цепь – это последовательность ребер, соединяющих две вершины (в орграфе – путь).
Цикл – это цепь из какой-то вершины в нее саму.
Взвешенный граф (сеть) – это граф, в котором каждому ребру приписывается вес (длина).
Связный граф – это граф, в котором существует цепь между каждой парой вершин.
k-cвязный граф – это граф, который можно разбить на k связных частей.
Полный граф – это граф, в котором проведены все возможные ребра (n вершин → n(n-1)/2 ребер).
Матрица смежности – это матрица, элемент M[i][j] которой равен 1, если существует ребро из вершины i в вершину j, и равен 0, если такого ребра нет.
Задача: определить, существует ли цепь длины k из вершины i в вершину j (или цикл длиной k из вершины i в нее саму).
M2[i][j]=1, если M[i][1]=1 и M[1][j]=1 или M[i][2]=1 и M[2][j]=1 или M[i][3]=1 и M[3][j]=1 и т.д.
Логическое умножение матрицы на себя:
M2 = M х M
В получившейся матрице имеем матрицу с длинами путей 2. Если по главной диагонали будут 1, значит имеем цикл, длиной 2.
25.
