Wikipédia

Largura de caminho: diferenças entre revisões

Explorar interativamente o histórico
← Ver a alteração anteriorVer a alteração posterior →
Conteúdo apagado Conteúdo adicionado
VisualTexto wiki
concordancia
concordância
Linha 39:
O jogo de busca de nós em um grafo é uma forma de [[Jogo de perseguição e fuga|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 {{harvtxt|Kirousis|Papadimitriou|1985}} 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.
 
==LimitesLimitantes==
[[File:Caterpillar tree.svg|thumb|Uma [[árvore centopeia (grafo)]], um grafo máximo com largura de caminho um.]]
Todo grafo de ''n''-vértices com largura de caminho ''k'' tem no máximo {{nowrap|''k''(''n'' &minus; ''k'' + (''k'' &minus; 1)/2))}} 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 {{nowrap|''n'' &minus; ''k''}} [[Problema do clique|cliques máximos]], cada um contendo {{nowrap|''k'' + 1}} vértices; em uma ''k''-árvore que não é um {{nowrap|(''k'' + 1)-clique}} 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 [[árvore centopeia (grafo)| árvores centopeia]].<ref>{{harvtxt|Proskurowski|Telle|1999}}.</ref>
Linha 69:
É NP-difícil aproximar a largura de caminho de um grafo para dentro de uma constante aditiva.<ref name="bghk92"/> A melhor [[algoritmo de aproximação|taxa de aproximação]] conhecida de um algoritmo de aproximação em tempo polinomial é O((log&nbsp;''n'')<sup>3/2</sup>).<ref>{{harvtxt|Feige|Hajiaghayi|Lee|2005}}.</ref> Para algoritmos de aproximação anteriores para largura de caminho, veja {{harvtxt|Bodlaender|Gilbert|Hafsteinsson|Kloks|1992}} e {{harvtxt|Guha|2000}}. Para aproximaçãoes em classes de grafos restritas, veja {{harvtxt|Kloks|Bodlaender|1992}}.
 
==GrafosMenores menoresde Grafo==
Um [[grafo menor|menor]] de um grafo ''G'' é outro grafo formado a partir de ''G'' por meio de contração e remoção de arestas, e remoção de vértices. Grafos menores possuem uma teoria profunda em que diversos resultados envolvem largura de caminho.
 
===Excluindo uma floresta===
Se uma família ''F'' de grafos é fechada sob a operação de gerar grafos menores de grafos (todo menor de um membro de ''F'' está também em ''F''), então pelo [[Teorema de Robertson–Seymour]] ''F'' pode ser caracterizadocaracterizada com os grafos que não tem nenhum menor em ''X'', onde ''X'' é um conjunto finito de [[:en:forbiddenmenores graphde characterization|grafos menoresgrafo proibidos]].<ref name="gm20">{{harvtxt|Robertson|Seymour|2004}}.</ref> ParaPor exemplo, o [[teorema de Wagner]] constata que os grafos planares são os grafos que nem possuem o [[grafo completo]] ''K''<sub>5</sub> nem o [[grafo bipartido completo]] ''K''<sub>3,3</sub> como menores. Em vários casos, as propriedades de ''F'' e as propriedades de ''X'' são proximamente relacionadas, e a primeira que resulta deste tipo foi por {{harvtxt|Robertson|Seymour|1983}},<ref name="rs83"/> e se refere à relação entre largura de caminho limitada com a existência de uma [[árvore (grafo)|floresta]] na família de grafos menores proibidos. Especificamente, define uma família ''F'' de grafos ter ''largura de caminho limitada'' se existe uma constante ''p'' que para cada grafo em ''F'' tem largura de caminho no máximo ''p''. Então, uma família de menores-fechada ''F'' tem largura de caminho limitada se e somente se o conjunto ''X'' de grafos menores proibidos para ''F'' inclui no mínimo uma floresta.
 
Por outro lado, esse resultado é uma trivial para provar: se ''X'' não inclui ao menos uma floresta, então os grafos de ''X''-livres-de-menor não tem largura de caminho limitada. Pois, neste caso, os grafos de ''X''-livres-de-menor incluem todas as florestas, e em particular eles incluem as [[árvore binária|árvores binárias perfeitas]]. Mas uma árvore binária perfeita com 2''k''&nbsp;+&nbsp;1 níveis tem uma largura de caminho ''k'', então neste caso os grafos de ''X''-livres-de-menor tem largura de caminho ilimitada. Na outra direção, se ''X'' contém uma floresta de ''n''-vértices, então os grafos de ''X''-livres-de-menor tem largura de caminho no máximo ''n''&nbsp;&minus;&nbsp;2.<ref>{{harvtxt|Bienstock|Robertson|Seymour|Thomas|1991}}; {{harvtxt|Diestel|1995}}; {{harvtxt|Cattell|Dinneen|Fellows|1996}}.</ref>
Obtida de "https://pt.wikipedia.org/wiki/Largura_de_caminho"