Gráfica bipartita
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 4 de octubre de 2020; las comprobaciones requieren 12 ediciones .Un grafo bipartito o bígrafo en teoría de grafos es un grafo cuyo conjunto de vértices se puede dividir en dos partes de tal manera que cada arista del grafo conecta un vértice de una parte con algún vértice de la otra parte, es decir, hay sin bordes entre los vértices de las mismas partes del gráfico.
Definición
Un grafo no dirigido se llama bipartito si el conjunto de sus vértices se puede dividir en dos partes de manera que:
- ningún vértice en está conectado a los vértices en
- ningún vértice en está conectado a los vértices en
En este caso, los subconjuntos de vértices y se denominan partes de un grafo bipartito .
Definiciones relacionadas
Un grafo bipartito se llama grafo bipartito completo (este concepto es diferente de un grafo completo , es decir, uno en el que cada par de vértices está conectado por una arista) si hay una arista para cada par de vértices . Para
dicho gráfico se denota con el símbolo .
Ejemplos
Los grafos bipartitos surgen naturalmente cuando se modelan las relaciones entre dos clases diferentes de objetos. Por ejemplo, el gráfico de jugadores y clubes de fútbol: un borde conecta el jugador correspondiente y el club si el jugador jugó en este club. Más ejemplos abstractos de grafos bipartitos:
- árbol _
- Un ciclo simple que consta de un número par de vértices.
- Cualquier gráfico plano cuyas caras estén limitadas por un número par de aristas.
Los gráficos bipartitos se utilizan para describir los códigos LDPC .
Propiedades
- Un grafo es bipartito si y solo si no contiene un ciclo de longitud
impar .
- En particular, un gráfico bipartito no puede contener una camarilla de tamaño mayor que 2.
- Un grafo es bipartito si y solo si es bicromático; es decir, su número cromático es dos.
- El gráfico se divide en pares de vértices multicolores si y solo si algún elemento de una de las partes está conectado al menos con elementos de la otra ( teorema de boda ).
- Un grafo bipartito completo con más de 2 vértices en cada parte no es plano .
- Cualquier gráfico bipartito es perfecto .
Comprobación de bipartito
Para verificar la bipartición del gráfico, es suficiente seleccionar cualquier vértice en cada componente conexa y marcar los vértices restantes durante el recorrido del gráfico (por ejemplo, mediante búsqueda en anchura ) alternativamente como pares e impares (ver ilustración) . Si no hay conflicto, todos los vértices pares forman el conjunto y todos los vértices impares forman .
Aplicaciones
- redes de petri
- Conde Levy
- teoría de la codificación
- gráfica de factores
- Conde de Tanner