Teoria dos Grafos - Aula 2 - Conceitos Básicos

Prévia do material em texto

*
DEPARTAMENTO DE INFORMÁTICA
Mestrado em Ciência da Computação
Conceitos Básicos
Teoria dos Grafos
 (Aula 2)
*
Grafos
Conceitos Básicos
*
Grad. CC - Teoria dos Grafos 
V = {v1, v2, v3, v4, v5, v6, v7, v8, v9}	n = 9
E = {e1, e2, e3, e4,..., e9, e10, e11, e12} m = 12
Conceitos Básicos
Grafo: Geometricamente, um grafo é um conjunto de pontos (vértices ou nós) conectados por linhas (arestas).
*
Grad. CC - Teoria dos Grafos 
Conceitos Básicos
Cada aresta é definida por um par não-ordenado de nós, que são suas extremidades:
e = (vi , vj)
e5, e7 , e8 incidentes a v5
v5 adjacente a v4, v6, v7
d(v) : grau do nó v = número de arestas incidentes a v 			 (nós adjacentes)
d(v1) = d(v2) = d(v8) = d(v9) = 2
d(v3) = d(v4) = d(v5) = d(v6) = 3
d(v7) = 4
*
Conceitos Básicos
Teorema: o número de nós de grau ímpar em um grafo finito é par.
Demonstração: 
Multi-grafo: sem laços, mas eventualmente com arestas paralelas
Grafo simples (grafo) : sem laços nem arestas paralelos
*
Grad. CC - Teoria dos Grafos 
Exemplos - Grafos com apelidos
*
Grad. CC - Teoria dos Grafos 
Grafos com apelidos
*
Grad. CC - Teoria dos Grafos 
Grafos com apelidos
Gêmeos
Sunlet
Peixe
*
Grad. CC - Teoria dos Grafos 
Grafos com apelidos
Grafo Pirâmide
Grafo pirâmide forte
Grafo pirâmide dupla
*
Grad. CC - Teoria dos Grafos 
Grafos com apelidos
Grafo Escorpião
*
Conceitos Básicos
Kn: grafo completo com n nós número de arestas: n(n-1)/2
Grafo k-regular: todos os nós têm grau k.
K3
K4
K5
Kn é (n-1)-regular
Quantas arestas têm Kn?
*
Conceitos Básicos
Desenhe um subgrafo 2-regular no grafo de Peterson abaixo.
*
Conceitos Básicos
De interesse entre os grafos regulares são os grafos Platônicos, formados dos vértices e linhas dos cinco sólidos regulares (platônicos) – o tetraedro, octaedro, cubo, icosaedro e dodecaedro.
 tetraedro octaedro cubo icosaedro dodecaedro
*
Conceitos Básicos
Grafo bipartido: o conjunto de nós pode ser particionado em dois subconjuntos V1 e V2 tais que qualquer aresta possui uma extremidade em V1 e a outra em V2 .
Km,n: grafo bipartido completo onde |V1| = m e |V2| = n
V1
V2
*
Grad. CC - Teoria dos Grafos 
Esse grafo é bipartido?
Sim
Conceitos Básicos
*
Grad. CC - Teoria dos Grafos 
Esse grafo é bipartido?
Não
Conceitos Básicos
*
Conceitos Básicos
 é um subgrafo de : 	 
 e são complementares:
1
3
2
4
1
3
2
4
*
Conceitos Básicos
	 	 
Grafo induzido em por :
			
	onde E(X) é o subconjunto de E formado por todas as arestas com as duas extremidades em X.
G(X)
G
X = {2, 3, 4, 5}
1
2
3
4
5
6
Dado o Grafo G=(V,E) e o subgrafo induzido H=(W,F)
Diz que H é um subgrafo induzido quando F contiver exatamente as ligações de G envolvendo vértices de W
*
Conceitos Básicos
Clique: subconjunto de nós que induz 	um subgrafo completo.
C1 = {1, 2, 3}
1
3
2
4
5
6
C2 = {2, 4, 5}
C3 = {4, 6}
C4 = {3} 
*
Conceitos Básicos
*
Conceitos Básicos
Caminho (path) de a : Seqüência P de vértices e arestas alternados, tais que cada aresta (arco) é incidente ao nó anterior e ao nó posterior.
	 P é um ciclo ou circuito. Pode ser representado por somente seus vértices ou arestas 
Caminho elementar (simples): cada vértice (aresta) aparece exatamente uma vez. 
Comprimento de um caminho: número de arestas (um caminho é de comprimento k se existem k arestas no caminho).
Caminhos disjuntos em vértices/arestas: não têm vértices/arestas em comum
*
Conceitos Básicos
Vértices vi e vj são conectados se existe um caminho de vi a vj.
Dois vértices vi e vj estão na mesma componente conexa se existe um caminho entre eles.
Um grafo é conexo se possui uma única componente conexa, ou seja, se existe um caminho entre qualquer par de nós
	
É conexo?
Problema importante: determinar se um grafo é conexo ou não.
*
Um grafo gerador de um grafo conexo G=(V,E) é um subgrafo conexo G’ com o mesmo conjunto de nós V.
Conceitos Básicos
Grafo G
Grafo gerador de G
v é um ponto de articulação do grafo conexo 
	G se sua remoção desconecta G.
Se uma componente conexa de um grafo não contem ponto de articulação, então ela é uma componente 2-conexa.
Uma aresta e cuja remoção desconecta um 
	grafo conexo é chamada de ponte.
*
Conceitos Básicos
Digrafo ou grafo orientado: grafo no qual são associadas direções aos seus arcos.
1
3
0
1
*
Conceitos Básicos
Uma cadeia a1, a2, ..., aq de arcos é uma sequência de arcos (ou arestas) tal que cada arco ai tem uma extremidade comum com o arco ai-1 e outra com o arco ai+1, 2 ≤ i ≤ q-1.
3
2
4
1
5
a1
a2
a3
a5
a6
a4
a7
a2, a5, a6, a4  cadeia entre os nós 2 e 3
Ciclo: cadeia cujas extremidades coincidem (conceito não-orientado).
Caminho a1, a2,..., aq: cadeia em que todos os arcos possuem a mesma orientação (extremidade final do arco ai coincide com a extremidade inicial do arco ai+1).
Circuito: caminho cujas extremidades coincidem.
*
Conceitos Básicos
Um digrafo é conexo (ou fracamente conexo) se possui uma única componente conexa e existe uma cadeia entre qualquer par de nós. Matematicamente, se e só se xA, yA, xy , existe uma cadeia de x a y.
	
*
Conceitos Básicos
Um digrafo é fortemente conexo se e só se xA, yA, xy , existe um caminho de x a y.
	
*
Conceitos Básicos
Dois vértices vi e vj estão na mesma componente fortemente conexa de um grafo orientado se existe um caminho de vi a vj e um caminho de vj a vi.
{1, 2, 3, 4, 5, 6, 8, 9, 10}
{7}
{1, 2, 3, 4}
{5, 6, 7}
*
Conceitos Básicos
Um digrafo é semi-fortemente conexo (ou unilateralmente conexo) se e só se xA, yA, xy , existe um caminho de x a y ou existe um caminho de y a x.
	
*
Conceitos Básicos
Grafos planares:
	Um grafo é planar se ele pode ser representado no plano de modo tal que não haja interseção entre suas arestas.
K3 ?
K5 ?
K4 ?
K3,3 ?
PLANAR
NÃO
PLANAR
NÃO
*
Conceitos Básicos
Árvore: grafo conexo sem circuitos
Floresta: grafo cujas componentes conexas são árvores
Sim!
*
Conceitos Básicos
Teorema: Se T é uma árvore com n vértices, então:
Existe um único caminho entre dois nós quaisquer de T.
Sejam i, j dois nós de T tais que a aresta (i, j) não existe. Então, a inserção da aresta (i, j) em T provoca a formação de exatamente um ciclo.
 T possui n-1 arestas.
Graphviz | Graphviz - Graph Visualization Software
*
Conceitos Básicos
Matriz de incidência nó-arco:
	Uma linha para cada nó
	Uma coluna para cada aresta
Formas de representação e matrizes associadas a um grafo
1
2
3
4
a1
a2
a3
a4
a5
*
Conceitos Básicos
Uma matriz quadrada é unimodular se seu determinante é 1.
Uma matriz retangular A é totalmente unimodular se e somente se qualquer matriz quadrada regular extraída de A é unimodular.
A matriz de incidência de um grafo é totalmente unimodular. Uma matriz de incidência contém exatamente dois elementos não-nulos por coluna (+1, -1).
Formas de representação e matrizes associadas a um grafo
Obs: Uma matriz quadrada se chama regular se seudeterminante é não nulo. Caso contrário, se chama singular.
*
Conceitos Básicos
Matriz de adjacência:
	Uma linha para cada nó
	Uma coluna para cada nó
Grafos sem arcos paralelos:
n2 posições
Formas de representação e matrizes associadas a um grafo
aij = 1  (i , j )  A
aij = 0  (i , j )  A
*
Conceitos Básicos
Lista de nós:
	Cada nó aponta para a lista de seus sucessores (ou nós adjacentes)
Formas de representação por listas de adjacências
n nós 
m arestas
 n +m posições
nós sucessores
nós predecessores
*
Conceitos Básicos
Formas de representação por listas de adjacências
m
n
1 2 3 4
1 2 3 4 5 6 7
Lista de arcos
S(.)
T(.)
É simples passar de uma forma de representação para outra.
*
*
Conceitos Básicos
Desenhar o grafo representado pela matriz de adjacência abaixo:
Quais são as componentes fortemente conexas deste grafo?
Representar sua matriz de incidência.
{1,2,5,6}, {3,4}
*
Conceitos Básicos
Representar o mesmo grafo por sua lista de adjacências.
Representar o grafo por sua lista de arcos.
*
Conceitos Básicos
Algoritmo para converter uma representação de um grafo orientado sob forma de matriz de adjacência em matriz de incidência.
*
Grad. CC - Teoria dos Grafos 
GRAFOS: EXERCÍCIOS
Mostre que o grau máximo de qualquer vértice em um grafo simples com n vértices e n-1.
Mostre que o numero máximo de arestas em um grafo simples com n vértices e n(n-1)/2.
Construa um grafo com 10 vértices, que possua a seguinte seqüência de graus: {1,1,1,3,3,3,4,6,7,9}, ou mostre ser impossível construí-lo.
Escrever um algoritmo para converter a representação de um grafo orientado sob forma de matriz de incidência em uma representação por listas de adjacência.
*
Dado o grafo abaixo, preencha os vértices com os números 1,2,3,4,5,6,7,8 de tal maneira que números subseqüentes não sejam adjacentes. Explique sua idéia?! Determine a matriz e a lista de adjacência do grafo e faça um algoritmo para a lista de adjacência. Elabore um algoritmo para a sua idéia.
1
8
2
7
5
4
6
3
GRAFOS: EXERCÍCIOS
*
6. Mostre o grafo correspondente a seguinte situação:
GRAFOS: EXERCÍCIOS
*
*
*
*
Grad. CC - Teoria dos Grafos 
M.C.Escher / Cordon Art B.V.
Fim da Aula 2 
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*