gabarito_prova01_2023-2

Prévia do material em texto

R
as
cu
nh
o
UFBA
INSTITUTO DE COMPUTAÇÃO
MATA53 – Teoria dos Grafos – 2023.2
Professor: Roberto Freitas Parente
Gabarito – Prova 01
Questão 1. Defina de forma precisa os seguintes conceitos:
a) Grau e vizinhança de um vértice.
b) Grafo completo com n vértices.
c) Grafo bipartido com bipartição (X,Y ).
d) Componentes de um grafo G.
e) Floresta e Árvore com n vértices.
Utilizando as definições conhecidas, responda (de acordo com as instruções).
f) Para qualquer n podemos afirmar que Kn é um grafo euleriado?
g) Apresente o seguinte produto cartesiano: □
Resposta. Sejam as seguinte respostas:
a) Vizinhança de vértice v ∈ V (G) é definida por NG(v) = {u : vu ∈ E(G)}. Grau de vértice v ∈ V (G) é
definido por dG(v) = |NG(v)|.
b) Definimos o grafo completo com n vértice como Kn = (V,E), onde E = {xy : x ∈ v(G), y ∈ V (G), x ̸= y}
c) Um grafo bipartido G com bipartição (X,Y ) é tal que X,Y ⊆ V (G) onde X ∩ Y = ∅, X ∪ Y = V (G) e
G[X] e G[Y ] são conjuntos independentes.
d) As componentes de um grafo G são subgrafos maximais conexos de G.
e) Floresta é um grafo aćıclico. Árvores são grafos conexos e aćıclicos.
f) Não, pois um grafo é euleriano se, e somente se, todos os vértices têm grau par e existe no máximo uma
componente não trivial. Desta forma, Kn é euleriano apenas para n ı́mpares.
g)
Questão 2. Sejam P e Q caminhos de comprimentos máximos em um grafo conexo G com |P | ≥ |Q|. Prove
que P e Q tem um vértice em comum
Resposta.
1
R
as
cu
nh
o
Questão 3. Prove que um grafo é conexo se, e somente se, para toda partição dos vértices em dois conjuntos
não vazios existe uma aresta com cada vértice em cada conjunto.
Resposta.
Questão 4. Uma das versões do Teorema de Euler afima o seguinte:
• Seja G um grafo conexo. G é Euleriano se, e somente se, todo vértice tem grau par.
Avalie a “volta” (⇐) da prova abaixo apontando os posśıveis erros ou afirmando se está correta.
Prova por indução. Seja G um grafo conexo onde todos os vértices tem grau par. Como G é conexo, então
temos que todo vértice tem grau diferente de zero e todo vértice tem grau pelo menos 2. Desta forma, sabemos
que todo grafo com grau mı́nimo pelo menos 2 contém um ciclo. Seja C = (v1, v2, . . . , vk, v1) um ciclo de G,
faça G′ = G \ E(C). Ao retirarmos as arestas de um ciclo em G observamos que todo vértice manterá o grau
igual ou o grau será subtráıdo exatamente em 2 unidades. Desta forma, G′ satisfaz as hipóteses do teorema e
temos que G′ é um grafo Euleriano com C ′ = (u1, u2, u3, . . . , up, u1) o Circuito Euleriano de G
′. Por fim, para
mostrar que G é Euleriano basta observamos que existe o seguinte Circuito Euleriano: Seja ui a primeira vez
que v1 aparece em C
′, então teremos o seguinte Circuito Euleriano (u1, u2, . . . , ui, v2, . . . , vk, ui, . . . , up, u1).
Resposta.
Questão 5. Seja v um vértice de corte de um grafo simples G. Prove que G \ v é conexo.
Resposta. Pela definição de vértice de corte, temos que G\v é desconexo. Pela definição de conexidade, temos
que mostrar que para todo par de vértice tem um caminho entre eles. Observe que pela definição de componenete
conexa temos que no complementar de G \ v existirão todas as arestas posśıveis entre as componentes. Desta
forma, se x, y ∈ V (G \ v) estão em componentes distintas, então existirá uma arestas em G \ v. Se x, y estão
na mesma componente e G \ v é desconexo, então existe pelo menos uma outra componenete conexa com um
vértice z e como observado temos que xz, yz ∈ E(G \ v) o que define o caminho xzy.
Questão 6. Seja T uma árvore com n ≥ 2 vértices. Prove as seguintes afirmações:
1. T tem pelo menos 2 (duas) folhas
Resposta. Seja P um (x, y)-caminho maximal em T . Observe que os vértices d(x) = d(y) = 1, pois caso
contrário, pela suposição de maximal, formaŕıamos um ciclo.
2. Para k ∈ N, se ∆(T ) ≥ k, então existem pelo menos k folhas
2