...

Lista de Exercícios 9: Soluções

by user

on
Category: Documents
1

views

Report

Comments

Transcript

Lista de Exercícios 9: Soluções
DCC111 – Matemática Discreta
UFMG/ICEx/DCC
Lista de Exercícios 9: Soluções
Grafos
1o Semestre de 2016
Ciências Exatas & Engenharias
1. O grafo de interseção de uma coleção de conjuntos A1 , A2 , . . . , An é o grafo que tem um vértice para cada
um dos conjuntos da coleção e tem uma aresta conectando os vértices se esses conjuntos têm uma interseção
não vazia. Construa o grafo de interseção para as seguintes coleções de conjuntos.
(a)
A1
A2
A3
A4
A5
=
=
=
=
=
{0, 2, 4, 6, 8}
{0, 1, 2, 3, 4}
{1, 3, 5, 7, 9}
{5, 6, 7, 8, 9}
{0, 1, 8, 9}
Resposta:
A1
A5
A2
A4
A3
(b)
A1
A2
A3
A4
A5
{. . . , −4, −3, −2, −1, 0}
{. . . , −2, −1, 0, 1, 2, . . .}
{. . . , −6, −4, −2, 0, 2, 4, 6, . . .}
{. . . , −5, −3, −1, 1, 3, 5, . . .}
{. . . , −6, −3, 0, 3, 6, . . .}
=
=
=
=
=
Resposta:
A1
A5
A2
A4
A3
(c)
A1
A2
A3
A4
A5
A6
{x|x < 0}
{x| − 1 < x < 0}
{x|0 < x < 1}
{x| − 1 < x < 1}
{x|x > −1}
R
=
=
=
=
=
=
1
Resposta:
A1
A2
A3
A6
A5
A4
2. Pode haver um grafo simples com 15 vértices, cada um com grau 5?
Resposta:
Não. O grau desse suposto grafo seria 15 × 5 = 75, que é um número ímpar. Sabe-se que o grau de qualquer
grafo deve ser um número par.
3. Determine se cada um dos grafos abaixo é bipartido.
a
b
e
(a)
c
d
b
c
a
e
b
(b)
d
c
a
d
f
b
(c)
e
c
a
d
f
b
(d)
e
c
a
(e)
d
f
e
Resposta:
2
(a) Sim. Seja V = {a, b, c, d} e W = {e}. Não existe nenhuma aresta entre vértices de V e entre vértices
de W . Toda aresta conecta algum vértice de V a algum vértice de W .
a
b
a
b
e
e
c
d
c
Grafo original
d
Grafo bipartido
(b) Sim. Seja V = {a, c} e W = {b, d, e}. Não existe nenhuma aresta entre vértices de V e entre vértices
de W . Toda aresta conecta algum vértice de V a algum vértice de W .
b
b
c
a
e
c
a
e
d
Grafo original
d
Grafo bipartido
(c) Não. Se a ∈ V então {b, d, e} ⊆ W e c ∈ V . O vértice f está conectado ao vértice b ∈ W e ao c ∈ V .
Assim, não é possível associar f nem a V e nem a W o que faz com que o grafo não seja bipartido.
b
c
a
b
d
f
a
d
e
f
Grafo original
c
e
Grafo não é bipartido
(d) Sim. Seja V = {a, b, d, e} e W = {c, f }. Não existe nenhuma aresta entre vértices de V e entre vértices
de W . Toda aresta conecta algum vértice de V a algum vértice de W .
b
c
a
b
d
f
a
d
e
Grafo original
c
f
e
Grafo bipartido
(e) Não. Se a ∈ V então {b, f } ⊆ W . O vértice b está conectado, além do vértice a, aos vértices d e e, que
por sua vez estão conectados entre si. Ou seja, os vértices d e e devem pertencer a diferentes conjuntos
e, ao mesmo tempo, não podem pertencer ao conjunto de b. Assim, o grafo não é bipartido.
3
b
c
a
b
d
a
d
e
f
Grafo original
c
f
e
Grafo não é bipartido
4. Quantos vértices e quantas arestas têm os grafos abaixo?
(a) Kn (grafo completo)
Resposta:
|V | = n
|E| = n(n−1)
. Existem n vértices, cada um com grau n − 1. Assim, a quantidade de arestas é dada
2
pela metade desse produto.
(b) Km,n (grafo bipartido completo)
Resposta:
|V | = m + n
|E| = m × n
(c) Cn (grafo ciclo)
Resposta:
|V | = n
|E| = n
(d) Qn (grafo cubo)
Resposta:
|V | = 2n
n
|E| = 2 2×n . Existem 2n vértices, cada um com grau n. Assim, a quantidade de arestas é dada pela
metade desse produto.
(e) Wn (grafo roda)
Resposta:
|V | = n + 1
|E| = 2n
5. Quantas arestas tem um grafo com vértices de graus 5, 2, 2, 2, 2, 1? Desenhe um possível grafo.
Resposta:
O grafo possui seis vértices e tem um grau total de 5 + 2 + 2 + 2 + 2 + 1 = 14. Isso significa que existem
sete arestas.
4
6. Existe um grafo simples com cinco vértices dos seguintes graus? Se existir, desenhe um possível grafo.
(a) 3, 3, 3, 3, 2
Resposta:
O grafo tem um grau total de 3 + 3 + 3 + 3 + 2 = 14. Isso significa que existem sete arestas.
(b) 1, 2, 3, 4, 5
Resposta:
O grafo tem um grau total de 1 + 2 + 3 + 4 + 5 = 15. Isso não é possível.
(c) 1, 2, 3, 4, 4
Resposta:
O grafo tem um grau total de 1 + 2 + 3 + 4 + 4 = 14. No entanto, como existem dois vértices com grau 4,
todos os vértices devem ter pelo menos grau 2, como mostrado na figura abaixo. Como supostamente
existe um vértice com grau 1, não é possível existir tal grafo.
(d) 3, 4, 3, 4, 3
Resposta:
O grafo tem um grau total de 3 + 4 + 3 + 4 + 3 = 17. Isso não é possível.
(e) 0, 1, 2, 2, 3
Resposta:
O grafo tem um grau total de 0 + 1 + 2 + 2 + 3 = 8. Isso significa que existem quatro arestas.
(f) 1, 1, 1, 1, 1
Resposta:
O grafo tem um grau total de 1 + 1 + 1 + 1 + 1 = 5. Isso não é possível.
7. Quantos subgrafos com pelo menos um vértice tem K3 ?
Resposta:
São os subgrafos com um, dois e três vértices:
5
• Existem três subgrafos com um vértice e nenhuma aresta;
• Existem C(3, 2) = 3 possibilidades de escolher subgrafos com dois vértices. Para cada possibilidade,
podemos incluir ou não a aresta, i.e., 3 × 2 = 6 subgrafos com dois vértices;
• Com três vértices, temos 23 = 8 possibilidade de incluir ou não cada aresta.
Assim, a quantidade total de subgrafos com pelo menos um vértice é a soma de 3 + 6 + 8 = 17.
A figura abaixo mostra todos esses subgrafos.
v3
v1
v2
v1
v2
v1
v2
v3
v3
v2
v2
v1
v2
v1
v2
v1
v1
v2
v1
v2
v1
v2
8. Desenhe todos os subgrafos do grafo abaixo.
a
b
c
d
Resposta:
6
v2
v3
v3
v3
v2
v3
v3
v3
v3
v1
v3
v1
v3
v1
v3
v1
v2
b
a
a
d
c
a
b
a
a
c
c
b
a
b
a
a
a
d
c
d
c
b
a
b
a
d
c
c
a
d
b
c
b
b
d
a
b
c
b
a
d
b
d
b
a
d
c
d
c
d
c
d
c
d
b
a
b
a
b
a
b
a
b
c
d
c
d
c
d
c
d
c
d
a
b
a
b
a
b
a
b
c
d
c
d
c
d
c
d
a
a
a
a
9. Para que valores de n os grafos abaixo são regulares?
(a) Kn
Resposta:
O grafo completo Kn é regular para todos os valores de n ≥ 1, já que o grau de cada vértice é n − 1.
(b) Cn
Resposta:
O grafo ciclo Cn é regular para todos os valores de n ≥ 3, já que o grau de cada vértice é sempre 2.
(c) Wn
Resposta:
No grafo roda, o grau do vértice do centro é sempre n e o grau dos vértices no ciclo é sempre 3. Assim,
o grafo roda Wn é regular apenas para n = 3. Observe que W3 é o mesmo que K4 .
(d) Qn
Resposta:
O grafo ciclo Qn é regular para todos os valores de n ≥ 0, já que o grau de cada vértice é sempre n.
Observe que Q0 é o grafo com um vértice.
10. Quantos vértices tem um grafo regular de grau 4 com 10 arestas?
7
Resposta:
Um grafo regular de grau 4 com n vértices possui, pelo Teorema do Aperto de Mãos, 4n/2 = 2n arestas.
Como existem 10 arestas, temos que 2n = 10, i.e., n = 5 e existem cinco vértices. O grafo completo K5
possui cinco vértices, todos com grau 4 e 10 arestas.
11. O grafo complementar G de um grafo simples G tem os mesmos vértices de G. Dois vértices são adjacentes
em G se, e somente se, eles não são adjacentes em G. Determine os seguintes grafos.
(a) Kn
Resposta:
O complemento do grafo completo é o grafo com nenhuma aresta.
(b) Km,n
Resposta:
No grafo bipartido completo Km,n , existe uma aresta conectando vértices das “duas partes” e nenhuma
aresta entre cada parte. No grafo complemento, existe uma aresta entre cada vértice de cada parte
levando aos dois subgrafos Km e Kn .
(c) Cn
Resposta:
O grafo complemento de Cn é “quase” o grafo Kn , i.e., é o grafo Kn sem as arestas presentes em Cn .
(d) Qn
Resposta:
É o grafo onde existe uma aresta entre vértices cujos strings diferem em mais de um bit.
12. Se o grafo simples G tem v vértices e e arestas, quantas arestas tem G?
Resposta:
O grafo completo Kv possui C(v,2) = v(v − 1)/2 arestas. O grafo G tem todas as arestas de Kv exceto as
v(v−1)
−
e
arestas.
2
presentes em G. Assim G possui
13. Mostre que se G é um grafo simples com n vértices, então G ∪ G = Kn .
Resposta:
Considere o grafo G ∪ G. Claramente esse grafo possui o conjunto de vértices de G, i.e., possui n vértices.
Sejam dois vértices distintos u e v do grafo G ∪ G. Ou existe uma aresta conectando u a v em G ou em G.
Assim, pela definição de união, vamos ter uma aresta entre cada par de vértices u e v para um grafo com n
vértices, o que leva ao grafo Kn .
14. O grafo reverso de um grafo dirigido G = (V, E), representado por Gr , é o grafo dirigido (V, F ) onde
(u, v) ∈ F , se, e somente se, (v, u) ∈ E. Desenhe os grafos Gr correspondentes aos seguintes grafos:
(a)
c
b
a
e
a
e
d
(b)
b
c
d
8
(c)
a
b
e
d
c
f
Resposta:
(a)
c
b
a
e
c
b
d
a
e
Grafo original
d
Grafo reverso
(b)
e
a
b
b
d
c
e
a
d
c
Grafo original
Grafo reverso
(c)
a
b
a
c
f
b
c
f
e
e
d
Grafo original
d
Grafo reverso
15. Seja G um grafo dirigido. Mostre que G = Gr se, e somente se, a relação associada com G é simétrica.
Resposta:
Pela definição de grafo reverso, existe uma aresta de v para u em Gr se, e somente se, existe uma aresta de
u para v em G. Mas essa é exatamente a definição da propriedade de simetria. Assim, os grafos G e Gr
serão idênticos se, e somente se, eles tiverem a propriedade da simetria.
16. Represente a matriz de adjacência do grafo Q3 .
9
Resposta:
11
0
11
0
0
1
1
0
0
0
0
1
10
1
1
0
0
1
0
0
1
0
10
0
1
0
0
1
0
1
0
0
1
01
0
0
1
1
0
1
0
0
0
01
00
1
000
001
010
011
100
101
110
110
00
0
O grafo Q3 possui 23 = 8 vértices que podem ser rotulados pelos números binários de 0 a 7. A matriz de
adjacência correspondente é:
1
0
0
0
0
1
1
0
0
1
0
0
1
0
0
1
0
0
1
0
1
0
0
1
0
0
0
1
0
1
1
0
17. Seja uma matriz simétrica quadrada formada apenas por 0’s e 1’s que tem apenas 0’s na diagonal principal.
Essa matriz pode representar a matriz de adjacência de um grafo simples?
Resposta:
Um grafo simples é um grafo que não possui laços nem arestas paralelas. Se um grafo possuir um laço,
haverá uma entrada diferente de zero na diagonal principal. Se um grafo possuir arestas paralelas entre
os vértices u e v, haverá um valor maior que 1 nas entradas [u, v] e [v, u] da matriz de adjacência. Como
nenhuma dessas duas condições ocorre, essa matriz de adjacência representa um grafo simples.
18. O que representa a soma das entradas de uma coluna de uma matriz de adjacência de um grafo não dirigido?
E de um grafo dirigido?
Resposta:
Em um grafo não dirigido, cada aresta incidente ao vértice v contribui com um na v-ésima coluna. Assim, a
soma das entradas nessa coluna representa o número de arestas incidentes a v. Como uma aresta incidente
a um vértice v contribui com um para o grau do vértice (dois se for uma aresta laço), a soma dessa coluna
representa o grau do vértice v, se não houver laços e mais um para cada laço existente.
Em um grafo dirigido, cada aresta incidente ao vértice v contribui com um na v-ésima coluna, i.e., v é o
nó terminal da aresta dirigida. Assim, a soma das entradas nessa coluna representa o número de arestas
incidentes a v. Como uma aresta incidente a um vértice v contribui com um para o grau de entrada do
vértice (in-degree), a soma dessa coluna representa o grau de entrada do vértice v.
19. O que representa a soma das entradas de uma coluna de uma matriz de incidência de um grafo não dirigido?
Resposta:
A matriz de incidência de um grafo é a matriz M = (mij ) de tamanho n × m (n vértices e m arestas) sobre
o conjunto dos inteiros não negativos tal que a entrada mij = 1 quando a aresta ej é incidente a vi e 0 caso
contrário.
Como cada coluna representa uma aresta, a soma da coluna vale 2, quando a aresta incide a dois vértices,
ou 1, quando a aresta é um laço.
20. Os pares de grafos abaixo são isomorfos?
(a)
u1
u2
u3
u5
u4
v1
v2
v4
v3
u6
u7
v5
v6
v7
10
u8
v8
Resposta:
Não. No primeiro grafo, os vértices u3 e u6 , que têm grau 3, são adjacentes a um vértice em comum
(u5 ). No segundo grafo, os vértices v2 e v6 , que têm grau 3, não são adjacentes a um vértice em
comum.
(b)
v2
u2
u9
v1
u1
v3
v8
u3
v9
u6
u5
v10
u8
u10
v6
u7
u4
v7
v4
v5
Resposta:
Os grafos são isomorfos. Um possível isomorfismo é f (u1 ) = v1 , f (u2 ) = v9 , f (u3 ) = v4 , f (u4 ) = v3 ,
f (u5 ) = v2 , f (u6 ) = v8 , f (u7 ) = v7 , f (u8 ) = v5 , f (u9 ) = v10 e f (u10 ) = v6 .
21. Mostre que o isomorfismo de grafos simples é uma relação de equivalência.
Resposta:
Devemos mostrar que o isomorfismo gera uma relação que é reflexiva, simétrica e transitiva. A relação é
reflexiva já que a função identidade de um grafo para ele próprio provê o isomorfismo (correspondência
um-para-um). A relação é simétrica já que se f é uma correspondência um-para-um que faz com que o
grafo G1 seja isomorfo a G2 , então f −1 é uma correspondência um-para-um que faz com que o grafo G2
seja isomorfo a G1 . A relação é transitiva já que se f é uma correspondência um-para-um que faz com que
o grafo G1 seja isomorfo a G2 e g é uma correspondência um-para-um que faz com que o grafo G2 seja
isomorfo a G3 , então g ◦ f é uma correspondência um-para-um que faz com que o grafo G1 seja isomorfo a
G3 .
22. Mostre que os vértices de um grafo bipartido com dois ou mais vértices podem ser ordenados de tal forma
que a sua matriz de adjacência tem a forma
0 A
B 0
onde as quatro entradas acima são blocos retangulares.
Resposta:
Sejam V1 e V2 duas partes de tamanhos m e n, respectivamente. Podemos numerar todos os vértices de
V1 antes dos vértices de V2 . A matriz de adjacência é quadrada de tamanho (m + n)2 . Como não existem
arestas entre vértices de V1 , as primeiras m linhas e as primeiras m colunas devem ter 0. O mesmo raciocínio
vale para V2 e as últimas n linhas e n colunas devem ter 0.
23. Um grafo simples G é dito ser auto-complementar se G e G são isomorfos. Apresente um grafo simples
auto-complementar com cinco vértices.
Resposta:
Um grafo simples com cinco vértices pode ter no máximo 10 arestas (K5 ). Consequentemente para G e G
serem isomorfos os dois devem ter o mesmo número de arestas, ou seja, cada um deve ter cinco arestas.
Seja G o primeiro grafo abaixo. O segundo é o grafo G correspondente. O terceiro é novamente o grafo G
desenhado da “forma” de G.
11
c
a
b
d
e
1
4
4
5
3
2
5
3
1
2
24. Para que inteiros n o grafo Cn é auto-complementar?
Resposta:
Se Cn for auto-complementar, então Cn deve ter o mesmo número de arestas que seu complemento. Sabemos
que Cn possui n arestas e que o complemento deve ter uma quantidade de arestas idêntica, que pode ser
expressa pela quantidadede arestas
de Kn −n (quantidade de arestas do grafo completo menos a quantidade
de arestas de Cn ), i.e., n n(n−1)
− n. Se resolvermos essa equação, temos que n = 5. Isso significa que C5 é
2
o único grafo Cn que pode ser auto-complementar já que o número de arestas de C5 e de seu complemento
é o mesmo. Se desenharmos C5 e seu complemento vemos que os dois grafos são isomorfos.
v1
v1
e1
e5
e1
v2
v5
v3
e3
v4
e4
e2
e4
e5
e2
v4
e3
v3
v5
v2
25. Seja G = (V, E) um grafo simples. Seja R uma relação em V formada por pares de vértices (u, v) tal que
existe um trajeto (path) de u para v ou tal que u = v. Mostre que R é uma relação de equivalência.
Resposta:
Os vértices u e v estão relacionados se, e somente se, ambos estão no mesmo componente conexo. A relação
R é obviamente reflexiva. A relação é simétrica já que se u está no mesmo componente conexo de v então
v está no mesmo componente conexo de u. A relação R é transitiva já que se u está no mesmo componente
conexo de v e v está no mesmo componente conexo de w então u está no mesmo componente conexo de w.
26. Apresente um grafo que tenha um circuito Euleriano e um circuito Hamiltoniano mas que não sejam idênticos.
Resposta:
Seja o grafo K5 . Um circuito euleriano está mostrado no grafo do meio abaixo e um circuito hamiltoniano
no grafo à direita. Os números associados às arestas indicam uma possível ordem de fazer o caminhamento.
12
b
b
b
a
c
1
6
a
9 2
e
c
7 3
5
d
e
10
4
e
d
a
c
5 8
2
1
3
4
d
27. Um grafo possui oito vértices e seis arestas? Esse grafo é conexo? Justifique a resposta.
Resposta:
Não. O número mínimo de arestas para o grafo ser conexo é a quantidade de vértices menos um. Neste
caso, seriam necessárias pelo menos sete arestas para o grafo ser conexo.
28. Nos grafos abaixo, assuma que cada vértice possui um identificador único vi , i ≥ 1. Cada variável usada é
um número inteiro positivo maior ou igual a 1 ou um outro valor específico, conforme o caso. Para cada
letra, diga quantas soluções distintas podem ser obtidas.
(a) Árvores geradoras de um grafo Cn , n ≥ 3.
Resposta:
Grafo Cn é o grafo ciclo com n vértices. Se qualquer uma das n arestas for removida, então teremos uma
árvore geradora. Assim, existem exatamente n árvores geradoras distintas, cada uma correspondente
a remoção de uma das n arestas.
(b) Circuitos Hamiltonianos de um grafo Kn , n ≥ 3, começando num vértice vi , 1 ≤ i ≤ n.
Resposta:
Grafo Kn é o grafo completo com n vértices. Começando num vértice vi , 1 ≤ i ≤ n temos n − 1
vértices como segunda opção. Como terceira opção temos n − 2 vértices e assim sucessivamente até
chegarmos ao último vértice que tem uma aresta para o vértice vi , formando o circuito Hamiltoniano.
A quantidade de circuitos distintos começando num vértice vi é dada por:
(n − 1) × (n − 2) × . . . × 1 = (n − 1)!
(c) Circuitos Eulerianos de um grafo Km,m , m ≥ 2, m = 2a e começando num vértice vi , 1 ≤ i ≤ 2m.
Grafo Km,m , m ≥ 2, m = 2a é o grafo bipartido completo sendo que m é um número par. Os grafos
bipartidos completos que podemos ter são da forma K2,2 , K4,4 , K6,6 , . . .. Ou seja, cada vértice está
conectado a exatamente m outros vértices. Como m é par, o grau de cada vértice é par e, assim, é
possível haver circuitos Eulerianos.
Resposta:
Começando num vértice vi , 1 ≤ i ≤ 2m temos m opções de arestas para percorrer e chegar a um vértice.
Para esse segundo vértice temos m − 1 opções de arestas para percorrer e chegar a um vértice. Para
esse terceiro vértice temos novamente m − 1 opções de arestas para percorrer e chegar a um vértice,
considerando que desejamos maximizar a quantidade de circuitos. Esse processo é repetido exatamente
2m − 1 vezes, quando retornaremos ao vértice vi , ou seja, completamos a primeira parte do percurso.
Nesse momento, para o vértice vi temos exatamente m − 2 opções de arestas e chegar a um vértice.
Para esse próximo vértice temos m − 3 opções de arestas e, novamente, esse processo é repetido 2m − 1
vezes, quando a segunda parte do percurso é completada. Esse processo é repetido até que não haja
mais arestas a serem percorridas, terminando no vértice vi . Assim, a quantidade de circuitos Eulerianos
distintos começando num vértice vi é dada por:
m
m · (m − 1)
2m−1
· (m − 2) · (m − 3)
2m−1
2m−1
· ...2 · 1
=
2
Y
i=1
29. Determine os componentes fortemente conexos de cada grafo dirigido abaixo.
(a)
13
2i · (2i − 1)2m−1
a
b
e
d
c
Resposta:
(a) H1 : V1 = {a, b, e}
(b) H2 : V2 = {c}
(c) H3 : V3 = {d}
(b)
a
b
c
d
i
h
g
f
e
Resposta:
(a) H1 : V1 = {a, b, c, d, f, g, h, i}
(b) H2 : V2 = {e}
30. Seja uma árvore com n vértices.
(a) Quantas arestas têm essa árvore?
Resposta:
Tem n − 1 arestas.
(b) Prove esse resultado por indução matemática.
Resposta:
P (n) : Toda árvore com n vértices tem n − 1 arestas, n ≥ 1.
Prova (por indução matemática):
(a) Passo base: P (n0 ) = P (1): Toda árvore com um vértice tem zero arestas. Este passo é verdadeiro
já que a única aresta que poderia existir seria uma aresta laço e, assim, haveria um ciclo. Como
árvores não possuem ciclos, logo não pode haver nenhuma aresta.
(b) Passo indutivo: se a fórmula é verdadeira para n = k então deve ser verdadeira para n = k + 1,
i.e., P (k) → P (k + 1).
– Suponha que a fórmula seja verdadeira para n = k, i.e., P (k) : Toda árvore com k vértices tem
k − 1 arestas, k ≥ 1. [hipótese indutiva]
– Deve-se mostrar P (k + 1) : Toda árvore com k + 1 vértices tem k arestas, k ≥ 1.
Seja uma árvore com k vértices e k − 1 arestas. Vamos acrescentar um vértice v ? ao grafo que
representa essa árvore. Se esse vértice v ? não for conectado a nenhum vértice da árvore existente,
então teremos uma floresta e não uma árvore. Logo, temos que acrescentar uma aresta para não
termos uma floresta. Essa aresta deve ser incidente a v ? e a algum vértice da árvore va . O
acréscimo dessa aresta mantém a propriedade da árvore (grafo acíclico), já que existe apenas um
único caminho entre v ? e va e, conseqüentemente, com qualquer outro vértice da árvore. Note que
se acrescentarmos uma segunda aresta incidente a v ? e a um outro vértice da árvore passaremos a
14
ter um ciclo, o que deixa de caracterizar uma árvore. Ou seja, não podemos acrescentar mais de
uma aresta incidente a v ? .
Assim, ao acrescentarmos um vértice à árvore com k vértices e k − 1 arestas, passaremos a ter uma
árvore com k + 1 vértices e k arestas.
15
Fly UP