Пусть G = (V, E) - неориентированный граф.Найдите наиболее эффективный алгоритм, чтобы определить, имеет ли G клику размером> = 3.
, что я думаю: если G имеет клику размером больше 3, то она, безусловно, имеет клику размера 3, поэтому мыпросто нужно найти клику размером 3.
. Поэтому мой алгоритм таков: я использую матрицу адъюнктивности для представления G.
1. run DFS on G
2. for each v in V
2.1 for each u in Adj[v]
2.1.1 if v.pi != u
2.1.1.1 if (v.pi,u) is an edge in G
2.1.1.1.1 return TRUE
3. return FALSE
сложность: если G представлен в матрице адж, DFSбудет O (V ^ 2).
Для каждого v в V мы проверяем все Adj [v], поэтому мы проверяем все вершины и ребра в G - O (V + E)
Чтобы проверить, что две вершины v.pi, u образуют ребро, e = (v.pi, u) равно O (1)
Следовательно, сложность O (V ^ 2)
Am Iправо?Спасибо