10 Abril, 2020, 07:29 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: ¡Atención! Hay que poner la matemática con LaTeX, y se hace así (clic aquí):
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: k-ésima potencia de un grafo y notación  (Leído 315 veces)
0 Usuarios y 1 Visitante están viendo este tema.
wrrp
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 5


Ver Perfil
« : 24 Noviembre, 2019, 01:09 »

Pobar que

[texx]d(P_n^k)>2k-1[/texx] donde [texx]n>k^2+k[/texx]
En línea
wrrp
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 5


Ver Perfil
« Respuesta #1 : 24 Noviembre, 2019, 01:12 »

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   [texx]P_n[/texx].
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 46.144


Ver Perfil
« Respuesta #2 : 24 Noviembre, 2019, 17:26 »

Hola

 Bienvenido al foro.

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

Pobar que

[texx]d(P_n^k)>2k-1[/texx] donde [texx]n>k^2+k[/texx]

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

[texx]v_1--v_2--v_3-.\ldots--v_n[/texx]

Entiendo que la potencia [texx]k[/texx]-é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 [texx]k[/texx].

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

Saludos.


[texx]^{(1)}[/texx] Enlace corregido.
En línea
wrrp
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 5


Ver Perfil
« Respuesta #3 : 24 Noviembre, 2019, 20:57 »

Hola

Muchas gracias por la bienvenida.

En cuanto a d se refiere a que d=[texx]\displaystyle\frac{1}{n}\cdot\sum_{i=1}^n{deg(v_i)}[/texx].
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 [texx]n-[/texx]vértices, ¿sera un árbol?.
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 46.144


Ver Perfil
« Respuesta #4 : 25 Noviembre, 2019, 03:40 »

Hola

Lo que no me queda muy claro es que es un camino de [texx]n-[/texx]vértices, ¿sera un árbol?.

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



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

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

El grado de los vértices [texx]1,2,\dots,k[/texx] es respectivamente:

[texx]k,k+1,k+2,\ldots,2k-1[/texx]

Idem para los [texx]k[/texx] últimos.

Entonces:

[texx]\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)[/texx]

y

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

Termina...

Saludos.

* pathgraph.png (14.07 KB - descargado 51 veces.)
En línea
wrrp
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 5


Ver Perfil
« Respuesta #5 : 01 Diciembre, 2019, 22:39 »

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:
[texx]\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)[/texx]
y por lo anterior tenemos:

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

porque [texx]1>\frac{k^2+k}{n}[/texx].

En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 46.144


Ver Perfil
« Respuesta #6 : 02 Diciembre, 2019, 03:40 »

Hola

 Está bien.

Saludos.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!