Grafos

DCC111 – Matemática Discreta

UFMG/ICEx/DCC

Lista de Exercícios 9: Soluções
Grafos
2o Semestre de 2015

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