Meu gráfico é gracioso?

8

Um gráfico gracioso é um tipo de gráfico simples . Gráficos graciosos são especiais porque existe uma maneira de rotular todos os seus nós com números inteiros positivos, de modo que quando as arestas também são rotuladas com as diferenças dos nós que conectam, não há duas arestas com o mesmo rótulo e todos os rótulos até o número de arestas é usado.

Exemplo elaborado

Aqui está um gráfico simples que suspeitamos ser um gráfico gracioso

Gráfico Simples

Vamos tentar a seguinte rotulagem:

Marcado

Observe que temos permissão para pular números inteiros na rotulagem de nós. Agora, rotulamos cada extremidade com a diferença positiva entre os nós que conectam. Para maior visibilidade, eu os rotulei em vermelho.

Duplamente rotulado

Cada aresta tem um número único e nenhum número entre 1 e 7 (o número de arestas que temos) é deixado de fora. Assim, nosso gráfico é gracioso.

Tarefa

Dado um gráfico, através de qualquer método razoável de entrada, produza um valor verdadeiro, se for gracioso e, caso contrário, um valor falso.

Isso é então o objetivo é minimizar a contagem de bytes.

Casos de teste

Aqui os gráficos são representados como uma matriz de arestas:

3 nodes:

[(0,1),(0,2),(1,2)]

True

Labeling:

Node 0 -> 0
Node 1 -> 2
Node 2 -> 3

5 nodes:

[(0,1),(0,4),(1,2),(2,3),(3,4)]

False

5 nodes:

[(0,1),(1,2),(2,3),(3,4)]

True

Labeling:

Node 0 -> 0
Node 1 -> 1
Node 2 -> 3
Node 3 -> 6
Node 4 -> 10

9 nodes

[(0,1),(1,2),(1,7),(1,8),(2,3),(2,6),(3,4),(4,5)]

True

Labeling:

Node 0 -> 0
Node 1 -> 1
Node 2 -> 3
Node 3 -> 6
Node 4 -> 10
Node 5 -> 15
Node 6 -> 11
Node 7 -> 7
Node 8 -> 8

5 nodes

[(0,1),(0,2),(1,2),(1,3),(1,4),(3,4)]

False
Caçador Ad Hoc Garf
fonte
Acho algoritmos para verificação da graciosidade são conhecidos apenas para certas classes de gráficos (por exemplo, árvores )
ngenisis
2
@ngenisis Certamente pode ser brutalmente forçado. Existem algoritmos mais eficientes para determinadas classes, mas você pode usar restrições nos tamanhos das arestas para criar uma diferença máxima de rótulo de nó.
Ad Hoc Garf Hunter
[(0,1),(1,2),(2,3),(3,4)]é provavelmente um caso notável.
Dennis
A menos que esteja faltando alguma coisa, os gráficos do formulário {(k-1,k) : 0 < k < n}exigem os rótulos mais altos de todos os gráficos com o mesmo número de nós.
Dennis
@ Dennis Oh sim. Certamente é verdade que eles deveriam exigir n(n+1)/2como seu rótulo mais alto. Eu adicionei seu caso de teste.
Ad Hoc Garf Hunter

Respostas:

6

Jelly , 12 bytes

FSŒ!ị@€ḅ-AċJ

Toma uma matriz de arestas como pares de nós indexados em 1.

Experimente online! (Horrendamente ineficiente. Não se preocupe com os casos de teste reais.)

Como funciona

FSŒ!ị@€ḅ-AċJ  Main link. Argument: A (array of pairs)

FS            Flatten and sum, yielding s. This is an upper bound for the labels
              a graceful labeling (if one exists) would require.
  Œ!          Take all permutations of [1, ..., s].
      €       For each permutation P:
    ị@          Replace each integer in A with the element of P at that index.
       ḅ-     Convert all pairs from base -1 to integer, mapping (a,b) to b-a.
         A    Take absolute values.
           J  Yield the indices of A, i.e., [1, ..., len(A)].
          ċ   Count the occurrences of [1, ..., len(A)] in the result to the left.
Dennis
fonte
2
ḅ-é um dos meus truques favoritos Jelly :-)
ETHproductions
4

Mathematica, 121 116 bytes

Editar: salvou 5 bytes graças a JungHwan Min e Martin Ender

Cases[Range[1+Tr[n=Range@Length[e=EdgeList@#]]]~Tuples~VertexCount@#,w_/;Sort[Abs[#-#2]&@@w[[List@@#]]&/@e]==n]!={}&

Explicação

insira a descrição da imagem aqui

Função pura que pega um Graphobjeto Mathematica com vértices {1, 2, ..., k}para algum número inteiro não negativo k. Na pior das hipóteses, precisaremos apenas de rótulos de vértices que variam de 1a 1 + (1 + 2 + ... EdgeCount@#). Como nos salva alguns bytes depois, deixaremos ea lista de arestas e na lista {1, 2, ..., EdgeCount@#}, de modo que os pesos dos vértices serão retirados Range[1+Tr[n=Range@Length[e=EdgeList@#]]]. Geramos uma lista de todos os Tuplescomprimentos VertexCount@#, depois escolhemos as Casesque fornecem rotulagem discreta e verificamos se o resultado está Unequalna lista vazia {}. A graciosidade da lista de pesos de vértices wé verificada Mapexecutando ping na função Abs[#-#2]&@@w[[List@@#]]&sobre a lista de arestas e,Sort incluindo o resultado e verificando se o resultado éEqualpara n. Aqui está um detalhamento dessa função:

               List@@#     Replace the Head of the edge with List; i.e., UndirectedEdge[a,b] becomes {a,b}.
            w[[       ]]&  Select the corresponding vertex weights from the list w.
          @@               Replace the Head of that expression (List) with the function
Abs[#-#2]&                   which returns the absolute difference between its first two arguments.
                           This effectively passes the vertex weights into the absolute difference function. 
ngenisis
fonte
1
salve um byte mexendo com alguma precedência: VertexCount[#]->VertexCount@#
JungHwan Min 17/02
1
Aliás, o Trtruque para Lengthnão salva mais bytes se você precisar adicionar parênteses. Length[e=EdgeList@#]tem o mesmo comprimento. Mas é mais curto evitar isso completamente e reescrever o número triangular lá como Tr@Range@EdgeCount@#(e depois substituir eno final por EdgeList@#. Segundo, o operador de função raramente salva bytes, nesse caso, acho que é mais curto usar em Casesvez de Selecte depois em w_/;vez de w.
Martin Ender