En teoría de grafos, un grafo bipartito es un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos, de manera que las aristas no pueden relacionar vértices de un mismo conjunto.
Un grafo bipartito completo es un grafo bipartito en que todos los vértices de uno de los subconjuntos están relacionados con los del otro subconjunto.
Este concepto se puede generalizar al de grafo s-partito, como un grafo cuyo conjunto de vértices se puede particionar en s subconjuntos, de modo que las aristas solo conectan a vértices de subconjuntos diferentes. Análogamente, también se puede definir un grafo s-bipartito completo, como uno en que todos los pares de vértices pertenecientes a subconjuntos diferentes son adyacentes.
Un grafo G=(N, E) es bipartito si N se pueden separar en dos conjuntos U y V tal que se cumple
de manera que las aristas sólo pueden conectar vértices de un conjunto con vértices del otro; es decir:
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.
Los dos conjuntos U y V pueden ser pensados como un coloreo del grafo con dos colores: si pintamos los vértices en U de azul y los vértices de V de verde obtenemos un grafo de dos colores donde cada arista tiene un vértice azul y el otro verde. Por otro lado, si un grafo no tiene la propiedad de que se puede colorear con dos colores no es bipartito.
Un grafo bipartito con la partición de los vértices en U y V suele denotarse G = (U, V, E). Si |U| =|V|, esto es, si los dos subconjuntos tiene la misma cantidad de elementos o cardinalidad, decimos que el grafo bipartito G es balanceado. Si todos los vértices del mismo lado de la bipartición tienen el mismo grado, entonces G es llamado grafo birregular.
Los grafos bipartitos son utilizados, naturalmente, cuando se modelan relaciones entre dos diferentes clases de objetos. Por ejemplo, un grado conformado por dos conjuntos: jugadores de fútbol y clubes deportivos, con una arista entre cada jugador y un club, tal que el jugador ha jugado para dicho club; es un ejemplo natural de una red de afiliación, un tipo de grafo bipartito utilizado en el análisis de redes sociales.
En análisis de redes sociales, las redes diádicas son redes bimodales que se pueden representar como grafos bipartitos. Sin embargo, también se pueden definir grafos bipartitos sobre redes unimodales.
Escribe un comentario o lo que quieras sobre Grafo bipartito (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)