Logo Passei Direto
Buscar
Material
páginas com resultados encontrados.
páginas com resultados encontrados.

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Prévia do material em texto

GRAFOS – conceitos básicos
O que é um grafo?
Um grafo é uma representação gráfica de elementos de dados e das conexões entre alguns destes itens.
Uma árvore é um caso particular de grafo.
Outros exemplos: rotas de uma companhia aérea, sistema de distribuição de água, luz e internet.
Qual a importância computacional do uso de grafos?
É bastante abrangente o uso de grafos na computação em áreas como:
Análise de planejamento de projetos
Cibernética
Redes de Computadores
Circuitos Eletrônicos.
Sistemas de recomendação
Redes sociais
Qual a importância computacional do uso de grafos?
Qual a importância computacional do uso de grafos?
Definição
Um grafo é uma tripla (N, A, g) em que:
N = um conjunto não vazio de vértices (nós ou nodos)
A = um conjunto de arestas (arcos)
g = uma função que associa cada aresta a a um par não-ordenado x-y de vértices chamados extremos de a
Adjacência
Dois vértices são vértices adjacentes se forem os extremos de uma mesma aresta.
Duas arestas que possuem um extremo em comum são ditas arestas adjacentes.
Vértice isolado não é adjacente a qualquer outro vértice.
7
Laços
Um laço é uma aresta com extremos n-n para algum nó n.
Laços
Um laço é uma aresta com extremos n-n para algum nó n.
Paralelismo
Duas arestas que tem os mesmos extremos são ditas arestas paralelas. 
7
Grau
O grau de um vértice é número de arestas que o tem como ponto extremo.
Como a função g relaciona cada aresta a seus extremos, cada aresta tem um único par de pontos extremos.
7
Grafos completos
Um grafo completo é aquele no qual todos os vértices distintos dois a dois são adjacentes.
Subgrafo
Um subgrafo de um grafo consiste em um conjunto de vértices e um conjunto de arestas que são subconjuntos de vértices e arestas originais, nos quais os extremos de qualquer aresta são os mesmos que no grafo original.
Caminho
Um caminho é uma sequência de vértices e arestas, onde para cada i, os extremos da aresta ai  são ni-ni+1. 
O comprimento  de um caminho é o número de arestas que ele contém.
Conexão
Um grafo é conexo se houver um caminho entre quaisquer dois vértices.
Ciclos
Um ciclo é um caminho de algum vértice n até n de novo de forma que nenhum vértice ocorra mais de uma vez no caminho.
Um grafo sem ciclos é dito grafo acíclico.
7
Exercício
Trace um grafo que tenha:
os vértices {1,2,3,4,5}, 
as arestas {a1, a2, a3, a4, a5, a6} 
e a função 
g(a1)= 1-2, 
g(a2)= 1-3, 
g(a3)= 3-4, 
g(a4)= 3-4, 
g(a5)= 4-5, 
g(a6)= 5-5.
Encontre:
a - dois vértices que não sejam adjacentes;
b - um vértice que seja adjacente a ele mesmo;
c - um laço;
d - duas arestas paralelas;
e - o grau do vértice 3;
f - um caminho de comprimento 5;
g - um ciclo; 
h - Este grafo é completo?
i - Este grafo é conexo?
Grafos isomorfos
Dois grafos podem parecer muito diferentes em suas representações gráficas, mas serem, ainda assim, o mesmo grafo de acordo com nossa definição de grafo.
Os grafos apresentados anteriormente são os mesmos, pois tem os mesmos vértices, as mesmas arestas e a mesma função de associação de arestas e seus extremos.
Grafos isomorfos
Grafos isomorfos
Grafos isomorfos
Condições que garantem que um grafo não é isomorfo
Um grafo tem mais vértices que o outro;
Um grafo tem mais arestas que o outro;
Um grafo tem arestas paralelas e 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.
Os grafos abaixo são isomorfos?
Os grafos abaixo são isomorfos?
Grafos bipartidos
Seus vértices podem ser particionados em dois conjuntos não-vazios N1 e N2, tais que dois vértices x e y sejam adjacentes se, e somente se, x Є N1, e y Є N2. 
Se |N1| = m e |N2|= n, então este grafo é um bipartido completo Km,n 
Exercício
O grafo abaixo é um grafo bipartido? 
Se sim, ele é um grafo bipartido completo?
Qual uma outra forma de se desenhar este grafo?
1
4
5
2
6
3
Grafos planares
É um grafo que pode ser desenhado em um plano (folha de papel) e de forma que suas arestas se interceptem apenas em vértices.
Exercício
Demonstre planaridade em K4.
Demonstre planaridade em K5.
Exercícios
1 - Construir uma representação geométrica do grafo G = (V,E), onde:
V = {1,2,3,4,5,6}
E = {(1,3), (1,4), (1,5), (2,3),(2,4),(2,5),(3,5),(4,5)}
Exercícios
2 - Os amigos João, Pedro, Antônio, Marcelo e Francisco sempre se encontram para botar conversa fora e às vezes jogar dama, xadrez e dominó. As preferências de cada um são as seguintes: João só joga xadrez; Pedro não joga dominó; Antônio joga tudo; Marcelo não joga xadrez e dominó e Francisco não joga nada. 
Represente como um grafo bipartido.
Defina um subgrafo em que todos, menos Francisco, joguem ao mesmo tempo. 
Exercícios
3 - Identifique se os grafos a seguir são isomorfos:
Exercícios
3 - Identifique se os grafos a seguir são isomorfos:
Exercícios
3 - Identifique se os grafos a seguir são isomorfos:
Representação de Grafos
Matrizes de Adjacência
Uma linha para cada nó
Uma coluna para cada nó
Matriz de Adjacência
Desenhar o grafo representado pela matriz de adjacência abaixo:

Mais conteúdos dessa disciplina