Definición - ¿Qué significa Bipartite Graph?
Un gráfico bipartito es un gráfico en el que un conjunto de vértices de gráfico se puede dividir en dos conjuntos independientes, y no hay dos vértices de gráfico dentro del mismo conjunto adyacentes. En otras palabras, los gráficos bipartitos pueden considerarse iguales a dos gráficos coloreables. Los gráficos bipartitos se utilizan principalmente en el modelado de relaciones, especialmente entre dos clases de objetos completamente separadas.
Un gráfico bipartito también se conoce como bigraph.
Techinfo explica el gráfico bipartito
Un gráfico bipartito tiene dos conjuntos de vértices, por ejemplo A y B, con la posibilidad de que cuando se dibuja un borde, la conexión debería poder conectarse entre cualquier vértice en A y cualquier vértice en B. Si el gráfico no contiene ningún ciclo impar (el número de vértices en el gráfico es impar), entonces su espectro es simétrico. El número cromático, que es el número mínimo de colores necesarios para colorear los vértices sin vértices adyacentes que comparten los mismos colores, debe ser menor o igual a dos en el caso de un gráfico bipartito. Todos los tipos de gráficos acíclicos (gráficos que no tienen ciclos de gráficos) son ejemplos de gráficos bipartitos. Un gráfico cíclico se considera bipartito si todos los ciclos involucrados tienen una duración uniforme. Según el teorema de coloración de líneas de Koning, todos los gráficos bipartitos son gráficos de clase 1.
Los gráficos bipartitos se utilizan ampliamente en la teoría de codificación moderna, además de utilizarse en el modelado de relaciones.