¿Qué es la Parte II?

El gráfico bipartito, también llamado gráfico bipartito, es un modelo especial en la teoría de grafos. Significa que el conjunto de vértices se puede dividir en dos subconjuntos mutuamente disjuntos, y cada borde del gráfico está unido a los dos subconjuntos. Cada vértice pertenece a estos dos subconjuntos disjuntos y los vértices de los dos subconjuntos no son adyacentes.

Un método común para juzgar gráficos bipartitos es el método de teñido: tiñe cualquier vértice sin color y juzga sus vértices adyacentes, si no está teñido, tíñelo con un color diferente al de los vértices adyacentes. ha sido teñido y el color es el mismo que el color de los vértices adyacentes, significa que no es un gráfico bipartito. Si los colores son diferentes, continúe juzgando hasta que todos estén teñidos.