Grafo bipartito
Artículo
Discusión
Leer
Editar
Ver historial
Herramientas
Ejemplo de grafo bipartito.
Grafo bipartito con un subconjunto V1 y otro V2
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.1
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.1
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.1
Definición formal
Un grafo
�
=
(
�
,
�
)
{\displaystyle G=(N,E)} es bipartito si N se puede particionar en dos conjuntos U y
V, es decir, tal que
�
∪
�
=
�
{\displaystyle U\cup V=N} y
�
∩
�
=
∅{\displaystyle U\cap V=\emptyset }, de manera que las aristas sólo pueden conectar
vértices de un conjunto con vértices del otro; formalmente:
∀
�
1
,
�
2
∈
�
,
∀
�
1
,
�
2
∈
�
{\displaystyle \forall u_{1},u_{2}\in U,\forall v_{1},v_{2}\in V} no existe ninguna
arista
�
=
(
�
1
,
�
2
)
{\displaystyle e=(u_{1},u_{2})} ni
�
=
(
�
1
,
�
2
)
{\displaystyle e=(v_{1},v_{2})}.
Representación
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.
Ejemplos
Los grafos bipartitos son utilizados, naturalmente, cuando se modelan relaciones
entre dos diferentes clases de objetos. Por ejemplo, un grafo 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.2
Todo grafo sin ciclos de longitud impar es bipartito. Como consecuencia de esto:
Todo árbol es bipartito.
Los grafos cíclicos con un número par de vértices son bipartitos.
Todo grafo planar donde todas las caras tienen un número par de aristas es
bipartito.
Aplicaciones
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.1
Véase también
Grafo bipartito completo
Referencias
Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.
Stanley., Wasserman, (1994). Social network analysis : methods and applications.
Cambridge University Press. ISBN 9780521387071. OCLC 818663583.
Bibliografía
Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales:
Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-
84-7476-631-8. OCLC 871814053.
Control de autoridades
Proyectos WikimediaWd Datos: Q174733Commonscat Multimedia: Bipartite graphs /
Q174733
Categorías: Familias de grafosParidad (matemáticas)
