10

Recentemente estava respondendo uma questão (Escalonamento de máquinas - Teoria dos Grafos), porém ficou um problema em aberto que não consegui resolver:

  • Dado um grafo qualquer, identificar se ele é válido para o problema de alocação de operador por máquina

O problema original é mais ou menos assim:

São dadas n máquinas, m_1, m_2, ... m_n que precisam estar ligadas nos intervalos de tempos I_1, I_2, ... I_n respectivamente (portanto o intervalo I_k se refere à máquina m_k). Para uma máquina ficar ligada, é necessário que um operador fique com ela. Um operador só pode operar uma máquina por vez; portanto, se I_i ∩ I_j != ∅, então para operar m_i e m_j são necessários dois operadores diferentes. Qual o número mínimo de operadores suficiente para operar essas máquinas? Mostre o grafo que modele esse problema

Na minha resposta a essa pergunta, modelei esse problema como um problema de coloração de grafos. Excertos significativos da modelagem:

Um problema clássico de otimização para o menor possível é o de coloração de grafos. No caso, para usar esse esquema, precisamos mapear cada conceito de coloração de grafos no nosso problema atual.

  • Vértices:
    Cada vértice é uma máquina. O vértice i representa a máquina i
  • Arestas:
    Uma aresta ij significa que as máquinas i e j estão ligadas ao mesmo tempo. Ou então, mais formalmente, a interseção I_i com I_j é não vazia
  • Cores:
    Cada cor é um operador. Como um operador só pode operar uma máquina por vez, dois vértices vizinhos não podem ter a mesma cor.

Consegui inclusive descrever um algoritmo para geração "aleatória" de grafos válidos, mais ou menos assim:

Para n máquinas quaisquer, gere n pares de números (A_i,B_i) tal que A_i < B_i. Esses são os intervalos de tempo do funcionamento das máquinas. Se por acaso houver interseção não vazia entre (A_i,B_i) e (A_j,B_j), então no grafo deve existir a aresta ij. Detectadas todas as interseções, você terá um grafo válido de n vértices para esse problema de alocação de operários por máquina

Também consegui identificar e provar que o seguinte grafo é inválido para esse problema (demonstração omitida aqui):

1 --- 2
 \   /
  \ /
   x
  / \
 /   \
3 --- 4

Porém, não consigo um algoritmo geral para identificar se um dado grafo satisfaz ou não o caso descrito no problema.


Conversando com o pessoal da minha faculdade, consegui uma outra interpretação ao meu problema é:

Dados n intervalos contínuos nos números reais, nenhum deles com valores conhecidos, e dados a existência de interseção não vazia entre esses intervalos, determinar se existem números reais para esses intervalos que satisfazem essas interseções

No caso, os intervalos representariam os meus vértices e as interseções não vazias representariam as arestas entre esses vértices.

Eu fiz exatamente com essa questão de dar as interseções determinar se é válido ou não no Mathematics exchange

1 Resposta 1

4

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:

Exemplo de grafo que não é de intervalo

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:

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:

  1. um ciclo com 3 vértices é um clique
  2. 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.

um grafo acíclico que 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:

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

3 radicais E--M-- adicionados a um centro

(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:

  1. se todos os rótulos são válidos
  2. se as arestas são interseções (isso é feito em O(e), sendo e a quantidade de arestas no grafo)
  3. se existem interseções que não são arestas (isso é feito em O(n^2))

Por exemplo, para

3

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:

  1. tem 6 intervalos e 6 vértices, todos os rótulos de intervalos são também rótulos de vértices
    checado, positivo

  2. cada aresta tem uma interseção

     E1--M1: {5}
     M1--C:  {10}
     C--M3:  [13, 14]
     C--M2:  {20}
     E2--M2: {25}
    
  3. 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:

ciclo com 4 vértices não é graof 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:

  • AD
  • DA
  • BC
  • CB

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.

3
  • 1
    Só hj consegui ler :)
    – Maniero
    Commented 4/02/2018 às 0:44
  • @Maniero leitura leve para um sábado de noite? ;) Commented 4/02/2018 às 0:45
  • 1
    Quem sabe você consiga pensar em algo mais eficiente do que um tempo superfatorial... e eu ainda nem consegui reduzir isso a isomorfismo de grafo (nem que ajude muita coisa, pois isomorfismo é NPI, ainda não foi comprovado nem NPC nem P) Commented 4/02/2018 às 0:47

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .