grafos:arboricitypacking

Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

Link para esta página de comparações

Ambos lados da revisão anterior Revisão anterior
grafos:arboricitypacking [2023/05/15 20:10] – edição externa 127.0.0.1grafos:arboricitypacking [2023/05/15 20:11] (atual) – edição externa 127.0.0.1
Linha 1: Linha 1:
 +===== O Teorema do Empocatamento-Cobertura e Arbocidade ====
  
 Agora, consideramos o empacotamento e a cobertura em termos de arestas em vez de vértices. Quantas árvores geradoras **arestas-disjuntas** podemos encontrar em um determinado grafo conexo? E quantas árvores, não necessariamente arestas-disjuntas, são suficientes para cobrir todas as suas arestas? Essas duas perguntas têm dois teoremas clássicos para respondê-las. Mas, em vez de provar esses teoremas diretamente, obteremos ambos como corolários de uma bela unificação recente devida a Bowler e Carmesin: o **//Teorema da Embalagem-Cobertura//**. Agora, consideramos o empacotamento e a cobertura em termos de arestas em vez de vértices. Quantas árvores geradoras **arestas-disjuntas** podemos encontrar em um determinado grafo conexo? E quantas árvores, não necessariamente arestas-disjuntas, são suficientes para cobrir todas as suas arestas? Essas duas perguntas têm dois teoremas clássicos para respondê-las. Mas, em vez de provar esses teoremas diretamente, obteremos ambos como corolários de uma bela unificação recente devida a Bowler e Carmesin: o **//Teorema da Embalagem-Cobertura//**.
  • grafos/arboricitypacking.1684192235.txt.gz
  • Última modificação: 2023/05/15 20:10
  • por 127.0.0.1