View
8
Download
0
Category
Preview:
Citation preview
Figueiredo – 2011
Teoria dos GrafosAula 2
Aula passadaLogísticaObjetivosGrafos, o que são?Formando pares
Aula de hojeMais problemasreaisDefinições importantesAlgumas propriedades
Figueiredo – 2011
Objetivos da DisciplinaGrafos como ferramenta de modelagem
abtração de problemas reais
Algoritmos eficientes em grafos para resolver problemas
Abordagem?
Estudo de problemas reais
Construção de algoritmos eficientescomplexidade de algoritmos
Técnicas para construção de algortimos
Figueiredo – 2011
O que é um grafo?Definição: “Um grafo é um conjunto de pontos, chamados vértices, conectados por linhas, chamadas de arestas” [Wikipedia 2008]
a
c
b
e
d
f
É um grafo?
Definição burocrática!
Figueiredo – 2011
Grafo, outra definiçãoAbstração que permite codificar relacionamentos entre pares de objetos
Qualquer um! Ex. pessoas, cidades, empresas, países, páginas web, filmes, etc...
Que objetos?
Que relacionamentos?
Qualquer um! Ex. amizade, conectividade, produção, língua falada, etc.
Simétrico ou assimétrico
Figueiredo – 2011
GrafoAbstração que permite codificar relacionamentos entre pares de objetos
objetos
Exemplos?
vértices do grafo
arestas do graforelacionamentos
Figueiredo – 2011
Poder da Abstração
Muitos problemas resolvidos com o mesmo algoritmo (solução) em cima da abstração!
Problema Modelo(grafo)
ProblemaProblemaProblema
Solução
Algoritmo
Figueiredo – 2011
Alocação de Professores
Cada professor pode lecionar uma ou mais disciplinas
N professores M disciplinas (< N)
Problema 1: Dado o que cada professor pode lecionar, é possível que as M disciplinas sejam oferecidas simultaneamente?
Problema 2: Qual o maior número de disciplinas que podem ser oferecidas?
Figueiredo – 2011
Alocação de ProfessoresComo abstrair o problema (via grafos)?
Mesmo algoritmo!
Mesma abstração!
A
B
C
D
1
2
3
4
Figueiredo – 2011
Pesquisando no OrkutMilhões de pessoas (profiles)
Profiles interligadas via relacionamentos declarados
Problema 1: Como saber se duas pessoas estão “conectadas” através de uma sequência de relacionamentos?
Problema 2: Qual é o menor caminho entre duas pessoas?
Orkut resolve os dois problemas!
Figueiredo – 2011
Antonio é “amigo” da Camila
Pesquisando no Como abstrair o problema (via grafos)?
Objeto: profiles (pessoas)
Relacionamento: relacionamentos declarados
Antonio
Beto
CarlosDiogo
Ana
Bruna
Camila
Dalva
Carlos e Ana: Conectados? Menor caminho?
Figueiredo – 2011
Pesquisando no
Como Orkut resolve o problema?
milhões de profiles e relacionamentos!
Algoritmo(eficiente)!
Figueiredo – 2011
Viagem entre Cidades
Cidades brasileiras
Estradas entre cidades
Problema 1: Como saber se duas cidades estão “conectadas” por estradas?
Problema 2: Qual é o menor (melhor) caminho entre duas cidades?
Figueiredo – 2011
72Km
429Km
434Km716Km
1015Km
586Km
Viagem entre CidadesComo abstrair o problema (via grafos)?
Algoritmo parecido!(algumas variações)
Abstração parecida!
Rio
Sampa
BH
SantosBrasília
Figueiredo – 2011
GrafoAbstração que permite codificar relacionamentos entre pares de objetos
Como representá-loformalmente?
Conjuntos de objetos e de pares relacionados
Conjuntos!
Figueiredo – 2011
GrafoGrafo G = (V, E)
V = conjunto de objetoschamaremos de vértices ou nós
E = conjunto de pares relacionados chamaremos de arestas
par não ordenado: (a,b) == (b,a)
Exemplo: G = (V, E)V = {1, 2, 3, 4}
E = {(1,2), (1,3), (2,3), (3,4)}
Figueiredo – 2011
Representação Gráfica
Desenho de G (o que vimos até agora)representação gráfica dos conjuntos
Exemplo: G = (V, E)V = {1, 2, 3, 4}
E = {(1,2), (1,3), (2,3), (3,4)}
1
3 4
2
Figueiredo – 2011
Adjacência e IncidênciaVértices adjacentes são vértices “vizinhos”
mais precisamente...
Dado grafo G= (V, E)
Dois vértices a e b são adjacentes se existe e = (a, b) no conjunto E
Aresta e é incidente aos vértices a e b
Exemplo: G = (V, E)
V = {1, 2, 3, 4}
E = {(1,2), (1,3), (2,3), (3,4)} 4 e 1 são adjacentes?
3 e 2 são adjacentes?
Figueiredo – 2011
Vértices e ArestasNúmero de vértices de um grafo
n = |V| cardinalidade do conjunto
Número de arestas de um grafo
m = |E|Dado G = (V, E)
Menor número de arestas de G?
Maior número de arestas de G?
zero!
número de pares não ordenados em um conjunto de n = |V| objetos
n2 n n−1
2≤n2=
Figueiredo – 2011
GrauGrau de um vértice v
número de vértices adjacentes a v
função grau(v)
Exemplo: G = (V, E)V = {1, 2, 3, 4}
E = {(1,2), (1,3), (2,3), (3,4)}
grau(1) = ?
grau(4) = ?
Dado G = (V, E)Grau mínimo de um vértice?
Grau máximo de um vértice?
zero!
n - 1
Figueiredo – 2011
Grafo RegularTodos os vértices têm mesmo grau
no caso de r-Regular, grau é r
Exemplo: G é 2-regular, n = 3
V = {1, 2, 3}
E = {(1,2), (1,3), (2,3)}
1
3
2
Dado G = (V, E), e G r-regular
Quantas arestas tem G?
∣E∣=nr2
Por que?
Figueiredo – 2011
Grafo RegularSão regulares?
1 32 4
5 76 8
1 3
2
6 4
5
É possível ter qualquer combinação de n e r?
Figueiredo – 2011
Grafo CompletoAresta presente entre cada par de vértices
todos os vértices tem grau máximo
Notação de grafo completo
Kn onde n é o número de vértices
Exemplos
1
K1
1
2
K2
1 3
2
K3
1 3
2 4
K4
1 3
5 4
2
K5
Quantas arestas têm Kn?
Figueiredo – 2011
Ex. caminho entre 1 e 7?
1, 2, 3, 7 (1,2), (2,3), (3,7)
1, 5, 6, 2, 6, 7 é caminho?
CaminhoComo definir “caminho” em um grafo?Ex. caminho entre 1 e 7?
1 32 4
5 76 8
Caminho entre dois vérticessequência de vértices conectados por arestas
Caminho entre v1 e v
k
sequência v1, ..., v
k, tal que i=1,k−1vi ,v i1∈E
Figueiredo – 2011
Caminho SimplesVértices do caminho são distintos
não há “voltas”
1 32 4
5 76 8
Ex. caminho entre 1 e 7?
1, 5, 6, 2, 6, 7
1, 5, 8, 7
Dado G = (V, E)
qual é o menor caminho simples entre dois vértices?
qual é o maior?
não é caminho simples
é caminho simples
Comprimento do caminho
número de arestas que o forma
Figueiredo – 2011
CicloCaminho simples que começa e termina no mesmo vértice
v1 = v
k
1 32 4
5 76 8
Ex. ciclo em 5?
5, 1, 2, 3, 7, 6, 5
5, 1, 4, 8, 5
Dado G = (V, E)
qual é o maior ciclo?
n vértices, ciclo hamiltoniano
Comprimento do ciclo
número de arestas que o forma
Figueiredo – 2011
Subgrafo
Um grafo que é “parte” de outro grafomais precisamente...
Dado G = (V, E)
G' = (V', E') é subgrafo de G se
eV '⊆V E'⊆E
Figueiredo – 2011
Subgrafo Exemplo
1 32 4
5 76 8
Dado G = (V, E)
1 32
5 76
É subgrafo de G?
1 32
5 76
É subgrafo de G?
1 3
5 7
É subgrafo de G?
2
6
Figueiredo – 2011
CliqueUm grafo completo “dentro” de outro grafo
mais precisamente...
Dado G = (V, E)
G' = (V', E') é um clique de G se
G' é subgrafo de G
G' é um grafo completo
Figueiredo – 2011
Clique ExemploDado G = (V, E)
1 32 4
5 76 8
1 2
5
É clique de G?
1 2
5 6
É clique de G?Qual é o maior clique de G?
32
76
Problema “difícil”: encontrar maior clique de um grafo
Figueiredo – 2011
ConexoGrafo está “conectado”
como definir mair precisamente?
Grafo G=(V, E) é conexo se
existe caminho entre qualquer par de vértices
Caso contrário, G é desconexo
1 32
5 76
1 32
5 76
Conexo? Conexo?
Figueiredo – 2011
ConexoProblema: Como saber se um grafo é conexo?
Como você resolveria este problema?
Veremos algoritmo (eficiente)em duas aulas...
Figueiredo – 2011
Componentes ConexosMaiores subgrafos “conectados” de um grafo
mais precisamente...
Exemplo:
Subgrafos maximais de G que sejam conexosmaximal: subconjunto que maximiza a propriedade, no caso subgrafo conexo
6
78
2 36
5 97
8
1
42
5
1
4
Componenteconexo?
Componenteconexo?
Recommended