El radio, el diámetro y el centro del gráfico

Question

La excentricidad $ecc(v)$ de $v$ en $G$ es la mayor distancia de $v$ a cualquier otro nodo.

El radio $rad(G)$ de $G$ es el valor de la más pequeña excentricidad.

El diámetro $diam(G)$ de $G$ es el valor de la mayor excentricidad.

El centro de $G$ es el conjunto de nodos $v$ de tal manera que $ecc(v) = rad(G)$

Encuentra el radio, el diámetro y el centro del gráfico: http://gyazo.com/69685c4d20adc762e020264ddc3b089f Agradezco toda la ayuda posible.

Intenté seguir un ejemplo y aún no lo conseguí, cuando cuentas la distancia de un nodo a otro, ¿contas el nodo de inicio también o cuentas el nodo final en su lugar? Y cuando cuentas, ¿contas los de arriba y abajo o cómo cuentas? :)

Answer 1

La distancia se define como el número de aristas del camino más corto entre los vértices. Por ejemplo, los vértices adyacentes tienen una distancia de $1$ .

En su gráfico, podría ser útil enumerar explícitamente la excentricidad de cada vértice. No es demasiado difícil calcular la excentricidad de cada vértice. A continuación he etiquetado tu gráfico con las excentricidades de los vértices

                                             

Se puede ver que en este gráfico, las mayores excentricidades se producen en los lados del gráfico, siendo la mayor (el diámetro) $6$ . La menor excentricidad se produce en el vértice central con una excentricidad de $3$ . Este es su radio. Su centro consiste en todos los vértices que tienen una excentricidad igual al radio, en este caso $3$ . Para este gráfico, sólo hay un único vértice de este tipo, por lo que su centro en el único vértice etiquetado $3$ en el gráfico.

Puede ver que el nombre centro tiene un nombre muy acertado. Los vértices del centro minimizan la distancia máxima a cualquier vértice del grafo y en este sentido, realmente son los vértices más centrales del grafo.

Answer 2

Creo que para el grafo de trayectoria Pn, el diámetro es n-1.Pero el radio es (n-1/2)redondeado al entero más cercano. Por ejemplo, P3 tiene un radio de 1 pero no de 2.

Answer 3

para encontrar el radio de un grafo conectado G denotado por r=[v+e]÷[e-2] donde v=vértice del gráfico e=borde del grafo