Slide - Principais Classes de Grafos - 2022-2

Principais Classes de Grafos Principais Classes de Grafos 1 / 21 Grafos Regulares Dado um grafo G = (V, E) e d um inteiro positivo. Dizemos que G ´e d-regular se para todo v´ertice v ∈ V, d(v) = d. Se G ´e 3-regular, dizemos que G ´e cubico ´ . 2 / 21 Exemplo de Grafos Regulares 0-regulares 1-regulares 2-regulares cubicos Independente Maximo z α=4 {1,3,6,8} 1 2 34 Maximal x y G {1,7} . .. a b c 5 6 7 8 ω=2 2 G G GG e d 1 8910 17 18 11 3 12 α=5=n α=m=n/2 f i g h 7 6 5 16 20 15 19 13 14 4 α=5 {x,a,c,f,h} α=8 {1,3,6,9.11,14,16,19} ω=1 ω=2 ω=3 ω=2 3 / 21 Cliques e Conjuntos independentes Dado um grafo G = (V, E) e S ⊂ V. Dizemos que S ´e uma clique se para todo u, v ∈ S, uv ∈ E. Pelo inteiro ω representamos o numero de clique ´ de G que ´e o numero de ´ v´ertices de uma maior clique de G. 4 / 21 Cliques e Conjuntos independentes Dado um grafo G = (V, E) e S ⊂ V. Dizemos que S ´e independente se para todo u, v ∈ S, uv ∈/ E. Pelo inteiro α representamos o numero de independ ´ ˆencia de G que ´e o numero de ´ v´ertices do maior conjunto independente de G. 5 / 21 Cliques e Conjuntos independentes Dado um grafo G = (V, E) e S ⊂ V. Dizemos que S ´e um conjunto maximal com a propriedade p, se 1. S satisfaz a propriedade p e 2. qualquer R superconjunto pr´oprio de S (S ⊂ R e S = R) n˜ao satisfaz a propriedade p. Maior clique={a,b,c} Maiores independentes={a,d}, Maiores cliques={a,d}, {b,e}, {b,d}, {c,e}. {b,e}, {b,d}, {c,e}. Maior independente={a,b,c} a b c a b c e d e d G G α=2 ω=3 α=3 ω=2 Maior clique={a,b,c} Maiores independentes={a,d}, Maiores cliques={a,d}, {b,e}, {b,d}, {c,e}. {b,e}, {b,d}, {c,e}. Maior independente={a,b,c}bb 6 / 21 Notac¸˜oes Dado um grafo G = (V, E), 1. S ⊂ V, 2. R ⊂ E, 3. v ∈ V e 4. e ∈ E. Notamos: 1. G–S = (V \ S, E \ {uv | u ∈ S ou v ∈ S}), 2. G–R = (V, E \ {uv ∈ R}), 3. G–v = (V \ {v}, E \ {uv ∈ E}), 4. G–e = (V, E \ {uv}). A uni˜ao disjunta dos grafos G com H ´e o grafo G ∪ H = G + H = (V(G) ∪ V(H), E(G) ∪ E(H)). 7 / 21 Conjuntos Dominantes e Cobertura por v´ertices Dado um grafo G = (V, E) e S ⊂ V. Dizemos que S ´e dominante se para todo u ∈ V,ou u ∈ S e existe v ∈ S tal que uv ∈ E. Dado um grafo G = (V, E) e S ⊂ V. Dizemos que S ´e cobertura de arestas por v´ertices de G se para todo uv ∈ E, ou u ∈ S ou v ∈ S. a b c a b c e d e d Conjunto dominante minimo Cobertura minima Qual o menor numero de cameras para vigiar todas as salas? Qual o menor numero de cameras para vigiar todos os corredores? bb8 / 21 Mais exemplos de Conjuntos Dominantes e Cobertura por v´ertices Dominante m´ınimo = {a, d} Dominante m´ınimo = {d, f } Cobertura por v´ertices m´ınima = {a, c, d} Cobertura por v´ertices m´ınima = {d, f } Conjunto independente m´aximo = {b, e} Conjunto independente m´aximo = {a, b, c, e, g} 9 / 21 Independˆencia e cobertura Theorem Dado um grafo G = (V, E) e S ⊂ V . Ent˜ao S ´e um conjunto independente de G se e somente se V \ S ´e uma cobertura de arestas por v´ertices de G. Proof. Suponha que S ´e um conjunto independente de G. Ent˜ao, como S ´e um conjunto independente, as arestas de G podem ser particionadas em duas partes 1. As arestas de G que tem exatamente 1 extremidade em S. Estas arestas tem exatamente 1 extremidade em V \ S. 2. As arestas de G que tem exatamente as duas extremidade em V \ S. Logo, V \ S ´e uma cobertura. 10 / 21 Independˆencia e cobertura Theorem Dado um grafo G = (V, E) e S ⊂ V . Ent˜ao S ´e um conjunto independente de G se e somente se V \ S ´e uma cobertura de arestas por v´ertices de G. Proof. Suponha que V \ S ´e uma cobertura de arestas por v´ertices de G. Logo cada aresta uv ∈ E tem uma extremidade em V \ S. Assim, nenhuma aresta de G tem 2 extremidades em S. E dessa forma S ´e um conjunto independente. 11 / 21 Completos Dado n um inteiro positivo. O grafo completo Kn = (V, E) em n v´ertices satisfaz que para todo par u, v ∈ V, a aresta uv ∈ E. n 1 2 3 4 n ≥ 1 Kn m 0 1 3 6 =n(n−1) n 2 2 12 / 21 Partic¸˜ao Dado um conjunto S e um inteiro positivo k. Dizemos que os conjuntos (V1, V2, V3, . . . , Vk ), formam uma partic¸˜ao para o conjunto S, com as partes V1, V2, V3, . . . , Vk se 1. V1 ∪ V2 ∪ V3 ∪ . . . ∪ Vk = S e 2. se i = j, ent˜ao Vi ∩ Vj = ∅. 13 / 21 Bipartidos Dizemos que um grafo G = (V, E) ´e um bipartido se existe uma partic¸˜ao em conjuntos independentes (V1, V2) de V. Dados n1, n2 inteiros positivos. O grafo bipartido completo Kn1,n2 = (V, E) admite uma partic¸˜ao em conjuntos independentes (V1, V2) de V com |V1| = n1, |V2| = n2, tal que, se u ∈ V1 e v ∈ V2, ent˜ao uv ∈ E. Dizemos que Sn = K1,n ´e o grafo estrela n, dizemos que S3 ´e a garra . 14 / 21 Bipartidos Completos Kn1,n2 Kn1,n2 1 2 3 n2 1 m = 1 m = 2 m = 3 2 m = 4 m = 6 3 m = 9 n1 m = n1 × n2 15 / 21 Grafos Trivial, Caminho, Ciclo e Roda Dizemos que o grafo G = (V, E) ´e trivial se n = 1. Dado n um inteiro positivo. O grafo caminho Pn = (V, E) em n v´ertices satisfaz V = {v1, . . . , vn} e E = {vivi+1 | i ∈ {1, 2, . . . , n − 1}}. Dado n ≥ 3 um inteiro positivo. O grafo ciclo Cn = (V, E) em n v´ertices satisfaz V = {v1, v2, v3, . . . , vn} e E = {vivi+1 : i ∈ {1, 2, 3, . . . , n − 1}} ∪ {vnv1}. Dado n ≥ 3 um inteiro positivo. O grafo roda Wn = (V, E) satisfaz: V = {c, v1, v2, v3, . . . , vn}, E = {vivi+1 | i ∈ {1, 2, 3, . . . , n − 1}} ∪ {vnv1} ∪ {cvi| i ∈ {1, 2, 3, . . . , n}. 16 / 21 Exemplo de caminhos, ciclos e rodas n G 1 2 3 4 5 . . . |E(G)| Pn m = 0 m = 1 m = 2 m = 3 m = 4 . . . m = n − 1 Cn − − m = 3 m = 4 m = 5 . . . m = n Wn − − m = 6 m = 8 m = 10 t . . . m = 2n 17 / 21 n-cubos Dado n um inteiro n˜ao negativo. O grafo n-cubo Qn = (V, E) satisfaz que V ´e o conjunto dos vetores (v1, v2, . . . , vn), vi ∈ {0, 1}, |V| = 2ne uv ∈ E(Qn) se e somente se |diff (u, v)| = 1, isto ´e u tem exatamente 1 bit diferente de v. Veja que 1. |V(Qn)| = 2n. 2. |E(Qn)| = 2n−1n. Veja tamb´em que em um completo Kn o numero de arestas ´ m = O(n2). E no caso do n-cubo |E(Qn)| = |V(Qn)|. log2|V(Qn)|, que mostra que os n-cubos tem poucas arestas em relac¸˜ao a um grafo completo. 18 / 21 Exemplos de n-cubos Q0 Q1 0 1 Q2 00 01 11 10 Q3 000 001 011 010 110 111 101 100 Q4 0000 0001 0011 0010 0110 0111 010 Q4 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 11 Caminho m´ınimo do vertice 00 19 / 21 Uma matriz de adjacˆencias para os n-cubos Q 0 = (0) 0 1 Q 1 ( ) 0 1 1 0 ( ) 0 1 ( )1 0 1 0 = = =QQ 0 0 10 1 1 00 01 10 11 0 1 Q 2 = ( ) 0 1 00 0 1 Q 1 11( ) 0 1 01 1 0 1 0 1 0 = 0 1 0 1 1 0 Q 1 00 01 10 11 10 1 0 1 0 000 001 010 100 110 101 111 011 0 1 000 0 1 0 0 0 1 000 001 010 011 100 110 101 111 )0 1 1 0 001 011 010 Q3 = 110 111 101 100 20 / 21 1 0 0 1 0 1 1 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 ´Indice Remissivo I d-regular, 2 clique, 4 cobertura de arestas por v´ertices, 8 conjunto dominante, 8 conjunto independente, 5 conjunto maximal com a propriedadep, 6 cubico, 2 ´ grafoCn ciclon,n≥ 3, 16 grafon-cuboQn,n≥ 0, 18 grafoPn caminhon, 16 grafoSn=K1,n estrelan, 14 grafoWn rodan,n≥ 3, 16 grafo bipartido, 14 grafo bipartido completoKn 1 ,n 2, 14 grafo completoKn, 12 grafo garra, 14 grafo trivial, 16 numero de clique - ´ω, 4 numero de independ ´ˆencia, 5 partes, 13 partic¸˜ao, 13 21 / 21