Conforme percebido pelos usuários no MathExchange, meu problema se trata na detecção de um grafo de intervalo. Particularmente não consegui entender os algoritmos disponíveis na internet sobre o assunto. Então? Inventei minha prova.
Um grafo de intervalo é um grafo em que todo ponto pode ser representado como um segmento/intervalo contíguo na reta real e, obrigatoriamente, caso haja interseção entre dois intervalos, no grafo haverá uma aresta ligando os dois vértices.
Doravante, em todo momento que for mencionado "intervalo", sem delimitar sobre sua continuidade ou não, ele será subentendido como um "intervalo contíguo"
Todo conjunto de intervalos é possível representar através de um grafo (que, por sua vez, passa a ser chamado de "grafo de intervalo"), porém a recíproca não é verdadeira. Existem grafos que não podem ser representados através de um conjunto de intervalos. O exemplo já foi até mesmo fornecido:
Esse problema de reconhecimento é pelo menos NP. Talvez seja ainda mais específico, como P, mas ainda não tenho a prova.
Antes de fornecer a solução, vou apresentar alguns resultados interessantes.
Um grafo de intervalo representa infinitos intervalos
Pegue um grafo de intervalo G qualquer. Como ele é um grafo de intervalo, então existe um intervalo I qualquer que é representado por G. I é composto por N intervalos no seguinte formato (os intervalos podem ser abertos ou fechados, mas isso não influencia em nada a conclusão):
(c_1, f_1)
(c_2, f_2)
...
(c_N, f_N)
Podemos deslocar todos os intervalos uma posição para a direita. Como deslocamos um intervalo? Somando nos valores representativos de seus extremos a quantidade desejada para o deslocamento, óbvio. Então, podemos deslocar todos os intervalos uma posição para a direita e obteremos:
(c_1 + 1, f_1 + 1)
(c_2 + 1, f_2 + 1)
...
(c_N + 1, f_N + 1)
Por essa definição, temos que a quantidade de vértices é idêntica
Agora, sejam i
e j
dois intervalos que continham interseção. Isso significa que há uma aresta entre os vértices i
e j
. Após o deslocamento, como não alteramos o grafo mas sim o intervalo, para o grafo continuar representando os intervalos deslocados, deve existir interseção entre (c_i + 1, f_i + 1)
e (c_j + 1, f_j + 1)
.
Seja x
um ponto da interseção entre (c_i, f_i)
e (c_j, f_j)
. Então isso significa que temos as seguintes 4 inequações como verdade (escritas de forma compactada):
c_i, c_j <= x <= f_i, f_j
Se somarmos 1 em todos os termos, as inequações continuam verdadeiras:
c_i + 1, c_j + 1 <= x + 1 <= f_i + 1, f_j + 1
Então temos que x + 1
pertence à interseção de (c_i + 1, f_i + 1)
e (c_j + 1, f_j + 1)
.
Esse resultado garante que todas as arestas continuam existindo.
Agora, peguemos os intervalos k
e l
que não tenham interseção. Sem perder generalidade, podemos dizer que f_k < c_l
e que, portanto, não há elementos na interseção. Ao adicionar 1 dos dois lados, a inequação continua verdadeira e, portanto, não há interseção.
Esse resultado garante que não há aresta nova sendo criada.
Portanto, o grafo de intervalo formado a partir do deslocamento dos intervalos originais possui os mesmos vértices, nenhuma aresta a menos e nenhuma aresta a mais, logo é o mesmo grafo. Isso demonstra que um único grafo de intervalo representa uma classe infinita de conjuntos de intervalos.
Um único vértice é um grafo de intervalo válido
Pegue o intervalo (0, 1)
. Para representar ele, preciso de um vértice e nenhuma aresta.
Um grafo vazio é um grafo de intervalo
Tome um conjunto vazio de intervalos. Você não terá arestas nem vértices, portanto um grafo vazio é um grafo de intervalo válido, o grafo de intervalo trivial.
Adicionar um vértice sem arestas a um grafo de intervalo gera um grafo de intervalo válido
Pegue G um grafo de intervalo. Pegue um de seus possíveis intervalos que ele representa, qualquer um. Então, é possível dizer que ele tem um ponto mais a direita. Seja esse ponto MAX
. Adicione o intervalo (MAX+1, MAX+2)
. Não há intervalo com nenhum intervalo anterior, portanto não há arestas, e consiste de um grafo de intervalo válido.
Todo grafo de intervalo com n+1
vértices só pode ser formado através da operação de acresção de vértices a um outro grafo de intervalo com n
vértices
A operação de acresção de um vértice consiste em adicionar esse vértice e, também, possivelmente arestas que tem esse vértice como terminal. Isso significa que no grafo A--B--C
, ao adicionar D
, podemos adicionar as arestas A--D
, B--D
, C--D
, porém não podemos adicionar A--C
.
A demonstração é meio trivial: adicionar um intervalo ao conjunto trará (possivelmente) interseções desse intervalo novo com os intervalos antigos, porém não fará com que intervalos antigos passem a se interseccionar entre si. Isso significa que, ao adicionar o intervalo D
, não será criada a interseção A--C
, descrita no parágrafo anterior.
O grafo de 1 vértice é gerado a partir do grafo trivial.
Todo clique é um grafo de intervalo
Um clique é possível de ser feito através de operações de acresção. Peguemos o menor clique com arestas: A--B
. Um conjunto que de intervalos que representa esse grafo é:
(c, f)
(c, f)
Sim, isso mesmo, o primeiro intervalo (c, f)
representa A
e o segundo intervalo (c, f)
representa B
. Podemos adicionar quantas vezes quisermos esse mesmo intervalo para vértices distintos, então todos os vértices novos precisam estar ligados entre si e, também, ligados com todos os antigos também.
Toda linha aberta é um grafo de intervalo
Pegue um vértice do grafo tal que ele só tenha um único vizinho. Associe a ele o seguinte intervalo fechado:
[c, c + 1]
Pegue o seu ponto vizinho. Associe a ele o seguinte intervalo fechado:
[c+1, c+2]
O seu outro vizinho terá o intervalo fechado [c+2, c+3]
e assim por diante, de tal modo que, se a distância entre o vértice X
e o vértice inicial é n
, então o intervalo que X
representa é o seguinte intervalo fechado:
[c+n, c+n+1]
Isso garante que cada intervalo só tenha interseção com o seu vizinho logo menor e com o vizinho logo maior. Portanto, eu consegui um conjunto de intervalos a partir de um grafo de linha (aberto) qualquer, então todo grafo de linha (aberto) é um grafo de intervalo.
Toda estrela é um grafo de intervalo
Pegue uma estrela formado por 1 centro e n
satélites. Para o centro, coloque o intervalo fechado no começo e aberto no fim [0, n)
.
Ordene de maneira arbitrária os n
satélites de 0
até n-1
. Ao satélite de índice i
atribua o intervalo fechado no começo e aberto no fim [i, i+1)
. Isso garante que todo satélite tenha interseção com o vértice central pois seu intervalo está contido integralmente dentro do intervalo do vértice central. E também não há interseção alguma com outro vértice, portanto constituindo um grafo de estrela.
Qualquer subgrafo de acresção de um grafo de intervalo é, também, um grafo de intervalo
Um subgrafo de acresção S de um grafo G é um grafo composto por um subconjunto dos vértices de G e todas as arestas que ligam esses vértices e que pertençam a G.
Pegue um subconjunto de intervalos do conjunto usado para gerar o grafo cheio. Então, se os intervalos A
e B
selecionados no subconjunto tinham aresta no grafo completo, então eles terão no subgrafo. Caso não tivessem, continuarão sem ter. Então qualquer subgrafo de acresção selecionado será um grafo de intervalo válido.
Note que, a partir de um subgrafo de acresção, é possível gerar o grafo novamente.
É possível gerar um grafo que não é de intervalo a partir de um grafo de intervalo através da operação de acresção
Tome o grafo B--A--C
. Como é uma linha aberta, então é um grafo de intervalo. Adicionemos D
como vértice e, também, as arestas C--D
e B--D
. Isso gerará o seguinte grafo, que é conhecidamente um grafo que não é de intervalo:
Todo grafo de acresção gerado a partir de um grafo que não é de intervalo também não será de intervalo
Pegue a propriedade qualquer subgrafo de acresção de um grafo de intervalo é, também, um grafo de intervalo
. Se eu gerar um grafo após uma operação de acresção e esse grafo novo for de intervalo, isso implica que o grafo anterior é um subgrafo de acresção, e portanto também deveria ser um grafo de intervalo.
Isso implica que todo e qualquer grafo de acresção gerado a partir de um grafo que não é de intervalo também não será de intervalo.
Todo ciclo com 4 ou mais vértices não é um grafo de intervalo
Vamos provar para um ciclo de tamanho n + 4
.
Pegue uma linha aberta de tamanho n + 3
. Isso significa que ela será da forma A -- B -- (...n vértices...) -- W
. Isso significa que não há valores na interseção entre A
e W
. Podemos convencionar que o fim de A
é menor que o começo de W
sem perder generalidade.
Só o formato da linha, então, implica que c_A <= c_B <= f_A
, que f_B > f_A
e que f_B <= c_Z
.
Adicionemos o vértice Z
e apenas as arestas Z--A
e Z--W
(portanto, uma operação de acresção). Se o novo grafo for um grafo de intervalo, isso implica que há valores na interseção A--Z
e na interseção Z--W
.
Como f_A < c_W
, um possível valor para c_Z = f_a - ε1
, para f_A - c_a > ε1 >= 0
com ε1
muito pequeno. Então isso significa que f_Z = c_W + ε2
, para f_Z - c_z > ε2 >= 0
com ε2
muito pequeno. Um intervalo com esses valores, entretanto, implica que f_B
esteja contido dentro dele, portanto deveria ter uma aresta Z--B
para ser um grafo de intervalo. Como não há essa arestas, então essa acresção gera um grafo que não é de intervalo.
Um ciclo de tamanho 3 é um grafo de intervalo válido
Podemos fazer essa demonstração de 2 maneiras:
- um ciclo com 3 vértices é um clique
- pegue os intervalos
[0,3]
, [1,4]
, [2,5]
e monte o grafo de intervalo; você obterá um ciclo.
Existem grafos acíclicos que não são de intervalo
Um grafo não-direcionado acíclico conexo é uma árvore. Considere como sendo um tronco de um grafo acíclico como sendo o maior caminho entre a raiz e uma folha. Se existir um vértice cuja distância a todos os vértices do tronco seja maior do que 2, então o grafo não é de intervalo.
Sem perder generalidade, assuma que c_M1 <= c_M2 <= c_M3
. Note que M2
não tem aresta nem com M1
nem com M3
. Isso significa que, para ser um intervalo válido, o intervalo que C
representa precisa:
- conter totalmente o intervalo de
M2
- ter interseção com
M1
logo no começo do intervalo
- ter interseção com
M3
logo no final do intervalo
Como M2
está contido em C
e E2
tem interseção com M2
, então E2
deveria também ter interseção com C
. Logo, esse grafo não é um grafo de intervalo.
Note que isso não quer dizer que o seguinte grafo não seja um grafo de intervalo:
Isso de deve ao fato de que o tronco é E1--M1--C--M2--E2
, não E1--M1--C--M3
. Então a maior distância entre um vértice e o seu tronco é 1 (M3--C
).
Com esse resultado, podemos extrapolar para que, a partir de um grafo de intervalo conexo qualquer, se forem acoplados a ele três radicais distintos no formato E--M--
disjuntos entre si, o grafo resultante não é de intervalo.
Tá, mas e o que faço com isso?
Até agora, conseguimos encontrar duas classes de grafos que não são de intervalo:
- ciclos (sem cordas) de comprimento maior do que ou igual a 4
- 3 radicais
E--M--
disjuntos entre si conectados no mesmo grafo conexo
Infelizmente, não consegui demonstrar que essas são as única classes de grafos que não são disjuntos (tem outros, como trocando M
ou E
por subgrafos conexos, porém sem ligar nenhum vértice de E
com o subgrafo do outro lado de M
). Também obtemos um resultado muito interessante:
- todo grafo de acresção montado a partir de um grafo que não é de intervalo, também não é um grafo de intervalo
Esse último resultado indica que basta acharmos um subgrafo de acresção que é um ciclo sem cordas de tamanho maior do que ou igual a 4 para identificar que não é um grafo de intervalo. Também indica que qualquer coisa que lembra vagamente isso como
(com C
um subgrafo conexo) também não é um subgrafo de intervalo.
Em cima de tudo isso que foi posto, tenho algumas sugestões de como fazer essa validação:
Algoritmo não-determinístico
Uma primeira solução para demonstrar que o problema se encontra em NP.
Como um bom algoritmo em NP, é necessário um certificado para a entrada, então em cima desse certificado e da entrada, é possível obter a resposta correta.
O certificado consiste de, para um grafo com n
vértices (todos eles rotulados), um conjunto de n
intervalos também rotulados, de modo que o rótulo de um vértice coincida com o rótulo de um dos intervalos fornecidos.
A validação então se torna apenas verificar:
- se todos os rótulos são válidos
- se as arestas são interseções (isso é feito em
O(e)
, sendo e
a quantidade de arestas no grafo)
- se existem interseções que não são arestas (isso é feito em
O(n^2)
)
Por exemplo, para
Um certificado válido seria:
E1: [0, 5]
M1: [5, 10]
C: [10. 20]
M3: [13, 14]
M2: [20, 25]
E2: [25, 30]
As validações:
tem 6 intervalos e 6 vértices, todos os rótulos de intervalos são também rótulos de vértices
checado, positivo
cada aresta tem uma interseção
E1--M1: {5}
M1--C: {10}
C--M3: [13, 14]
C--M2: {20}
E2--M2: {25}
não tem outra interseção possível, portanto não está "faltando arestas" no grafo para representar esse grafo em específico.
Algoritmo determinístico
Esse algoritmo é altamente influenciado pelo certificado acima.
Primeiro, montamos uma "permutação" dos vértices. Como assim? Ordenamos os vértices em uma lista, simples assim. Se eu tenho n
vértices, então eu tenho n!
permutações possíveis. Para o grafo acima existem 6! = 720 permutações possíveis; algumas delas são:
C,M1,M2,M3,E1,E2
M1,E1,C,M2,E3,M3
E1,M1,C,M3,M2,E2
Nessa permutação, fazemos a suposição de que elas estão ordenadas de tal modo que o elemento na posição i+1
tem um intervalo cujo menor elemento é maior do que o menor elemento do intervalo do elemento da posição i
. Por exemplo, a terceira permutação acima poderia representar os seguintes intervalos:
0 1 2 3 4 5 6 7
E1: ****
M1: ******
C: ********
M3: **
M2: *****
E2: ****
Numericamente seria:
E1: [0, 1]
M1: [1, 2.7]
C: [2.7, 5]
M3: [3.7, 4]
M2: [4.7, 6.3]
E2: [6.3, 7.3]
Para ser um grafo de intervalo, deve haver pelo menos uma permutação dessas que, com essa interpretação do número inicial ser sempre crescente de acordo com a posição na lista, todo vértice e seus vizinhos compartilham a seguinte propriedade (considerando A
vindo antes de Z
na permutação, sem perder generalidade):
- se existe a aresta
A--Z
, então isso pode ser representado pela substring na permutação AZ
- se existe a aresta
A--Z
, e na permutação tiver alguns outros vértices no meio do caminho, então esses vértices são todos vizinhos de A
; por exemplo, ABCZ
implica que A
é vizinho de B
e de C
também
- caso não seja possível satisfazer uma das duas condições acima, então essa permutação é inválida
Tomemos as três permutações que usamos no começo para analisar.
A primeira, C,M1,M2,M3,E1,E2
. C
realmente é vizinho de M1,M2,M3
. Então a vizinhança de C
está válida. Porém M1
é vizinho de E1
mas não de M2
, nem de M3
, portanto essa permutação é inválida.
A segunda permutação, M1,E1,C,M2,E3,M3
. M1
é vizinho de E1,C
. E1
não tem mais nenhum outro vizinho, então está tudo bem com ele. C
tem como vizinhos restantes M2
e M3
, porém não tem E3
. Portanto permutação inválida.
Vamos pegar a terceira permutação: E1,M1,C,M3,M2,E2
. E1
tem como vizinho apenas M1
, então está tudo bem até aqui. M1
tem como outro vizinho C
. C
, por sua vez, tem como vizinho M2
e M3
, e eles aparecem na ordem M3,M2
. M3
não tem mais vizinhos restantes, então tudo bem até aqui. M2
precisa ainda do vizinho E2
, que vem logo em seguida. E2
não tem novos vizinhos. Então a permutação é válida e é possível escrever um conjunto de intervalos para essa permutação.
Peguemos agora um caso em que não é grafo de intervalo:
As possíveis permutações são:
ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
BDAC
BDCA
CABD
CADB
CBAD
CBDA
CDAB
CDBA
DABC
DACB
DBAC
DBCA
DCAB
DCBA
Todas elas devem ser inválidas. Vamos começar eliminando aquelas que começam com as seguintes sequências:
Porque não existem as arestas A--D
nem B--C
e todos esses vértices possuem arestas, portanto não a segunda letra da sequência deveria ser um de seus vizinhos. Assim, restou-nos:
ABCD
ABDC
ACBD
ACDB
BACD
BADC
BDAC
BDCA
CABD
CADB
CDAB
CDBA
DBAC
DBCA
DCAB
DCBA
Ainda são 16 sequências para serem eliminadas. Podemos eliminar todas que tenham a sequência BCD
, pois não existe B--C
porém existe B--D
. Semelhante para a sequência contrária, DCB
, e também para ADB
, ADC
, BCA
e seus inversos BDA
, CDA
e ACB
. Depois de filtrar:
ABDC
ACDB
BACD
BDCA
CABD
CDBA
DBAC
DCAB
Ainda são 8. Note que, agora, para todos esses restantes, o primeiro elemento possui ligação com o segundo elemento (como em A--B
), não possuem com o terceiro mas possuem com o último. Portanto, nenhuma dessas permutações é válida.
Esse algoritmo tem tempo médio esperado para funionar de O(n! * e)
, já que são n!
permutações e, para cada permutação, devo verificar aresta a aresta se a permutação é válida.