A origem da noção de largura da árvore

61

Minha pergunta hoje é (como sempre) um pouco boba; mas eu pediria que você considerasse gentilmente.

Eu queria saber sobre a gênese e / ou motivação por trás do conceito de largura de árvore. Eu certamente entendo que ele é usado nos algoritmos do FPT, mas não acho que essa tenha sido a razão pela qual essa noção foi definida.

Escrevi as anotações do escriba sobre esse tópico na classe do professor Robin Thomas . Eu acho que entendo algumas das aplicações desse conceito (como ele transfere propriedades de separação da árvore para o gráfico decomposto), mas por alguma razão não estou realmente convencido de que a razão pela qual esse conceito tenha sido desenvolvido foi medir a proximidade de um gráfico para uma árvore.

Vou tentar me esclarecer mais (não tenho certeza se posso, por favor, deixe-me saber se a pergunta não está clara). Eu gostaria de saber se noções semelhantes existem em algum outro ramo da matemática de onde essa noção foi supostamente "emprestada". Meu palpite será topologia - mas, devido à minha falta de experiência, não posso dizer nada.

A principal razão pela qual estou curioso sobre isso seria: na primeira vez que li sua definição, não sabia ao certo por que e como alguém iria concebê-la e com que finalidade. Se a pergunta ainda não estiver clara, eu finalmente tentaria declarar desta maneira - vamos fingir que a noção de largura de árvore não existe. Quais perguntas naturais (ou extensões de alguns teoremas / conceitos matemáticos) a configurações discretas levarão a conceber uma definição (deixe-me usar a palavra envolvida) como a da largura da árvore.

Akash Kumar
fonte
2
fyi o link anotador do escriba recebe erro 403 proibido.
vzn

Respostas:

58

Se você realmente quer saber o que levou Neil Robertson e eu à largura da árvore, não foram algoritmos. Estávamos tentando resolver a conjectura de Wagner de que, em qualquer conjunto infinito de gráficos, um deles é menor do que o outro, e estávamos no começo. Sabíamos que era verdade se restringíssemos a gráficos sem o caminho do k-vértice; deixe-me explicar o porquê. Sabíamos que todos esses gráficos tinham uma estrutura simples (mais exatamente, todo gráfico sem o caminho do k-vértice possui essa estrutura e todo gráfico com essa estrutura não tem o caminho do 2-k-vértice); e sabíamos que em todo conjunto infinito de gráficos, todos com essa estrutura, um era menor do que outro. Portanto, a conjectura de Wagner era verdadeira para gráficos com um limite no comprimento máximo do caminho.

Também sabíamos que isso era verdade para gráficos sem k-star menor, novamente porque tínhamos um teorema de estrutura para tais gráficos. Tentamos procurar menores mais gerais que tivessem teoremas de estrutura correspondentes que pudéssemos usar para provar a conjectura de Wagner e que nos levaram à largura do caminho; exclua QUALQUER árvore como menor e você terá a largura do caminho limitada; se você tiver a largura do caminho limitado, haverá árvores que você não poderá ter como menor. (Esse foi um teorema difícil para nós; tivemos uma prova tremendamente difícil no primeiro artigo sobre Graph Minors, não leia, pode ser muito mais fácil.) Mas poderíamos provar a conjectura de Wagner para gráficos com largura de caminho limitada, e isso significava que era verdade para gráficos que não continham nenhuma árvore fixa como menor; uma grande generalização do caminho e dos casos em estrela que mencionei anteriormente.

Enfim, com isso feito, tentamos ir mais longe. Como não pudemos fazer gráficos gerais, pensamos em gráficos planares. Encontramos um teorema de estrutura para os gráficos planares que não continham nenhum gráfico fixo fixo como menor (isso foi fácil); era limitado pela largura da árvore. Provamos que, para qualquer gráfico plano fixo, todos os gráficos planos que não o continham como menor limitavam a largura da árvore. Como você pode imaginar, isso foi realmente emocionante; por coincidência, o teorema da estrutura para excluir gráficos planares (dentro de gráficos planares maiores) foi uma reviravolta natural no teorema da estrutura para excluir árvores (dentro de gráficos gerais). Nós sentimos que estávamos fazendo algo certo. E isso vamos provar a conjectura de Wagner para todos os gráficos planares, porque tínhamos esse teorema da estrutura.

Como a largura da árvore funcionava para excluir gráficos planares dentro de gráficos planares maiores, era uma questão natural saber se funcionava para excluir gráficos planares dentro de gráficos não planares - era verdade que, para cada gráfico plano fixo, todos os gráficos que não o continham como um menor tinha limitado a largura da árvore? Isso não conseguimos provar por um longo tempo, mas foi assim que começamos a pensar na largura da árvore dos gráficos gerais. E uma vez que tivemos o conceito de largura da árvore, ficou bem claro que era bom para algoritmos. (E sim, não tínhamos ideia de que Halin já tinha pensado na largura da árvore.)

Paul Seymour
fonte
18
Bem-vindo ao cstheory, e obrigado pela ótima resposta!
Suresh Venkat
Muito obrigado por dedicar um tempo ao professor Seymour. Essa resposta é cheia de revelações reveladoras e cobre a parte histórica que a pergunta originalmente pretendia. Então, marcando este como a resposta aceita :)
Akash Kumar
61

Veja como você mesmo pode criar o conceito de largura de árvore.

Suponha que você queira contar o número de conjuntos independentes no gráfico a seguir.

Conjuntos independentes podem ser particionados em locais onde o nó superior está ocupado e em locais desocupados

Agora, observe que, sabendo se o nó superior está ocupado, é possível contar o número de conjuntos independentes em cada subproblema separadamente e multiplicá-los. Repetir esse processo recursivamente fornece um algoritmo para contar conjuntos independentes com base em separadores de gráficos.

Agora, suponha que você não tenha mais uma árvore. Isso significa que os separadores são maiores, mas você pode usar a mesma ideia. Considere contar conjuntos independentes no gráfico a seguir.

Use a mesma idéia de dividir o problema em subproblemas no separador, para obter o seguinte

Como no exemplo anterior, cada termo na soma se decompõe em duas tarefas menores de contagem no separador.

Observe que temos mais termos na soma do que no exemplo anterior, porque precisamos enumerar todas as configurações em nosso separador, que podem crescer exponencialmente com o tamanho do separador (tamanho 2, neste caso).

A decomposição em árvore é uma estrutura de dados para armazenar compactamente essas etapas de particionamento recursivo. Considere o gráfico a seguir e sua decomposição em árvore

Para contar usando essa decomposição, você primeiro corrige valores nos nós 3,6, que o dividem em 2 subproblemas. No primeiro subproblema, você também corrige o nó 5, que divide sua parte em duas subpartes menores.

O tamanho do maior separador em uma decomposição recursiva ideal é precisamente a largura da árvore. Para problemas de contagem maiores, o tamanho do maior separador domina o tempo de execução, e é por isso que essa quantidade é tão importante.

Quanto à noção de largura da árvore que mede o quão próximo o gráfico está de uma árvore, uma maneira de torná-lo intuitivo é observar a derivação alternativa da decomposição da árvore - a partir da correspondência com gráficos cordais. Primeiro triangule o gráfico atravessando os vértices em ordem e interconectando todos os vizinhos "de ordem superior" de cada vértice.

Em seguida, construa a decomposição da árvore pegando as panelinhas máximas e conectando-as se a interseção delas for um separador máximo.

Abordagens recursivas baseadas em separadores e triangulações para construir decomposição de árvores são equivalentes. A largura da árvore + 1 é o tamanho da maior clique na triangulação ideal do gráfico ou, se o gráfico já estiver triangulado, apenas o tamanho da maior clique.

Então, de certa forma, gráficos cordais de largura da árvore tw podem ser pensados ​​como árvores, onde, em vez de nós únicos, temos cliques de tamanho sobrepostos no máximo tw + 1. Gráficos não-cordais são "árvores de clique" com algumas arestas de clique ausentes

Aqui estão alguns gráficos de acordes e a largura da árvore.

Yaroslav Bulatov
fonte
12
Muito boa explicação Yaroslav ... Muito obrigado
Akash Kumar
4
Uma pergunta rápida Yaroslav .. Como você desenhou figuras tão legais? Você me fez lembrar como sou ineficiente no uso de recursos. Não sabia que você pode fazer coisas legais em um fórum de teoria :-). Partilha da mente, como você fez coisas tão incríveis? Obrigado
Akash Kumar
5
Eu tenho uma coleção de scripts do Mathematica para gerar diagramas como este ... para obter código para um tipo de diagrama específico, encontre um exemplo em yaroslavvb.blogspot.com ou mathematica-bits.blogspot.com e siga o link "Notebook" em esse post
Yaroslav Bulatov
6
Esta resposta é tão incrível. Uau.
toto
a aresta 7-10 é necessária no gráfico de acordes?
J. Schmidt
29

Acredito que a largura da árvore começou com o trabalho de Robertson Seymour já apresentado. Mas alguns precursores anteriores parecem ser:

  • O conceito de "dimensão" de um gráfico que controlaria o comportamento dos algoritmos de programação dinâmica nele, de Bertelé, Umberto; Brioschi, Francesco (1972), Programação Dinâmica Não Serial .

  • O conceito de jogos de evasão de perseguição em gráficos, de Parsons, TD (1976). "Evasão de perseguição em um gráfico". Teoria e Aplicações de Gráficos . Springer-Verlag. 426-441. Uma variante disso mostrou-se muito mais tarde equivalente à largura da árvore: Seymour, Paul D .; Thomas, Robin (1993), "Pesquisa de gráfico e um teorema min-max para a largura da árvore", Journal of Combinatorial Theory, Série B 58 (1): 22–33, doi: 10.1006 / jctb.1993.1027 .

  • Hierarquias separadoras para gráficos planares, a partir de Ungar, Peter (1951), "Um teorema dos gráficos planares", Journal of the London Mathematics Society 1 (4): 256, doi: 10.1112 / jlms / s1-26.4.256 e continuando com vários artigos de Lipton e Tarjan em 1979-1980. O tamanho do maior separador em uma hierarquia desse tipo está intimamente relacionado à largura da árvore.

Avançando para um momento em que as idéias de Robertson-Seymour já possam ter começado a flutuar, há também um artigo anterior ao Graph Minors II que conecta explicitamente as idéias de evasão e evasão de busca e que define uma noção de largura equivalente à largura de caminho : Ellis, JA; Sudborough, IH; Turner, JS (1983), "Separação de gráficos e número de pesquisa", Proc. 1983 Allerton Conf. em comunicação, controle e computação.

David Eppstein
fonte
3
Penso que isso não é verdade: aparentemente Halin descobriu o conceito dez anos antes, mas isso permaneceu despercebido até a redescoberta de Robertson e Seymour. Veja a resposta abaixo para obter detalhes.
Hermann Gruber
21

Em sua monografia sobre teoria dos grafos, Reinhard Diestel traça o conceito de largura da árvore e decomposições de árvores em um artigo de 1976 de Halin (embora não use esses nomes). Ele também atribui a este artigo o resultado de que os gráficos de grade planar têm largura de árvore ilimitada. Obviamente, ele também menciona o artigo posterior de Robertson e Seymour, que "redescobriram o conceito, obviamente inconscientes do trabalho de Halin" (desculpe se minha tradução é ruim).

  • Rudolf Halin. Funções para gráficos, J. Geometry 8 (1976): 171–186S
  • Reinhard Diestel. Graphentheorie , 3ª edição alemã, Notizen zu Kapitel 10. (Algumas edições em inglês do livro estão disponíveis on-line para download gratuito).
Hermann Gruber
fonte
4
Parece bastante preciso. De Diestel 3a (inglês) edição pp.354–355: "As noções de decomposição e largura de árvore foram introduzidas pela primeira vez (sob nomes diferentes) por R. Halin, funções S para gráficos, J. Geometry 8 (1976) 171–186. Entre outras coisas, Halin mostrou que as grades podem ter uma largura de árvore arbitrariamente grande. Robertson e Seymour reintroduziram os dois conceitos, aparentemente desconhecendo o artigo de Halin, com referência direta a K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), 570-590. (Este é o artigo seminal que introduziu decomposições de árvores simples "
András Salamon
11
Desculpe Sr. Gruber por esta reação super tarde. Vi sua resposta há muito tempo, não sabia se poderia aceitar outras respostas depois de já ter aceitado uma. Sua resposta é bastante precisa e parece morto em como observado por Mr. Salamon bem
Akash Kumar
16

A noção de largura da árvore [1] (e a noção semelhante de largura da ramificação ) foi introduzida por Robertson e Seymour em seus documentos seminais no Graph Minors .

Eles inicialmente introduzido árvore de largura , a fim de obter um teste algoritmo em tempo polinomial se um gráfico tem um subgráfico contraível para um grafo planar fixo .HGH

Veja: N. Robertson, PD Seymour. Menores de gráfico. II Aspectos algorítmicos da largura das árvores . JCT Série B (1986)

Mathieu Chapelle
fonte
Obrigado por trazer esta referência. Mas eu já estava ciente dessa referência (eu sabia que era um artigo de Robertson / Seymour - nunca tinha lido). Só não tinha certeza do que levou Robertson, Seymour a inventar essa noção. Obrigado por apontar isso. Mas eu estava procurando algo parecido com o que o professor Eppstein disse, marcando isso como a resposta aceita.
Akash Kumar
Ow, não há problema! O objetivo deste site é obter a melhor resposta para uma pergunta, e a resposta do Prof. Eppstein combina muito melhor!
Mathieu Chapelle