Processing math: 2%

1 votos

Distancia media del gráfico totalmente conectado con cola

Tengo un grafo que está totalmente conectado con n y tiene una cola de longitud c adjunto:

enter image description here

En este ejemplo, n = 4 y c = 3.

En general, el diámetro de este gráfico es 1+c (atravesar desde el final de la cola hasta uno de los nodos del componente totalmente conectado).

¿Es posible encontrar una expresión para la distancia media (=distancia media entre todos los pares de nodos del grafo) de este grafo?

4voto

Casteels Puntos 8790

Sea K_n sea su parte totalmente conexa con conjunto de vértices v_1,\ldots,v_n . Sea P=(w_c,w_{c-1},\ldots,w_1) sea tu cola donde w_1 está conectado a v_1 por una sola arista.

Denote la distancia entre vértices a y b por d(a,b) .

Caso 1 : a=v_i y b=v_j para algunos i\neq j . Entonces d(v_i,v_j)=1 así que \sum_{i,j,i\neq j} d(v_i,v_j) =\sum_{i,j,i\neq j} 1 ={n\choose 2}.

Caso 2 : a=w_i y b=v_1 : Entonces d(a,b)=i así que \sum_{i=1}^c d(w_i,v_1) = 1+2+\cdots c = {c+1\choose 2}.

Caso 3 : a=w_i y b=v_j para j\neq 1 . Entonces d(a,b)=i+1 . Así \sum_{j=2}^n\sum_{i=1}^c d(w_i,v_j) = \sum_{j=2}^n\sum_{i=1}^c i+1 = (n-1)\left({c+1\choose 2}+c\right).

Caso 4 : a=w_i y b=w_j para algunos i<j . Entonces d(a,b)=j-i . Así que \sum_{j=1}^c\sum_{i=1}^{j-1} d(w_j,w_i) = \sum_{j=1}^c\sum_{i=1}^{j-1} j-i = {c+1\choose 3}.

Si lo juntamos todo, vemos que la distancia media es de

\frac{{n\choose 2}+n{c+1\choose 2}+c(n-1)+{c+1\choose 3}}{{n+c\choose 2}}.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X