Loading [MathJax]/extensions/TeX/mathchoice.js

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 Kn sea su parte totalmente conexa con conjunto de vértices v1,,vn . Sea P=(wc,wc1,,w1) sea tu cola donde w1 está conectado a v1 por una sola arista.

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

Caso 1 : a=vi y b=vj para algunos ij . Entonces d(vi,vj)=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