Foros de matemática
22/11/2017, 04:12:35 am *
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: Ejercicio de grafos  (Leído 69 veces)
0 Usuarios y 1 Visitante están viendo este tema.
manooooh
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 148


Ver Perfil
« : 13/11/2017, 07:45:55 pm »

Hola a todos! El enunciado está adjunto en la imagen.





Punto a):

[texx]G_1[/texx] no tiene camino de Euler pues [texx]\exists{}C, D, E \in{} V \; / \; g(A) = g(C) = g(D) = g(E) = 3[/texx] (hay más de 2 vértices de grado impar).

Para que [texx]G_1[/texx] tenga camino de Euler basta suprimir 1 sola arista: por ejemplo, la que va de [texx]C[/texx] a [texx]D[/texx] (aunque haya 2 vértices de grado impar -[texx]A[/texx] y [texx]E[/texx]- la condición de camino de Euler es con la excepción de 2 vértices de grado impar).

Punto b):
[texx]\boxed{\textrm{Matriz de adyacencia } M_a = (m_{ij}) = \begin{cases} 1 & v_i \wedge v_j \textrm{ son adyacentes} \\ 0 & \textrm{caso contrario} \end{cases}}[/texx]

[texx]\boxed{M_a = \begin{pmatrix} 0 & 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}}[/texx]

El grafo es conexo pues entre 2 vértices cualesquiera existe al menos un camino.

El grafo es simple porque no repite vértices.

El grafo no tiene ciclos pues [texx]\textrm{#} \varphi (a_i) = 1[/texx].

El grafo tiene aristas puente pues [texx]\tilde{G}_a[/texx] es no conexo (¿esto es así? ¿Cómo lo vería visualmente? Me faltan decir cuáles serían).




¿Pueden corregirme si hay algo mal por favor?

Gracias!!

* EjercicioN3.jpg (222.84 KB - descargado 15 veces.)
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 40.308


Ver Perfil
« Respuesta #1 : 14/11/2017, 05:44:12 am »

Hola

Hola a todos! El enunciado está adjunto en la imagen.





Punto a):

[texx]G_1[/texx] no tiene camino de Euler pues [texx]\exists{}C, D, E \in{} V \; / \; g(A) = g(C) = g(D) = g(E) = 3[/texx] (hay más de 2 vértices de grado impar).

Para que [texx]G_1[/texx] tenga camino de Euler basta suprimir 1 sola arista: por ejemplo, la que va de [texx]C[/texx] a [texx]D[/texx] (aunque haya 2 vértices de grado impar -[texx]A[/texx] y [texx]E[/texx]- la condición de camino de Euler es con la excepción de 2 vértices de grado impar).

Punto b):
[texx]\boxed{\textrm{Matriz de adyacencia } M_a = (m_{ij}) = \begin{cases} 1 & v_i \wedge v_j \textrm{ son adyacentes} \\ 0 & \textrm{caso contrario} \end{cases}}[/texx]

[texx]\boxed{M_a = \begin{pmatrix} 0 & 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}}[/texx]

El grafo es conexo pues entre 2 vértices cualesquiera existe al menos un camino.

Bien.

Cita
El grafo es simple porque no repite vértices.

Supongo que querías decir: porque no hay dos aristas uniendo el mismo par de vértices.

Cita
El grafo no tiene ciclos pues [texx]\textrm{#} \varphi (a_i) = 1[/texx].

¿A qué estás llamando [texx]\textrm{#} \varphi (a_i)[/texx]?. Sea como sea...¡si tiene ciclos!. Por ejemplo: [texx]A-B-D-A[/texx]

Cita
El grafo tiene aristas puente pues [texx]\tilde{G}_a[/texx] es no conexo (¿esto es así? ¿Cómo lo vería visualmente? Me faltan decir cuáles serían).

¿A qué llamas [texx]\tilde{G}_a[/texx]?. Sea como sea el grafo no tiene aristas puente: si las hubiese podrías retirar una arista, y el grafo dejaría de ser conexo. Pero en tu grafo (se puede comprobar por inspección) quites la arista que quites sigue siendo conexo.

Saludos.
En línea
manooooh
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 148


Ver Perfil
« Respuesta #2 : 14/11/2017, 08:58:38 am »

Hola

Hola a todos! El enunciado está adjunto en la imagen.





Punto a):

[texx]G_1[/texx] no tiene camino de Euler pues [texx]\exists{}C, D, E \in{} V \; / \; g(A) = g(C) = g(D) = g(E) = 3[/texx] (hay más de 2 vértices de grado impar).

Para que [texx]G_1[/texx] tenga camino de Euler basta suprimir 1 sola arista: por ejemplo, la que va de [texx]C[/texx] a [texx]D[/texx] (aunque haya 2 vértices de grado impar -[texx]A[/texx] y [texx]E[/texx]- la condición de camino de Euler es con la excepción de 2 vértices de grado impar).

Punto b):
[texx]\boxed{\textrm{Matriz de adyacencia } M_a = (m_{ij}) = \begin{cases} 1 & v_i \wedge v_j \textrm{ son adyacentes} \\ 0 & \textrm{caso contrario} \end{cases}}[/texx]

[texx]\boxed{M_a = \begin{pmatrix} 0 & 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}}[/texx]

El grafo es conexo pues entre 2 vértices cualesquiera existe al menos un camino.

Bien.

Cita
El grafo es simple porque no repite vértices.

Supongo que querías decir: porque no hay dos aristas uniendo el mismo par de vértices.

Cita
El grafo no tiene ciclos pues [texx]\textrm{#} \varphi (a_i) = 1[/texx].

¿A qué estás llamando [texx]\textrm{#} \varphi (a_i)[/texx]?. Sea como sea...¡si tiene ciclos!. Por ejemplo: [texx]A-B-D-A[/texx]

Cita
El grafo tiene aristas puente pues [texx]\tilde{G}_a[/texx] es no conexo (¿esto es así? ¿Cómo lo vería visualmente? Me faltan decir cuáles serían).

¿A qué llamas [texx]\tilde{G}_a[/texx]?. Sea como sea el grafo no tiene aristas puente: si las hubiese podrías retirar una arista, y el grafo dejaría de ser conexo. Pero en tu grafo (se puede comprobar por inspección) quites la arista que quites sigue siendo conexo.

Saludos.

Hola, con lo de los ciclos tenés razón, me confundí con lazos/bucles.
Con lo de aristas puente tenés razón, no tenía una definición más "simple".

Gracias!
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

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