Tema 01 - Conceitos Básicos - TEXTO DE APOIO

Prévia do material em texto

NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 1 
 
 
 
 
 
 
 
 
 
 
 
 
GRAFOS 
 
 
 
 
 
 
 
 
 
NOTAS DE AULA 
 
 
 
 
PROF.: JÚLIO TADEU CARVALHO DA SILVEIRA 
 
 
 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 2 
1. GRAFOS 
1.1 DEFINIÇÕES E TERMINOLOGIA 
As definições a seguir se aplicam a grafos simples não direcionados. 
• Grafo (ou grafo simples) 
Um grafo G é um par G = (V, E), onde: 
V ou V(G) é um conjunto não vazio. 
Seus elementos são denominados vértices (ou nós) de G. 
E ou E(G) é um conjunto de pares não–ordenados de elementos distintos de V. 
Seus elementos são denominados arestas (edges) de G. 
O nome grafo decorre de que esta estrutura admite uma representação geométrica. 
EXEMPLO 1: G = (V, E), com |V| = 10 e |E| = 8 
V = { v1, v2, v3, v4, v5, v6, v7, v8, v9, v10 } 
E = { {v2,v3}, {v3,v4}, {v4,v5}, {v5,v3}, {v4,v6}, {v7,v4}, {v8,v9}, {v9,v10} } 
Representação geométrica 
 
FIGURA 1 – REPRESENTAÇÃO GEOMÉTRICA DO GRAFO DO EXEMPLO 1. 
Uma aresta é especificada pelos seus vértices extremos: e = {u,v} = {v,u}. 
Outras notações: e = uv = vu ou ainda e = v-w = w-v 
Alguns autores também usam a notação de par ordenado (v,w), utilizada em grafos 
direcionados, para especificar um par não-ordenado quando o contexto estiver implícito. 
No grafo do EXEMPLO 1, v2 ∈ V e {v5,v3} ∈ E. 
Ou então (v5,v3) ∈ E 
 v3-v5 ∈ E 
 v5v3 ∈ E. 
• CONVENÇÃO: 
 n = |V| e m = |E|. No grafo do EXEMPLO 1, temos n = 10 e m = 8. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 3 
• Vértices adjacentes e vértice isolado 
Vértices unidos por uma aresta são denominados adjacentes. No EXEMPLO 1, o vértice v3 é 
adjacente aos vértices v2, v4 e v5. Um vértice isolado não tem vértices adjacentes. No EXEMPLO 1, v1 
é um vértice isolado. 
• Aresta incidente: uma aresta é dita incidente aos seus dois vértices extremos. 
No EXEMPLO 1, a aresta (v2,v3) é incidente a v2 e a v3. 
• Arestas adjacentes: duas arestas que possuem vértice extremo em comum. 
No EXEMPLO 1, a aresta (v2,v3) é adjacente à aresta (v4,v3). 
• Pseudografos e Multigrafos 
É possível estender a definição de um grafo de forma a permitir arestas do seguinte tipo: 
− Laços (loops): arestas da forma (v,v), unindo um vértice a si mesmo; 
− Arestas paralelas: e1 = (v,w) e e2 = (v,w); ou seja, duas arestas distintas que unem o 
mesmo par de vértices. 
Um grafo que possua laços é denominado pseudografo; um grafo que contenha arestas 
paralelas é denominados multigrafos, como ilustrado na FIGURA 2. 
3
2
1
4
 
FIGURA 2 – PSEUDOGRAFO E MULTIGRAFO. 
Neste estudo NÃO ABORDAREMOS pseudografos e multigrafos: o termo grafo sempre será 
utilizado para designar um grafo simples (sem laços nem arestas paralelas). 
• GRAFO TRIVIAL: 
O grafo em que |V| = 1 é denominado grafo trivial. 
 
FIGURA 3 – GRAFO TRIVIAL: n = 1, E = ∅ 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 4 
• Grau de um vértice 
Denomina-se grau de um vértice v, notando-se grau(v) ou d(v), ao número de arestas que 
sejam incidentes a v. Ou, de forma equivalente, ao número de vértices adjacentes a v. A notação 
d(v) refere-se ao termo degree (inglês). 
Observe que d(v) ∈ IN ; se d(v) = 0 então v é um vértice isolado. 
No grafo do EXEMPLO 1: 
d(v1) = 0 d(v6) = 1 
d(v2) = 1 d(v7) = 1 
d(v3) = 3 d(v8) = 1 
d(v4) = 4 d(v9) = 2 
d(v5) = 2 d(v10) = 1 
 
• Isomorfismo 
Dois grafos G1(V1,E1) e G2(V2,E2) são isomorfos se existe uma bijeção f: V1 → V2 que 
preserve as adjacências entre seus respectivos vértices. Ou seja: 
|V1| = |V2| 
|E1| = |E2| 
(v,w) ∈ E1 ⇔ ( f(v) , f(w) ) ∈ E2. 
Em outras palavras, rearranjamos a disposição dos vértices (que podem até mesmo ser 
renomeados) de forma que as arestas do “novo” grafo correspondam às mesmas arestas (e seus 
respectivos vértices extremos) do grafo original. 
Como consequência da definição acima, é imediato verificar que |V1| = |V2| e |E1| = |E2| 
são condições necessárias (mas não suficientes) para o isomorfismo. Veja o exemplo ilustrado na 
FIGURA 4 abaixo, e complete o quadro a seguir: 
 
FIGURA 4 – GRAFOS ISOMORFOS. 
Complete: f(v1) = f(v2) = f(v3) = f(v4) = 
f(v5) = f(v6) = f(v7) = 
Resposta: f(v1) = g f(v2) = e f(v3) = a f(v4) = c 
f(v5) = f f(v6) = b ou d f(v7) = b ou d 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 5 
O isomorfismo entre grafos pode ser visualizado mesmo sem rotularmos os vértices (apenas 
identificando a mesma estrutura de conectividades), como na FIGURA 5 a seguir. 
 
FIGURA 5 – ISOMORFISMO: G1 E G2 SÃO ISOMORFOS. G3 E G4 SÃO ISOMORFOS 
EXERCÍCIOS 1.1 
1) Construir uma representação geométrica do grafo a seguir: 
V = { A, B, C, D, E, F } 
E = { {A,C}, {A,D}, {A,E}, {B,C}, {B,D}, {B,E}, {C,E}, {D,E} } 
2) Caracterize os conjuntos V e E de cada uma das representações a seguir: 
 a) 
 
V1 = { 
E1 = { 
 b) 
 
V2 = { 
E2 = { 
3) Desenhe os grafos G3 e G4, obtidos do G1 (questão 2) através dos isomorfismos indicados: 
 c) 
 
f : V1 → V3 f (1) = A f (2) = B f (3) = C 
 f (4) = D f (5) = E f (6) = F 
 d) 
 
4
2
1 6
3
5
G4
 
g : V1 → V4 
g(i) = 7 – i 
4) Calcule d(v) para cada vértice dos grafos G1 e G2 anteriores. 
Verifique se G1 e G2 satisfazem os teoremas 1.1 e 1.2. 
5) Desenhe todos os grafos distintos (não isomorfos) contendo 2, 3 ou 4 vértices. 
6) Existe algum grafo com 6 vértices, cujos graus são 0, 1, 2, 3, 4, 5? 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 6 
7) Desenhe algum grafo com 6 vértices, cujos graus são 2, 3, 3, 3, 3, 3; ou prove porque tal grafo 
não existe. 
8) Desenhe um grafo com 10 vértices, em todos os vértices tenham grau 1; ou prove que não 
existe grafo com tais características. 
9) Existe algum grafo com 5 vértices, cujos graus são 0, 1, 2, 3, 4? Por que? 
10) Prove que em qualquer grafo não trivial existem pelo menos dois vértices de mesmo grau. 
11) Desenhe todos os grafos não isomorfos que tenham o mesmo número de vértices e também 
o mesmo número de arestas. Faça isso para n = 3, 4, 5. 
12) Quantos grafos não isomorfos com 5 vértices de graus 1, 1, 1, 1, 2, você consegue desenhar? 
13) Quantos grafos não isomorfos com 5 vértices de graus 1, 1, 1, 2, 3, você consegue desenhar? 
14) Quantos grafos não isomorfos com 6 vértices de graus 1, 1, 1, 1, 1, 3, você consegue 
desenhar? 
15) Desenhe dois grafos NÃO isomorfos com 6 vértices, que tenham graus 1, 1, 1, 2, 2, 3. 
 
RESPOSTAS E COMENTÁRIOS DE ALGUNS EXERCÍCIOS 
3) 
c) 
 
d) 
 
5) 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 7 
6) Não. Demonstre esta impossibilidade a partir dos teoremas 1.1 ou 1.2. 
7) Demonstre esta impossibilidade a partir dos teoremas 1.1 ou 1.2. 
8) 
 
9) Existe algum grafo com 5 vértices, cujos graus são 0, 1, 2, 3, 4? Por que? 
Não. Suponha que exista tal grafo, sendo V = { v0, v1, v2, v3, v4 }. Considere que v0 e v4 os 
vértices de graus d(v0) = 0 e d(v4) =4. Assim, o vértice v4 deveria ser adjacente a TODOS os 
demais vértices do grafo – inclusive ao vértice v0. Mas isto é um absurdo, pois v0 é um 
vértice isolado, e não poderia ser adjacente a nenhum outro vértice, inclusive ao v4. Logo, 
tal grafo não existe. 
10) Prove que em qualquer grafo não trivial existem pelo menos dois vértices de mesmo grau. 
Dica. Em um grafo (simples) com n vértices, todos os graus dos vértices devem ser valores 
entre 0 e n-1 (inclusive). Formalmente: (∀v∈V) [ d(v) ∈ { 0,1,2,…,n-1} ]. 
Temos então n vértices e n valores distintos para os graus destes vértices. Porém, não 
podemos um vértice grau 0 e também um vértice com grau n-1 no mesmo grafo 
(resultado análogo ao exercício 9). 
Assim, apenas n-1 valores distintos serão graus de algum vértice. 
Temos então: n vértices do grafo, e apenas n-1 valores possíveis para seus graus. 
Consequentemente, pelo Princípio das Casas de Pombo, pelo menos dois vértices terão 
graus idênticos. 
12) 
 
Existe algum outro? 
13) 
 
Existe algum outro?14) Dica: existe apenas um grafo possível. 
15) Existem três grafos possíveis. Dois são exibidos abaixo. Você consegue desenhar mais um?