O zero é permitido como o peso de uma aresta, em um gráfico ponderado?

Estou tentando escrever um script que gera gráficos aleatórios e preciso saber se uma aresta em um gráfico ponderado pode ter o valor 0.

na verdade, faz sentido que 0 possa ser usado como um peso de ponta, mas tenho trabalhado com gráficos nos últimos dias e nunca vi um exemplo disso.

Permitido por quem ? Não existe uma Administração Central de Gráficos que decida o que você pode ou não fazer. Você pode definir objetos da maneira que for mais conveniente para você, desde que seja claro sobre qual é a definição. Se arestas com peso zero forem úteis para você, use-as; apenas verifique se seus leitores sabem o que você está fazendo.

O motivo pelo qual você normalmente não vê arestas com peso zero é que, na maioria dos contextos, uma aresta com peso zero é exatamente equivalente à ausência de uma aresta. Por exemplo, se seu gráfico representar países e a quantidade de transações realizadas entre eles, uma margem de peso zero significaria nenhuma negociação, o que é o mesmo que não ter nenhuma margem. Se o seu gráfico representar distâncias, uma borda com peso zero corresponderia a dois lugares à distância zero um do outro, o que significaria que eles realmente seriam o mesmo local, portanto, ambos deveriam ser representados pelo mesmo vértice. No entanto, em outros contextos, bordas com peso zero podem fazer sentido. Por exemplo, se o seu gráfico representa uma rede de estradas e os pesos das margens representam a quantidade de tráfego, há uma grande diferença entre uma estrada que ninguém usa (margem com peso zero) e nenhuma estrada (sem margem).

Depende do contexto. Em geral, sim, bordas com peso zero e até negativo podem ser permitidas. Em alguns casos específicos, pode ser necessário que os pesos das arestas não sejam negativos ou estritamente positivos (por exemplo, o algoritmo de Dijkstra exige que os pesos sejam não negativos).

Como as outras respostas observam, você é perfeitamente livre para considerar (ou excluir da consideração) gráficos ponderados com arestas de peso zero.

Dito isto, na minha experiência, a convenção usual na maioria das aplicações de gráficos ponderados é não fazer distinção entre uma borda com peso zero e a ausência de uma borda. Uma razão para isso é que, normalmente, os gráficos ponderados aparecem como generalizações de multigráficos , que por sua vez são generalizações de gráficos simples.

Especificamente, um multigráfico é um gráfico que (diferente de um gráfico simples ) permite várias arestas entre o mesmo par de nós. Considerando que, em um gráfico simples, qualquer par de nós sempre é conectado por 0 ou 1 arestas, um par de nós em um multigráfico pode ser conectado por 0, 1, 2, 3 ou mais (mas sempre um número inteiro não negativo de ) arestas.

A generalização de um multigráfico para permitir um número fracionário de arestas entre um par de nós leva naturalmente a considerar gráficos ponderados, e muitos algoritmos que funcionam em multigráficos arbitrários também podem funcionar nesses gráficos ponderados. Mas para tais algoritmos, o "peso" de uma aresta realmente denota sua multiplicidade . Assim, dada essa interpretação, não pode haver distinção significativa entre "sem arestas" e "0 arestas" entre um par de nós: ambos significam exatamente a mesma coisa.

Obviamente, um "gráfico ponderado" por definição é realmente apenas um gráfico com um número associado a cada aresta, e é perfeitamente possível interpretar o peso como algo diferente de multiplicidade, caso em que uma distinção entre nenhuma aresta e um peso zero de fato pode ser significativo. Mas é improvável que tentar aplicar algoritmos multigráficos padrão a esses "gráficos estranhamente ponderados" produza resultados que fariam sentido em termos da interpretação alternativa (não-multiplicidade) dos pesos das arestas.

Pense em um gráfico do sistema rodoviário em Cambridge, no Reino Unido, as notas são compartilhadas entre ciclistas e motoristas, assim como a maioria das arestas. Fazer isso diminui bastante o custo de manutenção dos dados.

Agora, se definirmos o peso da borda como sendo o tempo de viagem em segundos, cada borda terá dois pesos, um para os carros e para as bicicletas. Alguns pesos serão infinitos, pois os carros não são permitidos em ciclovias.

Agora considere dois cruzamentos muito próximos um do outro, tão próximos que só são serrilhados por alguns postes que impedem os motoristas. (Por exemplo, uma encruzilhada, onde os carros só podem virar à esquerda, mas os ciclistas podem seguir em qualquer direção.) Em seguida, obtemos algumas arestas com peso infinito dos motoristas e 0 peso para os ciclistas.

(Claramente, o gráfico poderia ser pré-processado para criar um gráfico mais simples para o roteamento de ciclistas, antes de elaborar os melhores roteadores.)

Parece que você está usando o peso para tentar representar dois aspectos distintos do gráfico. A primeira é se o gráfico realmente possui uma borda representável (desenhada) e a segunda é o peso real.

Como você notou, você entra em uma situação confusa se tiver usado 'diferente de zero' como um indicador de que uma aresta está presente (e precisaria ser desenhada ou listada), enquanto, ao mesmo tempo, agora encontrou uma situação onde o peso zero é classificado como válido.

Essencialmente, você precisará de outra maneira de representar a presença da borda (supondo que você realmente precise disso e não possa simplesmente criar uma matriz N ^ 2 de pesos, mas então cairá na armadilha de precisar decidir o que fazer com o loop bordas traseiras ...)