04 Abril, 2020, 09:47 *
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: Puedes practicar LATEX con el cómodo editor de Latex online
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Corte de un grafo  (Leído 140 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Julio_fmat
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 2.105



Ver Perfil WWW
« : 03 Noviembre, 2019, 22:17 »

Demuestre que todo grafo tiene un corte que contiene al menos la mitad de las aristas del grafo. En otras palabras, demuestre que todo grafo [texx]G[/texx] tiene un subconjunto de vertices [texx]X[/texx] tal que [texx]d(X)\ge \dfrac{m(G)}{2}.[/texx]

Hola, alguna idea para resolverlo? 
En línea

"Haz de las Matemáticas tu pasión".
manooooh
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 2.672


Ver Perfil
« Respuesta #1 : 03 Noviembre, 2019, 22:51 »

Hola

Demuestre que todo grafo tiene un corte que contiene al menos la mitad de las aristas del grafo. En otras palabras, demuestre que todo grafo [texx]G[/texx] tiene un subconjunto de vértices [texx]X[/texx] tal que [texx]d(X)\ge \dfrac{m(G)}{2}.[/texx]

Hola, ¿alguna idea para resolverlo? 

¿No es falso?

Considerá el siguiente grafo:


Vemos que en total tiene [texx]7[/texx] aristas. Si suprimimos el vértice rojo tenemos un grafo desconectado en el cual el vértice que quitamos sólo le incidían [texx]2[/texx] aristas, y [texx]2<\frac{7}{2}[/texx]. Por tanto el teorema es falso.

Incluso si mi definición de "Corte" no se aplicara a un vértice sino a aristas, tendríamos que si eliminamos la arista en verde nos queda un grafo desconectado tenemos que [texx]1<\frac{7}{2}[/texx].

O también puedo estar equivocándome yo.

Saludos

* ContraejemploGrafo.png (5.82 KB - descargado 35 veces.)
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!