Caminho induzido - Induced path

Um caminho induzido de comprimento quatro em um cubo . Encontrar o caminho induzido mais longo em um hipercubo é conhecido como o problema da cobra na caixa .

No matemático área da teoria gráfico , um caminho induzida num gráfico undirected L é um caminho que é um subgráfico induzida de L . Isto é, este é uma sequência de vértices em L de modo que cada dois vértices adjacentes na sequência são ligados por uma extremidade em L , e cada dois vértices não adjacentes na sequência não estão ligados por qualquer vantagem em L . Um caminho induzido às vezes é chamado de cobra , e o problema de encontrar caminhos longos induzidos em gráficos de hipercubos é conhecido como problema da cobra na caixa .

Da mesma forma, um ciclo induzido é um ciclo que é um subgráfico induzido de G ; os ciclos induzidos também são chamados de ciclos sem corda ou (quando a duração do ciclo é de quatro ou mais) orifícios . Um anti -furo é um furo no complemento de G , ou seja, um anti-furo é o complemento de um furo.

O comprimento do caminho induzido mais longo em um gráfico às vezes é chamado de número do desvio do gráfico; para gráficos esparsos , ter um número de desvio limitado é equivalente a ter uma profundidade de árvore limitada . O número de caminho induzida de um gráfico G é o menor número de caminhos induzidas em que os vértices do gráfico pode ser particionado, e o estreitamente relacionado número tampa caminho de L é o menor número de caminhos induzidas que em conjunto incluem todos os vértices de L . A circunferência de um gráfico é a duração de seu ciclo mais curto, mas esse ciclo deve ser um ciclo induzido, pois qualquer acorde pode ser usado para produzir um ciclo mais curto; por razões semelhantes, a circunferência ímpar de um gráfico é também o comprimento de seu ciclo induzido ímpar mais curto.

Exemplo

Comprimentos máximos de cobras ( L s ) e bobinas ( L c ) no problema das cobras na caixa para dimensões n de 1 a 4

A ilustração mostra um cubo, um gráfico com oito vértices e doze arestas e um caminho induzido de comprimento quatro neste gráfico. Uma análise de caso simples mostra que não pode mais haver um caminho induzido no cubo, embora ele tenha um ciclo induzido de comprimento seis. O problema de encontrar o caminho ou ciclo induzido mais longo em um hipercubo, colocado pela primeira vez por Kautz (1958) , é conhecido como o problema da cobra na caixa e tem sido estudado extensivamente devido às suas aplicações na teoria da codificação e engenharia .

Caracterização de famílias de grafos

Muitas famílias de grafos importantes podem ser caracterizadas em termos de caminhos ou ciclos induzidos dos grafos na família.

  • Trivialmente, os gráficos conectados sem nenhum caminho induzido de comprimento dois são os gráficos completos , e os gráficos conectados sem nenhum ciclo induzido são as árvores .
  • Um gráfico sem triângulo é um gráfico sem ciclo induzido de comprimento três.
  • As cografias são exatamente os gráficos sem caminho induzido de comprimento três.
  • Os gráficos cordais são os gráficos sem ciclo induzido de comprimento quatro ou mais.
  • Os gráficos sem buracos pares são os gráficos que não contêm ciclos induzidos com um número par de vértices.
  • Os gráficos trivialmente perfeitos são aqueles que não possuem um caminho induzido de comprimento três nem um ciclo induzido de comprimento quatro.
  • Pelo teorema do gráfico perfeito forte, os gráficos perfeitos são os gráficos sem furo ímpar e sem anti-furo ímpar.
  • Os gráficos hereditários de distância são os gráficos em que cada caminho induzido é o caminho mais curto e os gráficos em que cada dois caminhos induzidos entre os mesmos dois vértices têm o mesmo comprimento.
  • Os gráficos de blocos são os gráficos nos quais há no máximo um caminho induzido entre quaisquer dois vértices, e os gráficos de blocos conectados são os gráficos nos quais há exatamente um caminho induzido entre cada dois vértices.

Algoritmos e complexidade

É NP-completo determinar, para um gráfico G e parâmetro k , se o gráfico tem um caminho induzido de comprimento de pelo menos k . Garey & Johnson (1979) atribuem esse resultado a uma comunicação não publicada de Mihalis Yannakakis . No entanto, esse problema pode ser resolvido em tempo polinomial para certas famílias de grafos, como gráficos asteroidais sem triplo ou sem buracos longos.

Também é NP-completo para determinar se os vértices de um gráfico podem ser particionados em dois caminhos induzidos ou dois ciclos induzidos. Como consequência, determinar o número do caminho induzido de um gráfico é NP-difícil.

A complexidade de aproximar o caminho induzido mais longo ou problemas de ciclo pode estar relacionada à de encontrar grandes conjuntos independentes em gráficos, pela seguinte redução. De qualquer gráfico L com n vértices, formar um outro gráfico H com o dobro de vértices como L , através da adição de L n ( n  - 1) / 2 vértices com dois vizinhos, cada um para cada par de vértices em L . Em seguida, se L tem um conjunto independente de tamanho k , H deve ter um caminho induzida e um ciclo induzida de comprimento 2 k , formada por uma alternância de vértices do conjunto independente em L com vértices de I . Por outro lado, se H tem um caminho induzido ou ciclo de comprimento k , qualquer conjunto máximo de vértices não adjacentes em G desse caminho ou ciclo forma um conjunto independente em G de tamanho pelo menos k / 3. Assim, o tamanho do conjunto independente máximo em L está dentro de um factor constante do tamanho do maior caminho induzida e o mais longo ciclo induzida em H . Portanto, pelos resultados de Håstad (1996) sobre a inadequação de conjuntos independentes, a menos que NP = ZPP, não existe um algoritmo de tempo polinomial para aproximar o caminho induzido mais longo ou o ciclo induzido mais longo para dentro de um fator de O ( n 1 / 2-ε ) da solução ótima.

Furos (e anti-furos em gráficos sem ciclos sem corda de comprimento 5) em um gráfico com n vértices em arestas podem ser detectados no tempo (n + m 2 ).

Ciclos atômicos

Os ciclos atômicos são uma generalização dos ciclos sem acordes, que não contêm n- acordes. Dado algum ciclo, um n -chord é definido como um caminho de comprimento n conectando dois pontos no ciclo, onde n é menor que o comprimento do caminho mais curto no ciclo que conecta esses pontos. Se um ciclo não tem n acordes, é chamado de ciclo atômico, porque não pode ser decomposto em ciclos menores. No pior caso, os ciclos atômicos em um gráfico podem ser enumerados em tempo O ( m 2 ), onde m é o número de arestas do gráfico.

Notas

Referências