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



Título: Conjunto independiente maximal 2
Publicado por: Julio_fmat en 03 Noviembre, 2019, 23:02
Encuentre un conjunto independiente maximo en el [texx]k[/texx]-cubo.

Hola, sabemos que un conjunto es independiente si [texx]\forall u,v\in X[/texx], se tiene que [texx]\{u,v\}\notin E.[/texx]


Título: Re: Conjunto independiente maximal 2
Publicado por: Luis Fuentes en 04 Noviembre, 2019, 07:27
Hola

Encuentre un conjunto independiente maximo en el [texx]k[/texx]-cubo.

Hola, sabemos que un conjunto es independiente si [texx]\forall u,v\in X[/texx], se tiene que [texx]\{u,v\}\notin E.[/texx]

Utiliza este ejercicio:

http://rinconmatematico.com/foros/index.php?topic=111112.msg439342;topicseen#msg439342

Prueba que cualquiera de los dos subconjuntos que dan al grafo estructura de grafo bipartito son un conjunto independiente máximo.

Que es independiente es obvio; para ver que es máximo, razona por inducción que el número máximo posible de vértices independientes en un [texx]k[/texx]-cubo es [texx]2^{k-1}[/texx]. Nota que dad un [texx]k[/texx]-cubo podemos considerar los [texx]k-1[/texx]-cubos dados por los vertices:

[texx]V_0=\{(a_1,a_2,\ldots,a_{n-1},0)\}[/texx]
[texx]V_1=\{(a_1,a_2,\ldots,a_{n-1},1)\}[/texx]

y cualquier conjunto maximal de vértices del [texx]k[/texx]-cubo intersecado con [texx]V_0[/texx] y [texx]V_1[/texx] no puede tener más vértices que el número máximo de vértices independientes en el [texx](k-1)[/texx]-cubo.

Saludos.