Grafos Hamiltonianos e Eulerianos Exercícios Resolvidos sobre Ciclos e Árvores

Qual é o número mínimo de arestas possível num grafo com 9 vértices que contém um ciclo Hamiltoniano mas não contém nem um ciclo Euleriano nem um caminho Euleriano Resposta Assinale as afirmaçãoões verdadeiras sobre ÁRVORES Escolha uma ou mais O número de arestas de uma árvore é uma unidade menor que seu número de vértices Toda árvore tem vértice de grau 2 Toda árvore tem vértice de grau 1 Uma árvore é um grafo conexo sem ciclos Entre qualquer par de vértices distintos de uma árvore existe um único caminho O número de vértices de uma árvore é uma unidade menor que seu número de arestas Uma sequência d1 d2 dk é dita uma possível sequência para uma árvore se existe uma árvore com aquela sequência de graus Por exemplo 3 1 1 1 e 1 1 são possíveis sequências para uma árvore mas as sequências 4 3 1 1 1 e 6 1 1 não são Quais das seguintes sequências são possíveis sequências para uma árvore Escolha uma ou mais 4 4 1 1 1 1 1 1 2 2 2 2 1 1 3 3 3 1 1 1 1 1 5 3 1 1 1 1 5 4 3 2 1 1 1 1 2 2 1 1 1 1 Considere o grafo com pesos G com o seguinte matriz de adjacência A B C D E F A 0 3 0 1 0 5 B 3 0 2 0 6 0 C 0 2 0 3 0 0 D 1 0 3 0 0 0 E 0 6 0 0 0 2 F 5 0 0 0 2 0 Aplique o algoritmo do carteiro Qual é a mínima distância de um ciclo que passa por todas as arestas do grafo Resposta Suponha que G é um grafo simples sem arestas múltiplas com as seguintes propriedades i G possui 9 vértices ii G contém um ciclo Euleriano iii Existem três números distintos d d e d tal que três vértices tem grau d três vértices tem grau d e três vértices tem grau d Quantos vértices tem grau entre 3 e 7 Resposta