Em teoria dos grafos, uma decomposição em caminho de um grafo G é, informalmente, uma representação de G como um caminho "alargado",. e o pathwidth ou largura de caminho de G é um número que mede quanto o caminho foi ampliado em largura a partir de G. Mais formalmente, decomposição em caminho é uma sequência de subconjuntos de vértices de G em que os nós extremos de cada aresta apareçam em um dos subconjuntos e que cada vértice apareça em uma subsequência adjacente dos subconjuntos,. e a largura de caminho é um a menos que o tamanho do maior conjunto em dada decomposição. Largura de caminho é também conhecida como largura de intervalo (um a menos que o tamanho do clique máximo em um supergrafo de intervalo de G), número de separação de vértice, ou número de busca de nós..
Largura de caminho e decomposições em caminho são aproximadamente análogos a largura de árvore e decomposição em árvores. Têm um papel fundamental na teoria de menores de grafos: as famílias de grafos que são fechadas sob menores de grafos e não incluem todas florestas devem ser caracterizadas como tendo caminhos de largura delimitados, e os "vórtices" aparecendo na teoria geral de estrutura para famílias fechadas sob menores de grafos tem caminhos de largura delimitados.. Largura de caminho, e grafos de largura de caminho delimitados, possuem também aplicações em design de VLSI, desenho de grafos, and linguística computacional.
É NP-difícil encontrar a largura de caminho de grafos arbitrários, ou até mesmo fazer uma aproximação precisa.; ; ; .. De qualquer maneira, o problema é tratável por parâmetro fixo: testando se um grafo de largura de caminho k pode ser resolvido em uma quantidade de tempo que depende linearmente do tamanho do grafo mas super-exponencialmente em k.; Além disso, para várias classes especiais de grafos, como árvores, a largura de caminho pode ser computada em tempo polinomial sem dependência em k..; ; ; ; ; ; . Muitos problemas em algoritmos de grafos podem ser resolvidos eficientemente em grafos de largura de caminho delimitados, usando programação dinâmica em uma decomposição em caminho do grafo.. Decomposição em caminho pode também ser usada para medir complexidade de espaço de algoritmos de programação dinâmica em grafos de largura de árvore..
Definição No primeiro de sua famosa série de artigos sobre menores de grafos, Neil Robertson e Paul Seymour definiram a decomposição em caminho de um grafo G ser uma sequência de subconjuntos de Xi de vértices de G, com duas propriedades: Para cada aresta de G, existe um i tal que ambos extremos (vértices) da aresta pertencem ao subconjuntoXi; e Para cada três índices i ≤ j ≤ k, A segunda dessas propriedades é equivalente a requerer que os subconjuntos contendo quaisquer vértices específicos formem uma subsequência adjacente da sequência inteira. Nas definições encontradas nos últimos artigos sobre menores de grafos de Robertson e Seymour, uma decomposição em caminho é uma decomposição em árvore (X,T) em que a árvore subjacente T da decomposição é um caminho.
A largura de uma decomposição em caminho é definida da mesma maneira que é para uma decomposição em árvore, como maxi |Xi| − 1, e a largura de caminho de G é a largura mínima de quaisquer decomposições em caminho de G. A subtração de 1 do tamanho de Xi nessa definição faz pouca diferença na maioria da aplicações de largura de caminho, mas é usada para estabelecer a largura de caminho de um grafo caminho sendo igual a um.
Caracterizações alternativas Como descreve, largura de caminho pode ser caracterizada de várias maneiras equivalentes.
Sequências de colagem Uma decomposição em caminho pode ser descrita com uma sequência de grafos Gi que são "colados" juntos identificando pares de vértices de grafos consecutivos na sequência. de modo que o resultado da execução de todas essas colagens é G. Os grafos Gi devem ser considerados como os subgrafos induzidos por vértice dos conjuntos Xi na primeira definição das decomposições em caminho, com dois vértices em sucessivos subgrafos induzidos em serem colados conjuntamente quando eles são induzidos pelo mesmo vértice em G, e em outra direção pode-se recuperar os conjuntos Xi como os conjuntos de nós dos grafos Gi. A largura da decomposição em caminho é então um menor que o número máximo de vértices em um dos grafos Gi.
Largura de intervalo
A largura de caminho de qualquer grafo G é igual a um a menos que a quantidade dos menores cliques de um grafo de intervalos que contém G como subgrafo., Theorem 29, p. 13. Isto é, para cada decomposição em caminho de G pode-se procurar um super-grafo de intervalos de G, e para cada super-grafo de intervalos pode-se encontrar uma decomposição em caminho de G, tanto que a largura da decomposição seja uma menor que o numero de cliques do grafo de intervalos.
Por um lado, supondo que uma decomposição em caminho de G é dada. Então é possível representar os nó da decomposição como pontos em uma linha (em forma de um caminho) e representar cada vértice v como um intervalo fechado contendo esses pontos como extremos. Logo, os nós da decomposição em caminho compreendendo v correspondem aos pontos representativos no intervalo para v. O grafo de interseção dos intervalos formados dos vértices de G é um grafo de intervalos que engloba G como um subgrafo. Seus cliques máximos são dados pelos conjuntos de intervalos contendo os pontos representativos, e o tamanho do seu clique máximo é um mais a largura de caminho de G.
Por outro lado, se G é um subgrafo de um grafo de intervalos com número de cliques p + 1, então G tem uma decomposição em caminho com largura p, tal que seus nós são dados pelos cliques máximos do grafo de intervalos. Para exemplo, o gráfico de intervalos mostrado com sua representação de intervalos na figura ao lado tem uma decomposição em caminho com cinco nós, correspondendo aos seus cinco cliques máximos ABC, ACD, CDE, CDF, and FG; o tamanho do clique máximo é três e a largura dessa decomposição em caminho é dois.
Esta equivalência entre a largura de caminho e a largura de intervalo é aproximadamente análoga à equivalência entre largura de árvore e número de cliques mínimos (menos um) de um grafo cordal de que dado grafo é um subgrafo. Grafos de intervalos são um caso especial de grafos cordais, e grafos cordais podem ser representado como grafos de interseção de subárvores de uma árvore comum generalizando o modo que os grafos de intervalos são grafos de interseção de sub-caminho de um caminho.
Número de separação de vértices Supondo que os vértices de um grafo G são linearmente ordenados, então o número de separação de vértices de G é o menor número s que, para cada vértice v, no máximo s vértices são anteriores a v na ordenação mas que tem v ou um vértice posterior como vizinho.
O número de separação de vértices de G é o número de separação de vértices mínimo de quaisquer ordenações lineares de G. O número de separação de vértices foi definido por , e é igual à largura de caminho de G.; , Theorem 51. Isso resulta da correspondência anterior com números de cliques em grafos de intervalos: se G é um subgrafo de um grafo de intervalos I, representado (como na figura) de modo que todos os nós extremos dos intervalos são distintos, então a ordenação dos nós extremos da esquerda do intervalo de I têm número de separação de vértices um menor que o número de cliques de I. E, por outro lado, a partir de uma ordenação linear de G, é praticável a derivação de uma representação de intervalos de modo que o extremo esquerdo de um intervalo para um vértice v esteja em sua posição na ordenação em ao extremo direito está a posição do vizinho de v que vem por último na ordenação.
Número de busca de nós O jogo de busca de nós em um grafo é uma forma de perseguição e fuga, no qual um conjunto de investigadores colaboram para rastrear um fugitivo escondido em um grafo. Os rastreadores estão dispostos em vértices do grafo enquanto o fugitivo podem estar em qualquer aresta do grafo, e a localização do fugitivo e seus movimentos são ocultados dos investigadores. A cada turno, alguns ou todos os rastreadores podem se mover (arbitrariamente, não necessariamente ao longo das arestas) de um vértice a outro, e, então, o fugitivo tem o poder de se movimentar por qualquer caminho no grafo que não passe por um vértice ocupado por um investigador. O fugitivo é pego quando ambos extremos de sua aresta estão tomados por rastreadores. O número de busca de nós de um grafo é o número mínimo de rastreadores necessários para assegurar que haja a garantia de o fugitivo ser pego, independente de seu movimento. Como mostram, o número de busca de nós de um grafo é igual a sua largura de intervalo. A estratégia ótima para rastreadores é se movimentar de maneira em que em sucessivos turnos formem os conjuntos de separação de uma ordenação linear com número mínimo de vértices.
Limitantes
Todo grafo de n-vértices com largura de caminho k tem no máximo arestas, e os grafos máximos com largura de caminho k (grafos aos quais não podem ser adicionados mais arestas sem que se aumente a largura de caminho) têm exatamente este número de arestas. Um grafo máximo de largura de caminho k deve ser ou um k-caminho ou um k-centopeia (caterpillar), dois tipos especiais de k-árvore. Uma k-árvore é um grafo cordal com exatamente cliques máximos, cada um contendo vértices; em uma k-árvore que não é um por si só, cada clique máximo ou separa o grafo em dois ou mais componentes, ou contém um único vértice como folha (vértice de grau um), um vértice que pertence a apenas um único clique máximo). Um k-caminho é uma k-árvore com no máximo duas folhas, e uma k-centopeia é uma k-árvore que pode ser particionada em um k-caminho e um conjunto de k-folhas adjecentes a um k-clique separador do k-caminho. Em particular, os grafos máximo de largura da caminho um são exatamente as árvores centopeia..
Como decomposições em caminho são casos especiais de decomposições em árvores, a largura de caminho de qualquer grafo é maio ou igual a sua largura de árvore. A largura de caminho é também menor ou igual à largura de corte, o número mínimo de arestas que cruzam quaisquer cortes entre os vértice menor-numerados e os maior-numerados em um arranjo linear ótimo dos vértice de um grafo; isto acontece porque o número de separação de vértices, o número de vértices menor-numerados com vizinhos maior-numerados, pode no máximo ser igual ao número de arestas cortadas., Lemma 3 p.99; , Theorem 47, p. 24. Por razões similares, a largura de corte é no máximo a largura de caminho vezes o grau máximo dos vértices em um grafo dado., Lemma 1, p. 99; , Theorem 49, p. 24.
Quaisquer florestas n-vértices tem uma largura de caminho O(log n)., Theorem 5, p. 99; , Theorem 66, p. 30. dá um limite superior mais restrito de log3(2n + 1) na largura de caminho de uma floresta n-vértices. Pois, em uma floresta, é sempre possível encontrar um número constante de vértices cuja remoção deixa ser particionada em suas subflorestas menores com no máximo 2n/3 vértices cada. Um arranjo linear formado por particionar recursivamente cada uma dessas duas subflorestas, colocando os vértices separados entre elas, tem um número de busca de vértices logarítmico. A mesma técnica, aplicada à decomposição em árvore de um gráfico, mostra que, se a largura de árvore de um grafo n-vértices G é t, então a largura de caminho de G é O(t log n)., Theorem 6, p. 100; , Corollary 24, p.10. Como grafos planares exteriores, grafos série-paralelos e grafos de Halin possuem todos larguras de árvore limitadas, e têm no máximo largura de caminho logarítmica.