Matemática => Teoría de grafos => Mensaje iniciado por: Julio_fmat en 03 Noviembre, 2019, 22:17



Título: Corte de un grafo
Publicado por: Julio_fmat en 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?  ???


Título: Re: Corte de un grafo
Publicado por: manooooh en 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:

(http://rinconmatematico.com/foros/index.php?action=dlattach;topic=111113.0;attach=21394)

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