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
Vamos tentar a seguinte rotulagem:
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.
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 é código-golfe, 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
fonte
[(0,1),(1,2),(2,3),(3,4)]
é provavelmente um caso notável.{(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.n(n+1)/2
como seu rótulo mais alto. Eu adicionei seu caso de teste.Respostas:
Jelly , 12 bytes
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
fonte
ḅ-
é um dos meus truques favoritos Jelly :-)Mathematica,
121116 bytesEditar: salvou 5 bytes graças a JungHwan Min e Martin Ender
Explicação
Função pura que pega um
Graph
objeto Mathematica com vértices{1, 2, ..., k}
para algum número inteiro não negativok
. Na pior das hipóteses, precisaremos apenas de rótulos de vértices que variam de1
a1 + (1 + 2 + ... EdgeCount@#)
. Como nos salva alguns bytes depois, deixaremose
a lista de arestas en
a lista{1, 2, ..., EdgeCount@#}
, de modo que os pesos dos vértices serão retiradosRange[1+Tr[n=Range@Length[e=EdgeList@#]]]
. Geramos uma lista de todos osTuples
comprimentosVertexCount@#
, depois escolhemos asCases
que fornecem rotulagem discreta e verificamos se o resultado estáUnequal
na lista vazia{}
. A graciosidade da lista de pesos de vérticesw
é verificadaMap
executando ping na funçãoAbs[#-#2]&@@w[[List@@#]]&
sobre a lista de arestase
,Sort
incluindo o resultado e verificando se o resultado éEqual
paran
. Aqui está um detalhamento dessa função:fonte
VertexCount[#]
->VertexCount@#
Tr
truque paraLength
nã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á comoTr@Range@EdgeCount@#
(e depois substituire
no final porEdgeList@#
. Segundo, o operador de função raramente salva bytes, nesse caso, acho que é mais curto usar emCases
vez deSelect
e depois emw_/;
vez dew
.