Condição necessária e suficiente para uma árvore de abrangência mínima exclusiva

8

Este é um problema de exercício (Ex.3) da excelente nota de aula de Jeff Erickson. Aula 20: Árvores abrangentes mínimas [Fa'13] .

Prove que um gráfico com aresta ponderada tem uma árvore de abrangência mínima exclusiva se e somente se as seguintes condições forem válidasG

  • Para qualquer partição dos vértices de em dois subconjuntos, a borda de peso mínimo com um ponto de extremidade em cada subconjunto é única.G

  • A margem de peso máximo em qualquer ciclo de é única.G

Considere o " direção" ea seguinte gráfico .⇒G

mst

G tem um MST exclusivo. No entanto, para a partição e , a borda de cruzamento de peso mínimo não é exclusiva.{UMA}{B,C}

Eu entendi errado alguns pontos? Ou, se houver falhas no teorema, como podemos corrigi-lo?

graph-theory spanning-trees hengxin
fonte
3
Sim, isso parece ser um erro. Tente descobrir qual versão do exercício está correta. Por exemplo, parece que a segunda condição é realmente necessária.
Yuval Filmus
2
A menos que eu entenda mal, a segunda condição também não é necessária. Considere o gráfico {(A, B, 1), (A, C, 1), (A, D, 1), (B, D, 10), (D, C, 10)}. Ele também possui uma árvore de abrangência mínima composta de arestas conectadas a A. Mas há um ciclo com 2 arestas de peso máximo (e a primeira condição também não é atendida). CC @YuvalFilmus
babou
@jeffe, o que você acha? ;)
Luke Mathieson
Eu acho que o segundo deveria estar em "em qualquer ciclo sem corda " (portanto, um ciclo mínimo no sentido de que não inclui os menores como subgráficos induzidos). A primeira condição parece significativamente errada. Por exemplo, pegueG qualquer árvore onde todos os pesos das arestas estejam 1, então Gpossui um MST exclusivo (em si), mas qualquer partição com mais de uma borda cruzada tem várias bordas com peso mínimo.
Luke Mathieson
1
Opa! Sim, isso é um bug. (Nota para si mesmo: altere todas as instâncias de "Prove" para "Prove or
Disprove

Respostas:

0

Responda a minha própria pergunta simplesmente copiando o comentário feito por @JeffE, o autor da nota da palestra:

Opa! Sim, isso é um bug. (Observação para si mesmo: altere todas as instâncias de "Prove" para "Prove or refut".) - JeffE

hengxin
fonte