Un Grafo bipartito se denomina en Teoría de grafos a un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos V1 y V2 y las aristas siempre unen vértices de un conjunto con vértices de otro:
no existe ninguna arista e = (x1,x2) ni e = (y1,y2)
Siendo V el conjunto que contiene todos los vértices del grafo.
El conjunto de todos los grafos bipartitos es denominado ![{K}^{\left [2\right ]}](http://upload.wikimedia.org/math/3/9/e/39ee578001da9ecdb137bc5669c5c4d0.png)
; en particular, un grafo bipartito uniendo dos conjuntos, de m y n elementos, respectivamente, se denota por ![{K}^{\left [2\right ]}_{m,n}](http://upload.wikimedia.org/math/e/d/8/ed8c4b142dd240829ffb90a9050616bb.png)
, o, simplemente, Km,n.
Un grafo bipartito en el cual todos los elementos de V1 están unidos con todos los elementos de V2 se denomina bipartito completo
Los grafos bipartitos suelen representarse gráficamente con dos columnas (o filas) de vértices y las aristas uniendo vértices de columnas (o filas) diferentes.
Un árbol.
Un grafo sin ciclos de tamaño impar.
No hay comentarios:
Publicar un comentario