Autor Tema: k-ésima potencia de un grafo y notación

0 Usuarios y 1 Visitante están viendo este tema.

24 Noviembre, 2019, 05:09 am
Leído 1111 veces

wrrp

  • $$\Large \color{red}\pi$$
  • Mensajes: 5
  • Karma: +0/-0
  • Sexo: Masculino
Pobar que

\( d(P_n^k)>2k-1 \) donde \( n>k^2+k \)

24 Noviembre, 2019, 05:12 am
Respuesta #1

wrrp

  • $$\Large \color{red}\pi$$
  • Mensajes: 5
  • Karma: +0/-0
  • Sexo: Masculino
de antemano me disculpo si este no es el lugar adecuado para publicar este mensaje, pero encontre este problema y no he podido encontrar que es   \( P_n \).

24 Noviembre, 2019, 09:26 pm
Respuesta #2

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

 Bienvenido al foro.

 Recuerda leer y seguir  las reglas\( ^{(1)} \) del mismo así como el tutorial del LaTeX para escribir las fórmulas matemáticas correctamente.

Pobar que

\( d(P_n^k)>2k-1 \) donde \( n>k^2+k \)

Supongo que \( P_n \) se refiere al camino ("path graph") de \( n \)-vértices. Es decir el grafo:

\( v_1--v_2--v_3-.\ldots--v_n \)

Entiendo que la potencia \( k \)-ésima del grafo se refiera esto: el grafo con los mismos vértices y aristas uniendo vértices que en el grafo original estban a lo sumo a distancia \( k \).

Lo que no estoy seguro que estás denotando por \( d(P_n^k) \). ¿El diámetro?. Si fuese así el resultado no veo que sea cierto, porque si consideramos \( n=13 \) y \( k=3 \), se tiene que \( n>3^2+3 \), pero el diámetro de \( P_{13}^3 \) es (creo) \( 4 \), que no cumple \( 4>2\cdot 3-1 \).

Saludos.


\( ^{(1)} \) Enlace corregido.

25 Noviembre, 2019, 12:57 am
Respuesta #3

wrrp

  • $$\Large \color{red}\pi$$
  • Mensajes: 5
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Muchas gracias por la bienvenida.

En cuanto a d se refiere a que d=\( \displaystyle\frac{1}{n}\cdot\sum_{i=1}^n{deg(v_i)} \).
En cuanto a la potencia de un grafo estamos de acuerdo en los conceptos.
Lo que no me queda muy claro es que es un camino de \( n- \)vértices, ¿sera un árbol?.

25 Noviembre, 2019, 07:40 am
Respuesta #4

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Lo que no me queda muy claro es que es un camino de \( n- \)vértices, ¿sera un árbol?.

No. No coloqué el enlace que pretendía; lo he corregido. El grafo \( P_n \) es el grafo que tiene los vértices \( v_1,v_2,\ldots,v_n \) y aristas únicamente \( (v_i,v_i+1) \) con \( i=1,2,\ldots,n-1 \).



En cuanto a d se refiere a que d=\( \displaystyle\frac{1}{n}\cdot\sum_{i=1}^n{deg(v_i)} \).

Bien. Entonces nota que en \( P_n^k \), exceptuando los primeros y últimos \( k \) vértices, el resto de ellos tiene grado \( 2k \), porque están asociados con \( k \) vértices a izquierda y derecha.

El grado de los vértices \( 1,2,\dots,k \) es respectivamente:

\( k,k+1,k+2,\ldots,2k-1 \)

Idem para los \( k \) últimos.

Entonces:

\( \displaystyle\sum_{i=1}^n{deg(v_i)}=2(k+(k+1)+(k+2)+\ldots+(2k-1))+(n-2k)\cdot 2k=(3k-1)k+(n-2k)2k=2kn-(k^2+k) \)

y

\( d(P_n^k)=\dfrac{1}{n}\displaystyle\sum_{i=1}^n{deg(v_i)}=2k-\dfrac{k^2+k}{n} \)

Termina...

Saludos.

02 Diciembre, 2019, 02:39 am
Respuesta #5

wrrp

  • $$\Large \color{red}\pi$$
  • Mensajes: 5
  • Karma: +0/-0
  • Sexo: Masculino
Hola, perdon por no contestar rapido, es que se me había dificultado entender algunas cuestiones.
Ya tengo lo que creo que puede ser la demostración...

Demostración:

Se sabe que:
\( \displaystyle\sum_{i=1}^n{deg(v_i)}=2(k+(k+1)+\ldots + (k+k-1))+2k(n-2k)=(3k−1)k+(n−2k)2k=2kn−(k^2+k) \)
y por lo anterior tenemos:

d\( (P_n^k)=2k-\frac{k^2+k}{n}>2k-1 \)

porque \( 1>\frac{k^2+k}{n} \).


02 Diciembre, 2019, 07:40 am
Respuesta #6

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino