Tabla de contenido:
Definición - ¿Qué significa Gráfico bipartito?
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 se pueden considerar iguales a dos gráficos coloreables. Los gráficos bipartitos se usan principalmente en relaciones de modelado, especialmente entre dos clases enteras de objetos separadas.
Un gráfico bipartito también se conoce como bigraph.
Techopedia 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 pueda conectarse entre cualquier vértice en A a cualquier vértice en B. Si el gráfico no contiene ninguno 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 requerido 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 son de longitud par. Según el teorema de coloración de línea de Koning, todos los gráficos bipartitos son gráficos de clase 1.
Los gráficos bipartitos se usan ampliamente en la teoría de codificación moderna, además de usarse en las relaciones de modelado.
