Combinatoria
Olimpiada Tuymaada (2023)
Olimpiada Tuymaada 2023 Problema 2
2 En un grafo con $n$ vértices, cada dos vértices están conectados por un único camino. Para cada dos vértices $u$ y $v$, sea $d(u, v)$ la distancia entre $u$ y $v$, es decir, el número de aristas en el camino que conecta estos dos vértices, y $\deg(u)$ el grado de un vértice $u$. Sea $W$ la suma de las distancias por pares entre los vértices, y $D$ la suma de las distancias por pares ponderadas: $\sum_{\{u, v\}}(\deg(u)+\deg(v))d(u, v)$. Demuestra que $D=4W-n(n-1)$.
0
0
Kevin
Inicia sesión para agregar soluciones y pistas