lunes, 22 de agosto de 2011

graficas bipartitas

Sea r ≥ 2 un entero. Una grafica G = (V, E) es r-partita si existe una particion de V en r conjuntos independientes, que llamamos clases. En vez de decir 2-partita, decimos bipartita.
Una grafica r-partita donde cada par de vertices de distintas clases es adyacente se llama una grafica r-partita completa, o tambien multipartita completa.
Una grafica r-partita completa con clases de ni vertices se denota Kn1,...nr;cuando n1 = . . . = nr = s, la denotamos Ks,r. Entonces Ks,r es la grafica r-partita completa donde cada clase tiene exactamente s vertices. Las graficas K1,n son arboles pero se llaman estrellas por obvias azones.

Teorema 1. Una grafica es bipartita si y solo si no contiene un ciclo impar.

Demostracion. Sea G una grafica bipartita con biparticion (V1, V2), y sea x1x2 · · · xℓ un ciclo de G. Podemos suponer que x1 ∈ V1. Entonces x2 ∈ V2, x3 ∈ V1, etc.
Entonces xi ∈ V1 si y solo si i es impar. Ya que xℓ ∈ V2, ℓ es par.
Ahora supongamos que G no contiene ningun ciclo impar. Ademas, podemos suponer que G es conexa, porque una grafica es bipartita si y solo si cada componente es bipartita. Sea x ∈ V (G) y definimos V1 = {y ∈ V (G) | dist(x, y) ≡ 1 (mod 2)}, V2 = V (G) \ V1. Si existiera una arista xy ∈ E(G) tal que x, y ∈ Vi (i = 1 o 2), entonces G contendrıa un ciclo impar, lo que es mposible. Por lo tanto G es bipartita.

No hay comentarios:

Publicar un comentario en la entrada