Teoria dos Grafos
Componentes, Conj. Indep., Cliques
Grafo Conexo/Desconexo
Um grafo e conexo se existe um caminho entre qualquer par denos, caso contrario ele e chamado desconexo.
Basta que nao exista um caminho entre um no p e qualquer outrono do grafo para o grafo ser desconexo.
Dois nos estao conectados se existe um caminho entre eles nografo.
u
v
wx
y
u
v
wx
y
p
conexo desconexo
Componentes Conexos
Os componentes conexos de um grafo sao os subgrafos conexosmaximais deste grafo, ou seja, sao os subgrafos conexos que naoestao estritamente contidos em outros subgrafos conexos.
O subgrafo formado pelos vertices u e v juntamente com a aresta(u, v) corresponde a componente conexo?
u
v
wx
y
p
Componentes Conexos
Nao, pois ele esta contido no subgrafo formado pelos nosu, v, w, x, y e arestas (u, v), (v, w), (w, x), (x, y), (y, u) e (u, x).
u
v
wx
y
p
O grafo possui 2 componentes conexos. O primeiro formado pelosnos u, v, w, x, y e arestas (u, v), (v, w), (w, x), (x, y), (y, u), (u, x).E o segundo unicamente formado pelo no p.
Componentes Conexos
Quantos componentes conexos o grafo abaixo possui?
u
vw
x
y
z ts
Dois!
u
w
y
s
vx
z t
Componentes Conexos
Quantos componentes conexos o grafo abaixo possui?
u
vw
x
y
z ts
Dois!
u
w
y
s
vx
z t
Grafo totalmente conexo/desconexo
Um grafo totalmente desconexo tem todos os seus vertices comgrau zero.
u v w
Um grafo completo de n vertices, denotado por Kn, possui acaracterıstica de que todo vertice do grafo e adjacente aos demais.
y
u
v
wx w v
u
x
Quantas arestas um grafo completo (Kn) com n vertices possui?
Ele possui exatamente(n2
)= n(n−1)
2 arestas.
Grafo totalmente conexo/desconexo
Um grafo totalmente desconexo tem todos os seus vertices comgrau zero.
u v w
Um grafo completo de n vertices, denotado por Kn, possui acaracterıstica de que todo vertice do grafo e adjacente aos demais.
y
u
v
wx w v
u
x
Quantas arestas um grafo completo (Kn) com n vertices possui?
Ele possui exatamente(n2
)= n(n−1)
2 arestas.
Grafo totalmente conexo/desconexo
Um grafo totalmente desconexo tem todos os seus vertices comgrau zero.
u v w
Um grafo completo de n vertices, denotado por Kn, possui acaracterıstica de que todo vertice do grafo e adjacente aos demais.
y
u
v
wx w v
u
x
Quantas arestas um grafo completo (Kn) com n vertices possui?
Ele possui exatamente(n2
)= n(n−1)
2 arestas.
Conjunto Independente
Um conjunto independente (maximal) em um grafo e umconjunto de vertices nao adjacentes entre si que nao estaestritamente contido em outros conjuntos independentes.
O tamanho do maior conjunto independente e chamado numerode independencia, denotado por α(G)
O Grafo abaixo mostra um conjunto independente de tamanho 2formado pelos vertices {u,w}. Existe mais algum ?
u
v
wx
y
Sim. {y, v}, {y, w} e {x, v}.
Conjunto Independente - Exercıcio
1 2
543 6
7 8
Quais os conjuntos independentes:
numero de independencia α(G) =?
Conjunto Independente - Exercıcio
1, 3, 7, 4
1 2
543 6
7 8
Quais os conjuntos independentes:
numero de independencia α(G) =?
Conjunto Independente - Exercıcio
1, 3, 7, 4
1 2
53 6
7 8
Quais os conjuntos independentes:
numero de independencia α(G) =?
Conjunto Independente - Exercıcio
1, 4, 3, 7, 2, 6, 8, 5
1 2
53 6
7 8
Quais os conjuntos independentes:
numero de independencia α(G) =?
Conjunto Independente - Exercıcio
1, 4, 3, 7, 2, 6, 8, 5
1 2
3 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
1, 3, 7, 4
1 2
53 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
1, 4, 3, 7, 5, 2, 6, 8
1 2
53 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
1, 4, 3, 7, 5, 2, 6, 8
1
53
7
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
1 2
543 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
2, 8, 4, 5
1 2
543 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
2, 8, 4, 5, 1, 3, 7, 6
1 2
3 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
1 2
543 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
4, 1, 2, 3, 5, 7, 8
1 2
543 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
4, 1, 2, 3, 5, 7, 8
4 6
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
1 2
543 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
5, 2, 4, 6, 8
1 2
543 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
5, 2, 4, 6, 8, 1, 3, 7
1
53
7
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
1 2
543 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
6, 5
1 2
543 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
6, 5
1 2
43 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
6, 5, 1, 2, 3, 7, 8, 4
1 2
43 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
6, 5, 1, 2, 3, 7, 8, 4
1 2
3 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
6, 5, 4, 1, 2, 3, 7, 8
1 2
43 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
6, 5, 4, 1, 2, 3, 7, 8
1 2
43 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
6, 5, 4, 1, 2, 3, 7, 8
4 6
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}numero de independencia α(G) =?
Conjunto Independente - Exercıcio
1 2
543 6
7 8
Quais os conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}numero de independencia α(G) = 6
Cliques
Um clique (clique maximal) de um grafo e um conjunto devertices adjacentes entre si que nao esta estritamente contidoem outros cliques (conceito similar para dıgrafos).
O tamanho do maior clique de (dı)grafo G e chamadonumero de clique, ω(G).
Um clique de G e um subgrafo completo de G.
Cliques
Quantos cliques os grafos abaixo possuem ? Quais os valores deω(G)?
uv
wx
y
zu
v
wx
y
? cliques, ω(G) =? ? cliques, ω(G) =?
1 2
4
6
3
5
2
5
3
6
4
1
? cliques, ω(G) =? ? cliques, ω(G) =?
Cliques
Quantos cliques os grafos abaixo possuem ? Quais os valores deω(G)?
uv
wx
y
zu
v
wx
y
zu
v
wx
y
2 cliques, ω(G) = 3 ? cliques, ω(G) =?
1 2
4
6
3
5
2
5
3
6
4
1
? cliques, ω(G) =? ? cliques, ω(G) =?
Cliques
Quantos cliques os grafos abaixo possuem ? Quais os valores deω(G)?
uv
wx
y
zu
v
wx
y
zu
v
wx
y
2 cliques, ω(G) = 3 4 cliques, ω(G) = 3
1 2
4
6
3
5
2
5
3
6
4
1
? cliques, ω(G) =? ? cliques, ω(G) =?
Cliques
Quantos cliques os grafos abaixo possuem ? Quais os valores deω(G)?
uv
wx
y
zu
v
wx
y
zu
v
wx
y
2 cliques, ω(G) = 3 4 cliques, ω(G) = 3
1 2
4
6
3
5
2
5
3
6
4
1
4 cliques, ω(G) = 4 ? cliques, ω(G) =?
Cliques - Exercıcio
Quantos cliques os grafos abaixo possuem ? Quais os valores deω(G)?
uv
wx
y
zu
v
wx
y
zu
v
wx
y
2 cliques, ω(G) = 3 4 cliques, ω(G) = 3
1 2
4
6
3
5
2
5
3
6
4
1
4 cliques, ω(G) = 4 2 cliques, ω(G) = 4
Grafo Regular
Um grafo G = (V,A) e regular se todos os vertices de Gpossuırem o mesmo grau, i.e.,
δ(G) = ∆(G) = d(v) ∀v ∈ V
3 4
65
7 8
21
Observe que todo grafo completo e regular de grau n− 1, onde ncorresponde ao numero de vertices.
Grafo Regular - Exercıcio
Quantas arestas sao necessarias para desenhar um grafo regular de9 vertices, onde o grau de cada vertice e igual a 3?
Nao e possıvel! A soma dos graus dos vertices precisa ser par, logoo numero de vertices de grau ımpar tambem deve ser par.
E um grafo com 10 vertices ? Desenhe!
Sim. Um grafo regular com 10 vertices, onde cada verticetem grau 3, tambem e chamado de 3-regular.
34
65
7 8
2
1
910
Grafo Regular - Exercıcio
Quantas arestas sao necessarias para desenhar um grafo regular de9 vertices, onde o grau de cada vertice e igual a 3?
Nao e possıvel! A soma dos graus dos vertices precisa ser par, logoo numero de vertices de grau ımpar tambem deve ser par.
E um grafo com 10 vertices ? Desenhe!
Sim. Um grafo regular com 10 vertices, onde cada verticetem grau 3, tambem e chamado de 3-regular.
34
65
7 8
2
1
910
Grafo Regular - Exercıcio
Quantas arestas sao necessarias para desenhar um grafo regular de9 vertices, onde o grau de cada vertice e igual a 3?
Nao e possıvel! A soma dos graus dos vertices precisa ser par, logoo numero de vertices de grau ımpar tambem deve ser par.
E um grafo com 10 vertices ? Desenhe!
Sim. Um grafo regular com 10 vertices, onde cada verticetem grau 3, tambem e chamado de 3-regular.
34
65
7 8
2
1
910
Grafo Regular - Exercıcio
Quantas arestas sao necessarias para desenhar um grafo regular de9 vertices, onde o grau de cada vertice e igual a 3?
Nao e possıvel! A soma dos graus dos vertices precisa ser par, logoo numero de vertices de grau ımpar tambem deve ser par.
E um grafo com 10 vertices ? Desenhe!
Sim. Um grafo regular com 10 vertices, onde cada verticetem grau 3, tambem e chamado de 3-regular.
34
65
7 8
2
1
910
Grafo Ciclo
Um grafo ciclo, Cn, de n vertices (com n > 2) e um grafosimples 2-regular
34
21
4
6
5
12
3
C4 C6
Grafo Roda
Um grafo roda Wn, com n > 2, e igual ao grafo Cn
adicionado de mais um vertice, o qual e adjacente a todos osdemais.
Um grafo Wn possui n+ 1 vertices e 2n arestas
O vertice adicionado ao Cn possui grau igual a n, enquantoque os demais possuem grau igual a 3.
34
21
5
4
6
5
12
37
W4 W6
Grafo Bipartido
Um grafo G e bipartido se seus vertices podem ser separadosem dois conjuntos independentes de tal forma que todasarestas do grafo conectam vertices de conjuntos distintos.
u v
wx
y
z
Neste caso, o conjunto de vertices pode ser dividido em doisconjuntos
V1 = {y, u, v} e V2 = {x, z, w}
Grafo Bipartido
Considere um grafo bipartido constituıdo dos conjuntos Vj eVk.
Se todo vertice v ∈ Vj estiver ligado a todo vertice u ∈ Vk,entao temos um grafo bipartido completo G, chamado debiclique e denotado por Kr,s, onde r = |Vj | e s = |Vk|.
u v
wx
y
zK3,3
Quantos vertices e quantas arestas possui um biclique Kr,s?
Ele possui r + s vertices e r.s arestas.
Grafo Bipartido
Considere um grafo bipartido constituıdo dos conjuntos Vj eVk.
Se todo vertice v ∈ Vj estiver ligado a todo vertice u ∈ Vk,entao temos um grafo bipartido completo G, chamado debiclique e denotado por Kr,s, onde r = |Vj | e s = |Vk|.
u v
wx
y
zK3,3
Quantos vertices e quantas arestas possui um biclique Kr,s?
Ele possui r + s vertices e r.s arestas.
Grafo Bipartido
Considere um grafo bipartido constituıdo dos conjuntos Vj eVk.
Se todo vertice v ∈ Vj estiver ligado a todo vertice u ∈ Vk,entao temos um grafo bipartido completo G, chamado debiclique e denotado por Kr,s, onde r = |Vj | e s = |Vk|.
u v
wx
y
zK3,3
Quantos vertices e quantas arestas possui um biclique Kr,s?
Ele possui r + s vertices e r.s arestas.
Grafo K-partido
Um grafo G e k-partido se ele possuir k conjuntosindependentes. Logo, um grafo G bipartido e um grafo com 2conjuntos independentes, portanto, ele e 2-partido.
Um grafo G = (V,A) e chamado k-partido se os seguintescriterios forem obedecidos
1 for possıvel particionar o conjunto de vertices em k conjuntosnao vazios V1, V2, · · ·Vk, de forma que eles sejam disjuntosdois a dois, e a uniao dos elementos destes conjuntos seja oconjunto de vertices original.
2 cada aresta a ∈ A, tenha extremidades em conjuntos distintos.
3 k e o menor inteiro que ainda garante os criterios anteriores,caso contrario qualquer grafo com n vertices seria um grafon-partido.
Grafo K-partido - Exercıcio
1 2
543 6
7 8
Conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}
Particionamentos:
Grafo K-partido - Exercıcio
1 2
543 6
7 8
Conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}
Particionamentos:
{1, 2, 3, 6, 7, 8}, {4}, {5}
Grafo K-partido - Exercıcio
1 2
543 6
7 8
Conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}
Particionamentos:
{1, 2, 3, 6, 7, 8}, {4}, {5}{1, 3, 5, 7}, {4, 6}, {2, 8}
Grafo K-partido - Exercıcio
1 2
543 6
7 8
Conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}
Particionamentos:
{1, 2, 3, 6, 7, 8}, {4}, {5}{1, 3, 5, 7}, {4, 6}, {2, 8}{1, 3, 5, 7}, {4}, {2, 6, 8}
Grafo K-partido - Exercıcio
1 2
543 6
7 8
Conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}
Particionamentos:
{1, 2, 3, 6, 7, 8}, {4}, {5}{1, 3, 5, 7}, {4, 6}, {2, 8}{1, 3, 5, 7}, {4}, {2, 6, 8}{4, 6}, {1, 2, 3, 7, 8}, {5}
Grafo K-partido - Exercıcio
1 2
543 6
7 8
Conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}
Particionamentos:
{1, 2, 3, 6, 7, 8}, {4}, {5}{1, 3, 5, 7}, {4, 6}, {2, 8}{1, 3, 5, 7}, {4}, {2, 6, 8}{4, 6}, {1, 2, 3, 7, 8}, {5}{4, 6}, {2, 3, 7, 8}, {1, 5}
Grafo K-partido - Exercıcio
1 2
543 6
7 8
Conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}
Particionamentos:
{1, 2, 3, 6, 7, 8}, {4}, {5}{1, 3, 5, 7}, {4, 6}, {2, 8}{1, 3, 5, 7}, {4}, {2, 6, 8}{4, 6}, {1, 2, 3, 7, 8}, {5}{4, 6}, {2, 3, 7, 8}, {1, 5}
{4, 6}, {1, 2, 7, 8}, {3, 5}
Grafo K-partido - Exercıcio
1 2
543 6
7 8
Conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}
Particionamentos:
{1, 2, 3, 6, 7, 8}, {4}, {5}{1, 3, 5, 7}, {4, 6}, {2, 8}{1, 3, 5, 7}, {4}, {2, 6, 8}{4, 6}, {1, 2, 3, 7, 8}, {5}{4, 6}, {2, 3, 7, 8}, {1, 5}
{4, 6}, {1, 2, 7, 8}, {3, 5}{4, 6}, {1, 2, 3, 8}, {7, 5}
Grafo K-partido - Exercıcio
1 2
543 6
7 8
Conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}
Particionamentos:
{1, 2, 3, 6, 7, 8}, {4}, {5}{1, 3, 5, 7}, {4, 6}, {2, 8}{1, 3, 5, 7}, {4}, {2, 6, 8}{4, 6}, {1, 2, 3, 7, 8}, {5}{4, 6}, {2, 3, 7, 8}, {1, 5}
{4, 6}, {1, 2, 7, 8}, {3, 5}{4, 6}, {1, 2, 3, 8}, {7, 5}{4, 6}, {2, 7, 8}, {1, 3, 5}
Grafo K-partido - Exercıcio
1 2
543 6
7 8
Conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}
Particionamentos:
{1, 2, 3, 6, 7, 8}, {4}, {5}{1, 3, 5, 7}, {4, 6}, {2, 8}{1, 3, 5, 7}, {4}, {2, 6, 8}{4, 6}, {1, 2, 3, 7, 8}, {5}{4, 6}, {2, 3, 7, 8}, {1, 5}
{4, 6}, {1, 2, 7, 8}, {3, 5}{4, 6}, {1, 2, 3, 8}, {7, 5}{4, 6}, {2, 7, 8}, {1, 3, 5}{4, 6}, {2, 3, 8}, {1, 5, 7}
Grafo K-partido - Exercıcio
1 2
543 6
7 8
Conjuntos independentes:
{1, 2, 3, 6, 7, 8}, {1, 3, 5, 7}, {4, 6}
Particionamentos:
{1, 2, 3, 6, 7, 8}, {4}, {5}{1, 3, 5, 7}, {4, 6}, {2, 8}{1, 3, 5, 7}, {4}, {2, 6, 8}{4, 6}, {1, 2, 3, 7, 8}, {5}{4, 6}, {2, 3, 7, 8}, {1, 5}
{4, 6}, {1, 2, 7, 8}, {3, 5}{4, 6}, {1, 2, 3, 8}, {7, 5}{4, 6}, {2, 7, 8}, {1, 3, 5}{4, 6}, {2, 3, 8}, {1, 5, 7}{4, 6}, {1, 2, 8}, {3, 5, 7}
Grafo K-partido
12
5
43
67
8 12
5
43
6
7
8
2
54
3
6
7
8 1 1 2
54
3
6 7
8
Teoria dos Grafos
Componentes, Conj. Indep., Cliques