A árvore mínima de abrangência não terá apenas as bordas especificadas pela propriedade Cycle?[duplicado]

Question

.

Esta pergunta já tem uma resposta aqui :

Quais bordas não estão em nenhum MST? (1 resposta)

fechado 4 meses atrás .

Acabei de começar a entender as "árvores mínimas de abrangência" (MSTS) e deu a propriedade do ciclo. Estou me referindo ao livro - Design Algoritmo por Jon Kleinberg e Eva Tardos. A declaração da propriedade como escrita no livro é:

.

Suponha que todos os custos de borda sejam distintos. Seja c qualquer ciclo em g, e deixe a borda e= (v, w) ser a borda mais cara pertencente a C. Então e não pertence a nenhuma árvore mínima de abrangência.

Agora minha dúvida é: são as bordas de um gráfico (gráfico não direcionado com bordas com pesos positivos distintos) que não satisfazem a propriedade do ciclo os únicos que não estão presentes no mst ou haverá outras bordas que Não pertence ao MST e não são cobertos por esta propriedade?

Eu sou incapaz de inventar uma prova para argumentar se tais arestas existem ou não. Alguns podem dar uma prova para isso?

Answer 1

Vamos dizer que uma borda $ e $ em $ g $ é ruim < / forte> se existe um ciclo $ g $ em que $ e $ tem peso máximo.

Definir $ {\ cal b}={e ~ | ~ e $ é Bad na matemática $ g \} $ para ser a coleção de todas as bordas ruins.

Sua pergunta é se o gráfico $ (g - {\ cal B}) $ o mest de $ g $ (assumindo que todos os pesos de borda são distintos). A resposta é sim!

Para provar isso, basta mostrar que $ (g - {\ cal b}) $ é acyclic.

Assuma, em contrário, que $ (g - {\ cal B}) $ contém um ciclo, digamos $ c $ . Observe que $ c $ é um ciclo $ g $ também. Deixe $ E ^ * $ a borda do peso máximo no ciclo $ c $ . Agora $ e ^ * $ é um bad borda, por isso não deve ter sido é gráfico $ (G - {\ cal B}) $ no primeiro lugar. Isso mostra que $ (g - {\ cal B}) $ é acyclic.

Answer 2

desculpe se eu não entendi sua pergunta, mas o que eu acho que você quis perguntar é, seja possível que uma vantagem não esteja em um mst se esta borda não estiver em um ciclo.

Aqui está a minha resposta.

Deixe-nos supor que temos uma borda (u, v) em um graph g, que não faz parte de um ciclo.Isso significaria que não há caminho de você a v que não é a borda (u, v). Se a borda (u, v) não estivesse no MST, isso significaria que não há caminho de você a v neste mst, o que significa que o MST seria desconectado e, portanto, não é um MST. Portanto, se uma borda não faz parte de um ciclo, deve estar no MST do gráfico.