Como faço para particionar um grafo bipartido por cor?

Question

Por exemplo, suponha que tem um grafo G = (V, E) onde

V = {A, B, C, D}
E = {(A, B), (A, D), (C, D)}

Este gráfico é bipartido, e, portanto, pode ser dividida em dois conjuntos disjuntos {A, C} e {B, D}. Minha primeira suposição é que eu posso simplesmente andar pelas cores do gráfico e de alternâncias de atribuir a cada vértice. É este o caso, ou é mais complicado / mais simples do que isso? Há algum algoritmos conhecidos para isso?

Answer 1

Seu primeiro palpite é correta -. Atravessar o gráfico e alternativo

O algoritmo deve ser simples. Eu manteria duas filas de nós para visitar, um para cada cor. Pop nodos fora das filas alternadamente, marcar a sua cor, e empurrar quaisquer nós não visitados adjacentes na fila para a cor oposta. Termina quando o número de nós visitado + o comprimento de ambas as filas = número de nós no gráfico.

Answer 2

Traverse o gráfico e suplente, se não sucedido significa que o gráfico não é bipartido.

Answer 3

Se você tem certeza que o gráfico é biparte, então você pode cores apenas atribuir alternando-os para atravessar cada vértice, por entender que:

Um gráfico é bipartido se e só se for 2-ilusório.

Answer 4

De Wikipedia ( http://en.wikipedia.org/wiki/Bipartite_graph )

Se um gráfico bipartido é ligado, a sua bipartição pode ser definido pela paridade das distâncias a partir de qualquer arbitrariamente escolhido vértice v: um subconjunto consiste nos vértices a uma distância ainda a v e o outro subconjunto consiste nos vértices a uma distância estranho a v.

Assim, pode-se eficientemente teste se um gráfico é bipartido, utilizando esta técnica de paridade para vértices atribuir aos dois subconjuntos U e V, separadamente, dentro de cada componente ligado do gráfico, e, em seguida, analisar cada uma das arestas para verificar que tem pontos de extremidade atribuído a diferentes subconjuntos.

Answer 5

Eu implementei na minha Gráfico do desenho da ferramenta , você pode ver o meu código em JavaScript.

Eu só marcou primeiro vértice como partity esquerda, em seguida, de forma recursiva marcou de vizinhos como partity direita, de forma recursiva marcar seus vizinhos como partity esquerda ... Se você encontrar nó corretamente marcada, parada recursão deste ramo. Se você encontrar nó uncorrectly marcada, gráfico não é bipartido.

Talvez isso pode ser feito mais simples, mas durante os últimos meses eu tive algum duro Prolog - Haskell codificação dias, talvez tivesse afetado meu cérebro e agora vejo recursão em tudo :-D

Answer 6

Apenas no caso de qualquer um curioso, aqui está o código que eu vim com:

def dfs(root, colorings):
    to_visit1 = deque()
    to_visit2 = deque()
    to_visit1.append(root)
    while len(to_visit1) != 0 or len(to_visit2) != 0:
        dfs_color(to_visit1, to_visit2, True, colorings)
        dfs_color(to_visit2, to_visit1, False, colorings)

def dfs_color(queue, opposite_queue, color, colorings):
    while len(queue) != 0:
    v = queue.pop()
    if v in adjacency_list:
        colorings[v] = color
        neighbors = adjacency_list[v]
        del adjacency_list[v]
        for neighbor in neighbors:
        opposite_queue.append(neighbor)

Na verdade, este não é o meu melhor código. Estou usando True / False como a cor, porque quando eu usei recursão, que tornou fácil apenas dizer not color. Claro, eu tive que mudar isso porque eu estraguei a minha stack em gráficos maiores. Também para dar crédito onde devido, este código é baseado no código wikipedia para DFS .

Embora, como já foi referido, penso que este pode ser apenas um BFS disfarçados.