Definições Importantes em Grafos

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
Definições Importantes
1- Subgrafos: Um grafo G1 é dito ser um subgrafo de um grafo G se todos os vértices e todas as arestas de G1 estão em G.
Observações:
todo grafo é subgrafo de si próprio
o subgrafo de um subgrafo de G1 é subgrafo de G.
um vértice simples de G é um subgrafo de G
uma aresta simples de G (juntamente com suas extremidades) é subgrafo de G.
Prof.: Lamounier Josino de Assis
*
1
5
3
2
4
G
G1
G2
G3
3
4
2
6
5
1
5
1
2
5
6
Prof.: Lamounier Josino de Assis
*
Obs. Se E1 possuir todas as arestas de E, definidas pelos vértices de V1, então Gn é subgrafo induzido.
V1=< 2,3,6,4,5 >
E1= {(2,3)(2,6)(3,6)(6,4)(5,6)}
É um subgrafo induzido,pois
possui todas as arestas 
definidas pelo conjunto V1
de vértices em G
3
4
2
6
5
G3
Prof.: Lamounier Josino de Assis
*
G4 é subgrafo mas não é induzido, pois falta a aresta (2,3) de E1={(2,6)(3,6)(6,4)(5,6)},
onde V1=< 2,3,6,4,5 >. 
G3
3
4
2
6
5
Prof.: Lamounier Josino de Assis
*
2- Operações com Grafos
Sejam G1 = (V1,E1) e G2 = (V2,E2)
União:
 G = G1  G2 = (V1  V2 , E1  E2)
*
Sejam G1 = (V1,E1) e G2 = (V2,E2)
Intersecção: 
G = G1  G2 = (V1  V2 ,E1  E2)
G1  G2
v1
v2
v5
v3
a
c
*
Sejam G1 = (V1,E1) e G2 = (V2,E2)
Ring Sum: 
G = G1  G2 = (V1  V2 ,E’)
	Onde E’ é o conjunto dos arcos que estão em G1 ou G2 mas não em ambos. Ou seja,
E’ = (E1  E2) – (E1  E2)
G1  G2
v2
v4
*
Decomposição: um grafo G é dito ser decomposto em 2 subgrafos g1 e g2 se
	g1  g2 = G
	g1  g2 = vazio
	 g1 e g2 podem ter arcos repetidos?
	 g1 e g2 podem ter vértices repetidos?
Fusão de vértices:
*
Remoção: Sejam vi um vértice de G e ej um arco de G
	G - vi é o subgrafo de G obtido removendo o vértice vi e todos os arcos incidentes a vi 
	G - ej é o subgrafo de G obtido removendo-se o arco ej 
G - e1
G - V4
G
*
V3
V4
e5
G
e1
V1
V3
e2
V4
e4
e3
e5
V2
G
V1
V3
V4
V2
G  G
 Propriedades:
G1  G2 = G2  G1
G1  G2 = G2  G1
G1  G2 = G2  G1
G  G = G  G = G
G  G = completamente desconexo
*
3-. Grafo Completo ( Kn): Um grafo simples é denominado grafo completo de n vértices se e somente se, para todo par de vértices v,w  V, 
v ≠ w (v,w)  E (todo par de vértices é ligado por uma aresta).
Obs. Os grafos completos, também são regulares, isto é, todos os vértices possuem o mesmo grau. 
K2
K3
K4
Prof.: Lamounier Josino de Assis
*
Obs.
O grafo 
1)Não é completo,pois nem todo vértice é adjacente a todos os outros vértices. 
2) Dividindo os vértices em dois conjuntos disjuntos {1,2} e {3,4,5}, tais que dois vértices escolhidos no mesmo conjunto não são adjacentes, mas dois vértices quaisquer escolhidos um em cada conjunto são adjacentes. Tais grafos recebem o nome de grafos bipartido completo. K23 é um grafo bipartido de dois conjuntos {1,2} e {3,4,5}.
 
1
2
5
4
3
Prof.: Lamounier Josino de Assis
*
4- Grafos Isomorfos: São grafos que têm os mesmos vértices, as mesmas arestas e a mesma função que associa as extremidades a cada aresta.
Obs. Na representação de um grafo, as arestas podem se interceptar em pontos que não são vértices do grafo. G1 e G2 abaixo são isomorfos.
4
1
3
2
G1
3
2
1
4
G2
a1
a2
a2
a1
Prof.: Lamounier Josino de Assis
*
G3 também é o mesmo grafo ? 
a
d
b
c
e2
e1
Prof.: Lamounier Josino de Assis
*
Sim, pois se trocarmos os nomes dos vértices e das arestas em G1 através de funções:
f1: 1→ a			f2: a1 → e2
 2 → c			 a2 → e1
 3 → b
 4 → d
Pois f2: a1 liga 1(a) com 3(b) = e2 
 f1: a2 liga 2(c) com 4(d) = e1
Obs. Isto mostra que a relação 
entre as arestas e seus vértices
Extremos é preservada sob a
Mudança de nomes.
a
d
b
c
e2
e1
Prof.: Lamounier Josino de Assis
*
No entanto existem certas condições sob as quais se torna fácil ver que dois grafos não são isomorfos. 
São elas:
Um grafo tem mais vértices que o outro
Um grafo tem mais arestas que o outro
Um grafo tem arestas paralelas e o outro não.
Um grafo tem um laço e o outro não.
Um grafo tem um vértice de grau K e o outro não.
Um grafo é conexo e o outro não.
Um grafo tem um ciclo e o outro não.
 
Prof.: Lamounier Josino de Assis
*
Verifique se os grafos abaixo são isomorfos.Justifique
 sua resposta.
Prof.: Lamounier Josino de Assis
*
Dados os grafos 
Percebemos que cada grafo:
Tem seis vértices e sete arestas
Nenhum deles arestas paralelas ou ciclos
Ambos têm três ciclos
d) Quatro vértices de grau 2 e dois de grau 3.
Portanto, nenhum dos testes óbvios de isomorfismo se aplica. No entanto, o grafo b tem um vértice de grau 2 que é adjacente a dois de grau 3, o que não ocorre com o grafo a, e, assim, os grafos não isomorfos. 
a
b
Prof.: Lamounier Josino de Assis
*
5- Planaridade
O problema das 3 casas
É possível conectar os 3 serviços às 3 casas sem haver cruzamento de tubulação?
 água
 luz
 telefone
A teoria dos grafos mostra que não é possível
Prof.: Lamounier Josino de Assis
*
Planaridade.
Grafo que pode ser desenhado no plano sem cruzamentos, isto é, duas arestas somente se encontram nos vértices onde são incidentes
Ex) Pessoas que projetam circuitos integrados querem que todos os componentes em uma camada do chip formem um grafo planar, de modo a não haver cruzamento de conexões
K4 é um grafo planar pois admite pelo menos uma representação num plano sem que haja cruzamento de arestas (representação planar)
Prof.: Lamounier Josino de Assis
*
Obs.
Nem todos os grafos são planares 
K3,3 e K5 são não planares
Prof.: Lamounier Josino de Assis
*
K5 é um grafo simples completo com cinco vértices. Porém não é possível desenhar um aresta de v3 para v5 sem cruzar a aresta (2,4), ou uma ou mais arestas interiores, como (1,4).
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
Prof.: Lamounier Josino de Assis
*
Planaridade
Todo subgrafo de um grafo planar é planar
Todo grafo que tem um subgrafo não planar é não planar
Todo grafo que contém o K3,3 ou K5 como subgrafos, é não planar
Prof.: Lamounier Josino de Assis
*
Planaridade
Se G é um grafo planar, a representação planar de G divide o plano em regiões.
8 regiões
4 regiões
r4, região externa
r1
r2
r3
r5
r6
r7
r8
r4
r1
r2
r3
r4
Prof.: Lamounier Josino de Assis
*
Planaridade.
A fórmula de Euler (1750)
Seja G um grafo simples planar conectado com e arestas e v vértices. Seja r o número de regiões na representação planar de G. Então, 
r = e – v + 2 
v – nº de vértices
e – nº de arestas
r – nº de regiões
Prof.: Lamounier Josino de Assis
*
Teorema sobre o número de vértices e arestas
Para um grafo simples e planar e conexo com v vértices e e aresta:
Se a representação planar divide o plano em regiões, então v – e + r = 2
Se v ≥ 3 então e  3v – 6
Se v ≥ 3 e se não existem ciclos de comprimento 3, então e  2v – 4 
Prof.: Lamounier Josino de Assis
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*