Grafo implícito

Origem: Wikipédia, a enciclopédia livre.

No estudo de algoritmos de grafos, uma representação por grafo implícito (ou mais simplesmente grafo Implícito) é um grafo em que os vertices ou arestas não são representados como objetos explícitos na memória de um computador, mas sim, determinados algoritmicamente a partir de alguma entrada.

Representação de vizinhança[editar | editar código-fonte]

A noção de grafo implícito é comum em vários algoritmos de busca que são descritos em termo de grafos. Nesse contexto, um grafo implícito pode ser definido como um conjunto de regras para definir toda a vizinhança de um determinado vértice.[1] Este tipo de representação por grafo implícito é análoga a uma lista de adjacência, na medida em que fornece acesso fácil para os vizinhos de cada vértice. Por exemplo, na busca de uma solução para um enigma, como o Rubik's Cube, pode-se definir um grafo implícito no qual cada vértice representa um dos estados possíveis do cubo, e cada aresta representa um movimento de um estado para outro. É simples gerar os vizinhos de qualquer vértice, tentando todos os movimentos possíveis do quebra-cabeça e determinando os estados alcançados por cada um desses movimentos; no entanto, uma representação implícita é necessária, pois o espaço de estados do Cubo de Rubik é demasiado grande para permitir que um algoritmo consiga listar todos os seus estados.[2]Em teoria da complexidade computacional, várias classes de complexidade foram definidas em conexão com grafos implícitos, definidos como citado acima, por uma regra ou algoritmo para listar os vizinhos de um vértice. Por exemplo, PPA é a classe de problemas em que tem-se como entrada um grafo implícito não direcionado (no qual os vértices são n - cadeias binárias bits, com um algoritmo de tempo polinomial para listar os vizinhos de qualquer vértice) e um vértice de grau ímpar no grafo, e deve-se encontrar um segundo vértice de grau ímpar. Pelo handshaking lema, tal vertice existe; Encontrar um é um problema NP, mas os problemas que podem ser definidos desta forma podem não ser necessariamente NP-completos, pois não se sabe se PPA = NP. PPAD é uma classe análoga definido em grafos orientados implícitos que tem atraído a atenção na teoria dos jogos porque contém o problema de computar um equilíbrio de Nash.[3] O problema de testar atingibilidade (teoria dos grafos) de um vértice para outro num grafo implícito pode também ser usado para caracterizar classes de complexidade não-deterministicamente limitadas por espaço, incluindo a NL (a classe de problemas que podem ser caracterizados por acessibilidade em grafos implícitos cujos vértices são O(log n)-bit bitstrings), SL (a classe análoga para grafos não-direcionados), e PSPACE (a classe dos problemas que podem ser caracterizados em grafos implícitos com uso de bitstrings de comprimento polinomial). Neste contexto de complexidade teórica, os vértices de um grafo implícito podem representar os estados de uma máquina de Turing não determinística, e as arestas podem representar possíveis transições de estado, mas os grafos implícitos também podem ser usados para representar muitos outros tipos de estruturas combinatórias.[4] PLS, outra classe de complexidade, capta a complexidade de encontrar ótimos locais em um grafo implícito.[5]

Modelos de grafo implícitos também têm sido utilizados como uma forma de relativização, a fim de provar que as separações entre as classes de complexidade são mais fortes do que as separações conhecidas para modelos não-relativizados. Por exemplo, Childs et al utilizou representações de vizinhança usados por grafos implícitos para definir um problema de acesso em grafo que pode ser resolvido em tempo polinomial em um computador quântico, mas que requer tempo exponencial para resolver em qualquer computador clássico.[6]

Esquema de rotulagem de adjacência[editar | editar código-fonte]

No contexto das representações eficientes de grafos, J.H. Muller definiu um esquema de rotulagem de adjacência ou uma estrutura local para um grafo G em uma dada família F de grafos como sendo uma atribuição de um identificador O(log n) bits para cada vértice de G, em conjunto com um algoritmo (que pode depender de F, mas é independente do grafo específico G) que toma como entrada dois identificadores de vértice e determina se eles são ou não extremidades de uma aresta em G. Ou seja, este tipo de representação implícita é análogo a uma matriz de adjacências: é simples verificar se dois vértices são adjacentes, mas encontrar os vizinhos de qualquer vértice pode envolver fazer um loop através de todos os vértices e testar quais são vizinhos.[7]

Famílias de grafo com esquemas de rotulagem de adjacência incluem:

Grafos de grau limitado
Se todos os vértices de G tem no máximo d vizinhos, pode-se numerar os vértices de G de 1 a n e fazer com que o identificador para um vértice seja a (d + 1)- tupla de seu próprio número e os números de seus vizinhos. Dois vértices são adjacentes quando os primeiros números em seus identificadores aparecerem mais tarde no identificador de outro vértice. De forma mais geral, a mesma abordagem pode ser utilizada para fornecer uma representação implícita para grafos com arboricidade limitada ou degenerecência limitada, incluindo o grafo planar e os grafos em qualquer família de grafos fechada sob grafos menores.[8][9]
Grafos de interseção
Um grafo de intervalo é um grafo intersecção de um conjunto de Retas em uma Reta real. A ele pode ser atribuído um esquema de rotulagem de adjacência, em que os pontos que são extremidades de segmentos de reta são numeradas de 1 a 2n e cada um dos vértices do grafo é representado pelos números de um das duas extremidades do seu intervalo correspondente. Com esta representação, pode-se verificar se dois vértices são adjacentes, comparando os números que representam e verificando se esses números definem intervalos que se sobrepõem. A mesma abordagem funciona para outros grafos de intersecção geométricas, incluindo os grafos limitados por boxicity e o grafo de círculo, e todos os subgrupos desses grupos, como os grafos completamente separáveis e os cografos.[8][10] No entanto, uma representação por grafo de intersecção geométrica nem sempre implica na existência de um esquema de rotulagem de adjacência, pois pode ser necessário mais do que um número logarítmico de bits para especificar cada objeto geométrico. Por exemplo, representar um grafo como um grafo de disco unitário pode exigir uma quantidade exponencial de bits para as coordenadas dos centros do disco.[11]
Grafos de comparabilidade de baixa dimensão
O grafo de comparabilidade para um conjunto parcialmente ordenado tem um vértice para cada set e uma aresta entre dois elementos fixos que estão relacionados pela ordem parcial. A dimensão de uma ordem parcial é o número mínimo de ordens lineares cuja intersecção é a ordem parcial dada. Se uma ordem parcial tem dimensão de ordem limitada, então um esquema de rotulagem de adjacência para os vértices no seu grafo de comparabilidade pode ser definido rotulando cada vértice com a sua posição em cada uma das ordens lineares definidoras, e determinando que dois vértices são adjacentes se cada par correspondente de números em seus rótulos tem a mesma relação de ordem que cada outro par. Em particular, isto permite um sistema de rotulagem de adjacência para os grafos de comparabilidade cordais, que vêm de ordens parciais de dimensão, no máximo, quatro.[12][13]

A conjectura da representação implícita[editar | editar código-fonte]

Nem todas as famílias de grafo têm estruturas locais. Para algumas famílias, uma simples contagem de argumentos prova que os esquemas de rotulagem de adjacência não existem: somente O(n log n) bits podem ser utilizados para representar um grafo por inteiro, de modo que uma representação deste tipo só pode existir quando o número de grafos de n-vértices em uma dada família F é no máximo 2O(n log n). Famílias de grafos que tem um número de grafos maior que esse, como os grafos bipartidos ou os grafos livres de triângulo não tem esquema de rotulagem de adjacência.[8][10] No entanto, até famílias de grafos em que o número de grafos na família é pequeno podem não ter um esquema de rotulagem de adjacência; por exemplo, a família de grafos que possui menos arestas do que vértices tem 2O(n log n) grafos de n-vértices mas não tem um esquema de rotulagem de adjacência, porque poder-se-ia transformar qualquer grafo dado em um grafo maior desse grupo apenas adicionando um novo vértice isolado a cada aresta, sem mudar sua rotulabilidade.[7][10] Kannan et al. perguntou se ter um caracterização de grafo proibido e ter pelo menos 2O(n log n) grafos de n-vertices é o bastante para garantir a existência de um esquema de rotulagem de adjacência; essa pergunta, Spinrad acabou deixando como uma conjectura, e permanece aberta.[8][10] Entre as famílias de grafos que satisfazem as condições da conjectura e para as quais não se conhece nenhum esquema de de rotulagem de adjacência estão a família de grafos de disco e a família de grafos de intersecção de segmento de reta.

Esquemas de rotulagem e grafos universais induzidos[editar | editar código-fonte]

Se uma familia de grafos F tem um sistema de rotulagem de adjacência,então, os grafos de n - vértices de F podem ser representados como subgrafos induzidos de um grafo universal de tamanho polinomial, o grafo consistindo de em todos os identificadores de vértices possíveis. Por outro lado,se um grafo universal induzido deste tipo pode ser construído, em seguida, as identidades dos seus vértices podem ser usados como rótulos em um sistema de rotulagem de adjacência.[8] Para esta aplicação de representações de grafo implícitas, é importante que as etiquetas utilizem o menor número de bits possível, porque o número de bits nos rótulos traduz-se diretamente para o número de vértices do grafo universal induzido. Alstrup e Rauhe mostraram que qualquer árvore tem um esquema de rotulagem de adjacência com log2 n + O(Predefinição:Log-star n) bits por rótulo, do qual resulta que qualquer grafo com uma arboricidade k tem um esquema com k log2 n + O(Predefinição:Log-star n) bits por rótulo e um grafo universal com nk2O(Predefinição:Log-star n) vértices. Em particular, grafos planares têm arboricidade no máximo três, para que eles tenham grafos universais com um número quase-cúbico de vértices.[14] Esta ligação foi melhorada por Gavoille e Labourel que mostrou que os grafos planares e as famílias de grafos "minor-closed" têm um sistema de rotulagem com 2 log2 n + O(log log n) bits por rótulo e que os grafos de largura de arvore limitada tem um sistema de rotulagem com log2 n + O(log log n) bits por rótulo.[15]

Evasividade[editar | editar código-fonte]

A conjectura de Aanderaa–Karp–Rosenberg trata sobre grafos implícitos dados como um conjunto de vértices rotulados com uma regra da caixa preta para determinar quando dois vértices são adjacentes. A definição difere de um esquema de rotulagem adjacente no sentido de que a regra pode ser para um grafo específico em vez de ser uma regra genérica que se aplica a todos os grafos em uma família. Por causa dessa diferença, todo grafo tem uma representação implícita. Por exemplo, a regra pode ser usada para procurar o par de vértices em um matriz de adjacência separada. De todo modo, um algoritmo que recebe como entrada um grafo implícito desse tipo, deve operar nele somente através do teste de adjacência implícita, sem referência a como o teste é implementado.

Uma "propriedade de grafo" é a questão de se determinar se um grafo pertence a uma dada família de grafos. A resposta deve permanecer invariante sob qualquer re-rotulação dos vértices. Nesse contexto, a questão a ser determinada é quantos pares de vértices devem ser testados para adjacência, no pior caso, antes que essa propriedade possa ser determinada como verdadeira ou falsa para um dado grafo implicito. Rivest e Vuilemin provaram que qualquer algoritmo determinístico para qualquer propriedade de grafo não trivial deve testar um número quadrático de pares de vértices.[16] A conjectura completa de Aanderaa-Karp-Rosenberg é que qualquer algoritmo determinístico para uma propriedade de grafo monotônica (que permanece verdadeira se mais arestas são adicionadas a um grafo com a propriedade) deve, em alguns casos testar cada par possível de vértices. Vários casos da conjectura foram provados serem verdadeiros, por exemplo, sabe-se que é verdadeira para grafos com um número primo de vértices[17]— Mas a conjectura completa permanece aberta. Variantes do problema para algoritmos randômicos e algoritmos quânticos também têm sido estudadas.

Bender e Ron mostraram que, no mesmo modelo usado para a conjectura de evasividade, é possível somente em tempo constante distinguir grafos direcionados aciclícos de grafos que estão bem longe de serem acíclicos. Em contrapartida, um tempo rápido assim não é possível em modelos de grafos implicítos baseados em vizinhança.[18]

Referências

  1. ↑ Korf, Richard E. (2008), «Linear-time disk-based implicit graph search», Journal of the ACM, 55 (6), Article 26, 40pp, MR 2477486, doi:10.1145/1455248.1455250 .
  2. ↑ Korf, Richard E. (2008), «Minimizing disk I/O in two-bit breadth-first search», Proc. 23rd AAAI Conf. on Artificial Intelligence (PDF), pp. 317–324, The standard 3×3×3 Rubik’s Cube contains 4.3252 × 1019 states, and is too large to search exhaustively. 
  3. ↑ Papadimitriou, Christos (1994), «On the complexity of the parity argument and other inefficient proofs of existence» (PDF), Journal of Computer and System Sciences, 48 (3): 498–532, doi:10.1016/S0022-0000(05)80063-7 
  4. ↑ Immerman, Neil (1999), «Exercise 3.7 (Everything is a Graph)», Descriptive Complexity, ISBN 978-0-387-98600-5, Graduate Texts in Computer Science, Springer-Verlag, p. 48 .
  5. ↑ Yannakakis, Mihalis (2009), «Equilibria, fixed points, and complexity classes», Computer Science Review, 3 (2): 71–85, doi:10.1016/j.cosrev.2009.03.004 .
  6. ↑ Childs, Andrew M.; Cleve, Richard; Deotto, Enrico; Farhi, Edward; Gutmann, Sam; Spielman, Daniel A. (2003), «Exponential algorithmic speedup by a quantum walk», Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, New York: ACM, pp. 59–68, MR 2121062, doi:10.1145/780542.780552 .
  7. ↑ a b Muller, John Harold (1988), Local structure in graph classes, Ph.D. thesis, Georgia Institute of Technology .
  8. ↑ a b c d e Kannan, Sampath; Naor, Moni; Rudich, Steven (1992), «Implicit representation of graphs», SIAM Journal on Discrete Mathematics, 5 (4): 596–603, MR 1186827, doi:10.1137/0405049 .
  9. ↑ Chrobak, Marek; Eppstein, David (1991), «Planar orientations with low out-degree and compaction of adjacency matrices» (PDF), Theoretical Computer Science, 86 (2): 243–266, doi:10.1016/0304-3975(91)90020-3 .
  10. ↑ a b c d Spinrad, Jeremy P. (2003), «2. Implicit graph representation», Efficient Graph Representations, ISBN 0-8218-2815-0, pp. 17–30 .
  11. ↑ Kang, Ross J.; Müller, Tobias (2011), Sphere and dot product representations of graphs (PDF), consultado em 9 de julho de 2016, cópia arquivada (PDF) em |arquivourl= requer |arquivodata= (ajuda) 🔗 .
  12. ↑ Ma, Tze Heng; Spinrad, Jeremy P. (1991), «Cycle-free partial orders and chordal comparability graphs», Order, 8 (1): 49–61, MR 1129614, doi:10.1007/BF00385814 .
  13. ↑ Curtis, Andrew R.; Izurieta, Clemente; Joeris, Benson; Lundberg, Scott; McConnell, Ross M. (2010), «An implicit representation of chordal comparability graphs in linear time», Discrete Applied Mathematics, 158 (8): 869–875, MR 2602811, doi:10.1016/j.dam.2010.01.005 .
  14. ↑ Alstrup, Stephen; Rauhe, Theis (2002), «Small induced-universal graphs and compact implicit graph representations» (PDF), Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science: 53–62, doi:10.1109/SFCS.2002.1181882 .
  15. ↑ Arnaud, Labourel; Gavoille, Cyril (2007), «Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs» (PDF), Proceedings of the 15th annual European Symposium on Algorithms: 582-593, doi:10.1007/978-3-540-75520-3_52 .
  16. ↑ Rivest, Ronald L.; Vuillemin, Jean (1975), «A generalization and proof of the Aanderaa-Rosenberg conjecture», Proc. 7th ACM Symposium on Theory of Computing, Albuquerque, New Mexico, United States, pp. 6–11, doi:10.1145/800116.803747 .
  17. ↑ Kahn, Jeff; Saks, Michael; Sturtevant, Dean (1983), «A topological approach to evasiveness», Symposium on Foundations of Computer Science, Los Alamitos, CA, USA: IEEE Computer Society, pp. 31–33, doi:10.1109/SFCS.1983.4 .
  18. ↑ Bender, Michael A.; Ron, Dana (2000), «Testing acyclicity of directed graphs in sublinear time», Automata, languages and programming (Geneva, 2000), Lecture Notes in Comput. Sci., 1853, Berlin: Springer, pp. 809–820, MR 1795937, doi:10.1007/3-540-45022-X_68 .
Obtida de "https://pt.wikipedia.org/w/index.php?title=Grafo_implícito&oldid=54877360"