Prove ou dê um contraexemplo:
1. (1,0 pts) Todo grafo tem quantidade par de vértices com grau ı́mpar.
2. (1,0 pts) Todo grafo conexo tem uma árv...

Question

Prove ou dê um contraexemplo:1. (1,0 pts) Todo grafo tem quantidade par de vértices com grau ı́mpar.2. (1,0 pts) Todo grafo conexo tem uma árvore geradora3. (1,0 pts) Toda árvore é um grafo bipartido1. Todo grafo tem quantidade par de vértices com grau ı́mpar.2. Todo grafo conexo tem uma árvore geradora.3. Toda árvore é um grafo bipartido.

Ed · Answer

1. A afirmação é falsa. Um contraexemplo é o grafo K3, que possui 3 vértices e todos com grau ímpar.
2. A afirmação é verdadeira. Todo grafo conexo possui pelo menos uma árvore geradora.
3. A afirmação é verdadeira. Toda árvore é um grafo bipartido, pois não possui ciclos ímpares.

Prove ou dê um contraexemplo: 1. (1,0 pts) Todo grafo tem quantidade par de vértices com grau ı́mpar. 2. (1,0 pts) Todo grafo conexo tem uma árv...

Grafos

Outros

Essa pergunta também está no material:

prova02-Parente-2023.2

Grafos • Universidade Federal da BahiaUniversidade Federal da Bahia

💡 1 Resposta

✏️ Responder

Outros materiais

Perguntas relacionadas

Prove ou dê um contraexemplo: 1. (1,0 pts) Todo grafo tem quantidade par de vértices com grau ı́mpar. 1. Prove ou dê um contraexemplo: Sabemos q...

Prove ou dê um contraexemplo: 2. (1,0 pts) Todo grafo conexo tem uma árvore geradora 2. Prove ou dê um contraexemplo: Como G é conexo, basta pe...

Prove os seguintes: 1. (1,0 pts) Se G é um grafo plano, então ∑f∈F (G)gr(f) = 2|E(G)| 2. (1,5 pts) Se G é um grafo planar simples conexo com n ≥...

Seja T uma árvore com n ≥ 2 vértices. Prove as seguintes afirmações: 1. (1,0 pts) T tem pelo menos 2 (duas) folhas 2. (2,0 pts) Para k ∈ N, se...

Outros materiais