Suma de los caminos más cortos en el gráfico

Question

Dejemos que $d_{G} \left(x,y \right)$ sea la longitud del camino más corto entre los vértices $x$ y $y$ en el gráfico $G$ y que $s\left(G\right) = \sum_{x,y \in V \left[G\right]} d_{G} \left(x,y \right)$ . Para qué grafos no dirigidos de 2 vértices conectados $G$ , valor $S(G)$ es el más alto?

Answer 1

Es un ciclo, supongamos que hay otro gráfico $G$ que no es un ciclo y tiene la suma máxima deseada, tiene algunos nodos como $v$ con grado superior a dos y su grado es mínimo (por esta condición). $v$ Los vecinos de la empresa son $x_1,x_2,...x_r$ les mostramos por $N_1(v)$ , También $v$ está en algún ciclo como $C$ porque $G$ es dos conectados, suponga vecinos de $v$ en $C$ son $x_1,x_2$ , ahora si te mueves $x_2,x_3,..,x_r$ en $C$ y crear $C'$ por: $x_1,v,x_2,x_3,...,x_r,...,x_1$ y dejemos que las demás conexiones sean las mismas, el nuevo grafo creado es biconectado, porque hay dos vías entre los vértices interiores de $C'$ Además, por nuestra construcción no afectamos a la conexión de los vértices exteriores, sólo sustituimos una arista por un camino. También $G'$ tiene mayor suma de camino más corto, porque de nuevo no disminuimos la longitud de un camino entre vértices de $O = G\backslash (C\cup N_1(v))$ Además, no cambiamos la longitud de un camino entre vértices en $O$ y $N_1(v) \cup C$ pero la longitud del camino más corto entre $v$ y $x_3$ aumentada (en 1). Así que el nuevo gráfico $G'$ tiene una mayor suma de caminos más cortos, pero esto contradice nuestra suposición. Así que $G$ no puede tener un vértice de grado superior a 2. y como son dos conectados, es un ciclo.