Convertendo um dígrafo em um gráfico não direcionado de maneira reversível

10

Estou procurando um algoritmo para converter um dígrafo (gráfico direcionado) em um gráfico não direcionado de forma reversível, ou seja, o dígrafo deve ser reconstruído se recebermos o gráfico não direcionado. Entendo que isso custará o gráfico não direcionado ter mais vértices, mas não me importo.

Alguém sabe como fazer isso ou pode sugerir alguma referência? Desde já, obrigado.

Atualização: Em relação à resposta de AdrianN abaixo. Pode ser um bom ponto de partida, mas não acho que funcione na sua forma atual. Aqui está uma imagem do porque eu acho que não: insira a descrição da imagem aqui

Atualização após o comentário do DW: considero os vértices dos gráficos sem rótulo. Se uma solução envolve rotular os vértices (como o de AdrianN), deve fornecer o mesmo gráfico não-direcionado (isomórfico), não importa como a rotulagem seja feita. Minha definição de "isomórfica" para gráficos com vértices rotulados é que existe uma permutação da rotulagem que relaciona os dois gráficos, mas não tenho certeza da definição exata para gráficos não rotulados ...

algorithms graph-theory graphs Heterótico
fonte

11

Eu acho que essa pergunta é muito ampla. Quais são as suas restrições?

precisa saber é o seguinte

Eu realmente não consigo pensar em nenhuma restrição por enquanto. Eu acho que qualquer maneira de codificar as informações de um gráfico direcionado em um não direcionado seria suficiente, desde que seja reversível. Eu acho que o que eu tenho em mente é o tipo mais simples de gráficos não direcionados, então estou procurando uma solução que não use cores para os vértices ou as arestas.

Heterotic

Eu acho que você deve especificar na pergunta o que você quer dizer com "o mesmo gráfico". Você quer dizer que os vértices são rotulados ou que os vértices não são rotulados? Você quer dizer que

é o mesmo para ambos, ou que os dois gráficos são isomórficos? Parece que você quer dizer o último. Tem certeza de que isso é um requisito no seu aplicativo? Se você puder reter etiquetas, o problema ficará mais fácil e a resposta de AdrianN funcionará (porque a borda

não é a mesma que a borda

).

(V, E)

$(V,E)$

(3, 4)

$(3,4)$

(1^{'}, 2^{'})

$(1',2')$

DW

2

Por favor, incorporar as suas atualizações em questão. A qualquer momento, as postagens do SE devem ser lidas de cima para baixo sem se perguntar sobre o histórico; arquivado separadamente.

Raphael

6

Para cada aresta direcionada , adicione novos vértices e substitua pelas arestas , , , , , $e=(x,y)$ $v^e_1, \dots, v^e_5$ $e$ $xv^e_1$ $v^e_1v^e_2$ $v^e_1v^e_3$ $v^e_3v^e_4$ $v^e_4v^e_5$ . $v^e_3y$

Para decodificar, toda folha (vértice grau 1) cujo vizinho possui grau 2 deve ser para alguma aresta ; seu vizinho é e o outro vizinho de $v^e_5$ $e=(x,y)$ $v^e_4$ é . tem um vizinho único que possui o grau 3 e é adjacente a uma folha: o vizinho é e sua folha é (se $v^e_4$ $v^e_3$ $v^e_3$ $v^e_1$ $v^e_2$ $v^e_1$ tem dois vizinhos de folha, escolha um arbitrariamente para ser ). O outro vizinho da é e o outro vizinho da é . Restaure a aresta direcionada e exclua os vértices . $v^e_2$ $v^e_1$ $x$ $v^e_3$ $y$ $(x,y)$ $v^e_1, \dots, v^e_5$

David Richerby
fonte

7

A resposta de David Richerby (que foi aceita) é boa.

Eu segui as instruções dele em um exemplo simples de digrafo e espero que ajude alguém.

dígrafo a <-> b, c -> a, b -> c

(Eu teria postado isso como um comentário na resposta de David, mas não tenho os pontos de reputação necessários.)

William
fonte

11

A representação gráfica é uma grande melhoria em relação à resposta original. Obrigado por publicá-lo como resposta, não como comentário.

OrangeSherbet

11

Sempre me sinto sobrecarregado quando olho para uma explicação ou fórmula formal em um trabalho de matemática. Eu só tenho que superar essa ansiedade e olhar cada frase lentamente - olhando as coisas com as quais não estou familiarizado à medida que avança. Então, rabisco um exemplo como esse para ter certeza de que entendo. No final, eu sempre fico pasmo com a simplicidade de tudo isso, e meio que horrorizado com o esforço necessário para compreendê-lo. Parece que eu sou de um planeta diferente às vezes. Fico feliz que eu possa ajudá-lo a entender mais rápido. Depois de vê-lo, é fácil.

William

2

Para converter um gráfico direcionado em um gráfico não direcionado faça o seguinte: $D$ $G$

Numere os nós de $D$
Crie dois gráficos não direcionados , no mesmo vértice definido como $G'$ $G''$ $D$
Para cada aresta , em adicione a aresta a se , caso contrário, adicione a aresta a $u$ $v$ $D$ $G'$ $u<v$ $G''$
G é a união disjunta de e $G'$ $G''$

Ao fazer a união disjunta, é preciso ter cuidado para torná-la reversível.

Exemplo

adrianN
fonte

Esta é uma boa tentativa e está na linha que eu tinha em mente para obter uma resposta, mas não funciona porque o inverso não é único. Por exemplo, o gráfico O <-> OOO será convertido no gráfico OO OO OO OO, mas esse último também poderia ter vindo do gráfico direcionado O-> O O-> OOO, de modo que o processo não seja reversível.

Heterotic

Eu adicionei uma imagem para torná-la mais clara.

precisa saber é o seguinte

-1

E a função de identidade? Ou seja, todo dígrafo pode ser visto como um gráfico bipartido não direcionado com partições de tamanho igual e vice-versa.

muede
fonte

G = (V, E)

$G=(V,E)$

(V \times {0, 1}, {(⟨ u, 0 ⟩, ⟨ v, 1 ⟩) ∣ (u, v) \in E})

$(V\times\{0,1\}, \{(\langle u,0\rangle, \langle v,1\rangle)\mid (u,v)\in E\})$

G^{'}

$G'$

G

$G$

G

$G$

G^{'}

$G'$

-1

Aqui está uma facada nisso:

Substitua as informações de direção por vértices adicionais no gráfico não direcionado. Em outras palavras, use os vértices adicionais no gráfico não direcionado para "codificar" as informações de direção. Por exemplo, para cada vértice direcionado com pelo menos uma aresta, adicione um número de vértices não direcionados igual a 1 + o número de arestas "de entrada". Vértices com arestas zero permanecem inalterados.

Para executar a direção reversa, crie um vértice direcionado para cada vértice que tenha 0 ou mais de 1 aresta. (Vértices com exatamente uma aresta são os vértices de "codificação da direção"). Cada aresta que conecta outro vértice com várias arestas é uma conexão no gráfico direcionado. Agora é a parte complicada para a qual não posso explicar um algoritmo (mas acho que existe): você deve deduzir a direção das setas, considerando apenas o número de setas recebidas para cada vértice.

Eu acho que a parte complicada é como jogar um caça-minas :-) Descobrir onde as bombas (arestas de entrada) recebem o número de bombas adjacentes para cada quadrado (vértice).

Aaron
fonte

x

$x$

x

$x$

Por "vértice direcionado", quero dizer um vértice no gráfico direcionado (em oposição ao gráfico não direcionado equivalente). Você pode distinguir arestas "reais" de arestas de "codificação em graus" porque apenas os vértices "codificação em graus" têm uma única aresta. Essa foi a razão do "1 +" na minha descrição. Vou acreditar na sua "parte complicada". Eu não sei o que é exatamente equivalente a caça-minas, mas posso acreditar que eu talvez única chutou o balde na estrada :-)

Aaron

Além disso, não entendi muito bem sua solução quando a li pela primeira vez, mas vejo como ela funciona agora. Inteligente!

Aaron

x

$x$

x

$x$

(x, y)

$(x,y)$

(x_{0}, x), (x, y), (y, y_{0})

$(x_0,x), (x,y), (y,y_0)$

(y, y_{1})

$(y,y_1)$

x

$x$

y

$y$

(x, y)

$(x,y)$

Convertendo um dígrafo em um gráfico não direcionado de maneira reversível

Respostas: