Teoria dos Grafos - Instituto de Informática - UFRGSprestes/Slides/aula2-Renan.pdf · Grafo...

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