Digamos que temos um gráfico $ G $. Escolhemos uma aresta dele (qualquer aresta). Sempre haverá uma árvore abrangente que contém essa mesma aresta?
Acho que a resposta é sim, porque não importa o que façamos, sempre podemos criar uma árvore de abrangência para que a própria aresta que escolhemos seja incluída. Claro, uma prova mais formal seria necessário?
Comentários
- Você ' não escreveu nem mesmo uma prova informal: essencialmente, você ' disse " Acho que a resposta é sim, porque sim. "
Resposta
Observe que o gráfico inicial $ G $ precisa ser conectado ou não tem árvore de abrangência. (Embora o mesmo argumento aplicado a cada componente mostre que qualquer gráfico tem uma floresta de abrangência contendo qualquer aresta escolhida.)
Seja $ G = (V, E) $ seja um gráfico conectado, deixe $ T $ seja qualquer subárvore de extensão e seja $ e $ qualquer aresta em $ E $. Afirmamos que há uma árvore de abrangência que inclui $ e $. Se $ e \ em T $, estamos prontos. Caso contrário, $ T + e $ contém um ciclo. Esse ciclo contém necessariamente pelo menos uma aresta $ e “\ neq e $ (na verdade, contém pelo menos duas). $ T + ee” $ é uma árvore geradora que contém $ e $.
Você deve provar a si mesmo que $ T + ee “$ é realmente uma árvore geradora.
Resposta
Adicionar uma aresta a uma árvore causa um ciclo único. Você pode remover qualquer aresta deste ciclo (diferente da que adicionou) para recuperar uma árvore. Esta nova árvore contém a aresta que foi adicionada.
Comentários
- Isso ' é exatamente o que eu disse!
- Sim, mas Eu disse com menos palavras. 🙂
- Porque minhas sete sentenças realmente precisam ser resumidas em três. Temos cinco mil perguntas não respondidas no site – seria muito melhor responder algumas delas do que postar respostas duplicadas para perguntas que não ' precisam delas.
- Então leia a resposta existente s antes de postar o seu próprio.
- Nada é realmente obrigatório – como poderíamos aplicá-lo, afinal? Mas geralmente se espera que as respostas contribuam com algo novo, e como você pode saber se ' está fazendo isso se não ' não sabe o que ' já foi dito? Ter várias respostas que dizem a mesma coisa apenas confunde a página, embora, obviamente, ' não seja grande coisa com apenas duas. Postar uma resposta curta e resumida pode definitivamente ser valioso quando as respostas existentes são longas; Eu apenas não ' acho que não acrescenta nada neste caso específico.