Dado un gráfico, ¿existe un enfoque bien conocido para determinar si el gráfico es bipartito? Si es así, ¿hay alguna forma de particionar el gráfico? Cuales son las formas?

Answer 1

Cada gráfico bipartito puede ser coloreado por dos colores, de modo que ningún vértice adyacente tenga el mismo color.

Elija cualquier vértice y asígnele el color rojo. Luego proceda coloreando a todos sus vecinos de azul. Para cada vértice coloreado, colorea a todos sus vecinos con el color opuesto. Si hay colisiones, lo que significa que queremos colorear un vértice con un color diferente al que tiene, abortamos y concluimos que el gráfico no puede ser bicolor y, por lo tanto, no es bipartito (debe contener un ciclo extraño).

Actualización [1]
Aquí hay algunas formas de particionar:

• agrupamiento espectral [2]
  

  los vértices corresponden a objetos de datos, los bordes corresponden a las relaciones entre objetos y los pesos de los bordes corresponden a la fuerza de las relaciones. el conjunto de vértices V se divide en dos subconjuntos V1 y V2. Luego, la agrupación se logra minimizando el corte

• Copartición coherente : realizar el método anterior por separado en {X, Y} y {Y, Z} [2]

1. Escribí esta respuesta rápidamente y pasé por alto la segunda parte de la pregunta:
2. inconveniente: problema de particionamiento:
   La respuesta de Sameer Gupta a ¿Cuáles son algunos buenos problemas con los juguetes (un solo codificador puede hacer durante un fin de semana) en ciencia de datos? Estoy estudiando el aprendizaje automático y las estadísticas, y estoy buscando algo socialmente relevante utilizando conjuntos de datos / API disponibles públicamente.

en.wikipedia.org/wiki/Bipartite_graph

Answer 2

” Un gráfico conectado no dirigido es bipartito si no hay un ciclo de longitud impar “. Esta condición se puede usar para verificar si un gráfico es bipartito (y también encontrar una partición si existe) en tiempo lineal usando BFS:

Idea conceptual:
Inicie la búsqueda en cualquier vértice y asigne etiquetas alternas a los vértices visitados durante la búsqueda: asigne la etiqueta 0 al vértice inicial, 1 a todos sus vecinos, 0 a los vecinos de esos vecinos, y así sucesivamente. Si en algún paso un vértice tiene (visitó) vecinos con la misma etiqueta que él mismo, entonces el gráfico no es bipartito (ya que esto implica que hay un ciclo de longitud impar). Si la búsqueda termina sin que ocurra tal situación, entonces el gráfico es bipartito. Además, todos los vértices etiquetados como 0 están en una partición y todos los vértices etiquetados como 1 están en otra partición.

Tiempo de ejecución: igual que el tiempo para un BFS (es decir, O (| E | + | V |))