Enviar respuesta 
 
Calificación:
  • 0 votos - 0 Media
  • 1
  • 2
  • 3
  • 4
  • 5
Buscar en el tema
Consulta ejercicios teóricos de grafos
Autor Mensaje
Apellidocomplicado Sin conexión
Militante
Sin estado :(
***

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 69
Agradecimientos dados: 21
Agradecimientos: 18 en 11 posts
Registro en: Sep 2015
Mensaje: #1
Consulta ejercicios teóricos de grafos Dudas y recomendaciones Matemática Discreta
Tengo una consulta con dos ejercicios de grafos de la guía

El 2)d) dice:
Cita:Si G es un grafo conexo con #A=26 y gr(v)>= 4 para todos los vértices de V, se pide indicar el mayor número del cardinal que puede alcanzar V.
Yo hice lo que está en el attachment.
¿Tiene sentido o mandé fruta mal?

El 2) e) dice
Cita:Si G es un grafo simple con 52 aristas, dar el menor número de vértices que puede tener.
¿Se aplica la misma propiedad, aún cuando no sabemos cómo están distribuidos los grados de los vértices, como en otros ejercicios donde dice "hay 3 vértices de grado 5, 4 de grado 6, etc?


Archivo(s) adjuntos Imagen(es)
   
01-02-2018 18:17
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
manoooooh Sin conexión
Profesor del Modulo A
Sin estado :(
*****

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 227
Agradecimientos dados: 0
Agradecimientos: 80 en 64 posts
Registro en: Feb 2017
Mensaje: #2
RE: Consulta ejercicios teóricos de grafos
Hola,

(01-02-2018 18:17)Apellidocomplicado escribió:  
Cita:Si G es un grafo conexo con #A=26 y gr(v)>= 4 para todos los vértices de V, se pide indicar el mayor número del cardinal que puede alcanzar V.

[Imagen: attachment.php?aid=16125]

¿Por qué multiplicás los vértices por los grados de los vértices? Además escribís \[V\cdot g(v)=2A\] como ecuación y luego \[V\cdot 4\geq 2A\] como inecuación, pero llegás al resultado correcto.

Si todos los n vértices tienen orden 4, deben haber \[\dfrac {4n}2=2n\] aristas. Como nos dicen que el número de aristas es 26 debe ser \[n\leq 13.\]



(01-02-2018 18:17)Apellidocomplicado escribió:  
Cita:Si G es un grafo simple con 52 aristas, dar el menor número de vértices que puede tener.

¿Se aplica la misma propiedad, aún cuando no sabemos cómo están distribuidos los grados de los vértices, como en otros ejercicios donde dice "hay 3 vértices de grado 5, 4 de grado 6, etc?

No. Un grafo simple completo de n vértices, tiene como máximo número de aristas \[\dfrac {n(n-1)}2\] con n vértices. Para \[n=10\] son 45 aristas, insuficiente, y para \[n=11\] son 55. Debe tener por tanto al menos 11 vértices.

P.D.: La imagen es innecesaria en este caso, ya que todo lo que aparece se puede teclear. Recordá usar para las fórmulas LaTeX: acá podés ver cómo se utiliza.

Saludos
(Este mensaje fue modificado por última vez en: 01-02-2018 21:39 por manoooooh.)
01-02-2018 21:34
Envíale un email Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Buscar en el tema
Enviar respuesta 




Usuario(s) navegando en este tema: 1 invitado(s)



    This forum uses Lukasz Tkacz MyBB addons.