Considere un gráfico no ponderado no dirigido simple con al menos tres vértices. Si A es la array de adyacencia del gráfico, entonces el número de 3 ciclos en el gráfico viene dado por la traza de
(A)
un 3
(B)
Un 3 dividido por 2
(C)
Un 3 dividido por 3
(D)
Un 3 dividido por 6
Respuesta: (D)
Explicación:
Sea A[][] la representación matricial de adyacencia del grafo.
Si calculamos A 3 , entonces el número de triángulos en el gráfico no dirigido es igual a trace(A 3 ) / 6.
Donde trace(A) es la suma de los elementos en la diagonal principal de la array A. Trace de un gráfico representado como array de adyacencia A[V][V] es,
traza(A[V][V]) = A[0][0] + A[1][1] +….. + A[V-1][V-1]
Cuenta de triángulos = traza(A 3 ) / 6
Si calculamos A n para una representación de array de adyacencia del gráfico, entonces un valor A n [i][j] representa el número de caminatas distintas entre el vértice i al j en el gráfico.
En A 3 , entre cada par de vértices, recibimos todas las rutas diferentes de longitud
3. Un triángulo es una ruta cíclica tridimensional que comienza y termina en el mismo vértice.
Entonces A 3 [i][i] representa un triángulo que comienza y termina en el vértice i.
Debemos dividir el resultado por tres ya que un triángulo tiene tres vértices y cada vértice se cuenta por separado.
Además, dado que la gráfica no está dirigida, cada triángulo es el doble de ipqj e iqpj, por lo que también dividimos por 2.
Por lo tanto, el número de triángulos es una traza (A 3 ) / 6.
Cuestionario de esta pregunta
Comente a continuación si encuentra algo incorrecto en la publicación anterior
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA