Grafo bipartito

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.​ 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.​ 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-partito completo, como uno en que todos los pares de vértices pertenecientes a subconjuntos diferentes son adyacentes.​