*1. Mostre que um grafo simples é uma árvore se e somente se ele não contiver nenhum ciclo simples e a adição de uma aresta que liga dois vértices não adjacentes produzir um novo grafo que tem exatamente um ciclo simples (no qual ciclos que contêm as mesmas arestas não são considerados diferentes).
Passo 1
O enunciado pede para mostrar a equivalência entre duas propriedades de um grafo simples
:
-
é uma árvore (ou seja, é conexo e acíclico). -
não contém nenhum ciclo simples, e além disso, para quaisquer dois vértices não adjacentes , ao adicionar a aresta obtém-se um grafo que tem exatamente um ciclo simples.
Conteúdo principal: teoria de grafos – definição de árvore, ciclos simples, conectividade, caminho simples único em árvore e propriedade de minimalidade de arestas.
Passo 2
(“
”) Suponha que
é árvore.
- Por definição de árvore,
é acíclico, logo não contém ciclo simples. - Em toda árvore existe exatamente um caminho simples entre quaisquer dois vértices
e . Se e não forem adjacentes, esse caminho simples tem comprimento . Ao inserir a aresta , fechamos esse único caminho, formando exatamente um ciclo simples (aquele que segue o caminho pré-existente de a e retorna por ). Não há como formar outro ciclo, pois antes da adição não havia ciclos e só incluímos uma aresta.
Passo 3
(“
”) Agora suponha que
não contém ciclo simples e que, para quaisquer vértices não adjacentes
, ao adicionar a aresta
surge exatamente um ciclo simples.
- Primeiro, mostremos que
é conexo. Se fosse desconexo, haveria dois vértices em componentes distintas; como não há caminho entre eles, ao inserir não se formaria ciclo algum, contradizendo a hipótese de “exatamente um ciclo”. Logo, é conexo. - Já assumimos que não há ciclo simples em
.
Conectividade + ausência de ciclos é a definição de árvore. Portantoé árvore.
Resposta
Concluímos que um grafo simples
é árvore se e somente se não tiver ciclo simples e a adição de qualquer aresta ligando dois vértices não adjacentes cria exatamente um ciclo simples.