Um grafo é um par de conjuntos G = (V,A), em V é o conjunto de vértices e A é o conjunto de arestas.
V = {6A,6B,7A,7B,8A,8B}
Nota: Os vértices são os pontos
A = { (6A,7A),(6A,7B),(6A,8B), (6B,7A),(6B,8A),(6B,8B), (7B,8A),(7B,8B), (8A,8B) } OU
6A -> {(6A,7A),(6A,7B),(6A,8B)}
6B -> {(6B,7A),(6B,8A),(6B,8B)}
7A -> {(6A,7A),(6B,7A)}
7B -> {(6A,7B),(7B,8A),(7B,8B)}
8A -> {(6B,8A),(7B,8A),(8A,8B)}
8B -> {(6A,8B),(6B,8B),(7B,8B)}
Nota: As arestas são as ligações desses pontos
São vértices ligadas por uma aresta. A aresta que ligam as vértices são chamadas de arestas incidentes
Nesse caso 6A e 7A são adjacentes
São vértices não possuem uma aresta fazendo a ligação entre elas.
Nesse caso 6A e 6B são não adjacentes
Número de vértices = |V| Número de arestas = |A|
Nesse caso esse grafo possui |V| = 6 e |A| = 9
É o número de vezes que as arestas incidem sobre o vértice, ou seja, o número de arestas que ligam esse vértice a outro.
Grau de um Vértice = d(v)
Utilizando o grafo anterior: d(6A) = 3 d(6B) = 3 d(7A) = 2 d(7B) = 3 d(8A) = 3 d(8B) = 4
- Identificar o melhor caminho em uma empresa de logística ou o menor caminho.
- Identificar como um caminhão de lixo pode passar por um bairro sem repetir um quarteirão
- Encontrar o menor percurso em uma rede de computadores
- Encontrar dados em comum entre usuários de uma rede social
É quando todas as arestas e vértices se encontram conectadas, usando o exemplo anterior teriamos: 6A -> {(6A,6B),(6A,7A),(6A,7B),(6A,8A),(6A,8B)} 6B -> {(6A,6B),(6B,7A),(6B,7B),(6B,8A),(6B,8B)} 7A -> {(6A,7A),(6B,7A),(7A,7B),(7A,8A),(7A,8B)} 7B -> {(6A,7B),(6B,7B),(7A,7B),(7B,8A),(7B,8B)} 8A -> {(6A,8A),(6B,8A),(7A,8A),(7B,8A),(8A,8B)} 8B -> {(6A,8B),(6B,8B),(7A,8B),(7B,8B),(8A,8B)}
Denotado por Kn, onde n é o número de vértices
É um grafo em que cada aresta tem uma orientação
Nesse caso a ordem das vértices que conectam a aresta importa.
então tendo um grafo onde as arestas estão definidas como:
A = {(1A,2B),(2B,1B),(1A,3A),(3A,1B)}
(1A,2B) é diferente de (2B,1A), sendo assim: 1A -> 2B existe 2B -> 1A não existe
Se na definição do meu grafo eu incluisse (2B,1A), nesse caso ele existiria: A = {(1A,2B),(2B,1A),(2B,1B),(1A,3A),(3A,1B)}
1A <-> 2B, ou seja, tanto 1A -> 2B quanto 2B -> 1A existem
No caso dos Grafos Direcionais, cada vértice terá um grau de entrada e um grau de saída.
Usando o segundo caso anterior de um Grafo Direcionado, teriamos:
d in (1A) = 1 -> (2B,1A) d out (1A) = 2 -> (1A,2B),(1A,3A) d in (3A) = 1 -> (1A,3A) d ou (3A) = 1 -> (3A,1B)
É uma aresta que liga um vértice a ele mesmo.
A = {(1A,2B),(1A,1A),(2B,1B),(1A,3A),(3A,1B)}
1A - 1A
Grafo onde duas vértices podem estar ligadas por mais de uma aresta, nesse caso dizemos que estas são arestas paralelas ou arestas múltiplas.
Grafos sem laços ou arestas múltiplas.
É a quantidade de vértices que ele possui
É o vértice de grau 0, ou seja, nenhuma aresta incidindo sobre ele
É o vértice que possui apenas uma aresta incidindo sobre ele
Denotado por delta minúsculo é o menor Grau de um vértice, no caso será pego d(V) com a menor incidencia de arestas Denotado por delta maiúsculo é o maior Grau de um vértice, no caso será pego d(V) com a maior incidencia de arestas
É um Grafo x contido em um Grafo y, ou seja, x pertence a y
C = contido em V() = vértice A() = aresta
x C y se V(x) C V(y) e A(x) C A(y)
É uma sequência de arestas do tipo (V0,V1),(V1,V2),(V2,V3),...(Vs-1,Vs). V0 é o início do passeio e Vs é o fim. s é o comprimento do passeio.
É uma sequência onde as arestas não se repetem, ou seja, todas as arestas do passeio são distintas.
É quando V0 da trilha é igual Vs, ou seja, é quando termina na mesma vértice em que começou.
É uma sequência onde as vértices não se repetem, ou seja, todas as vértices da trilha são distintas.
É um caminho onde V0 = Vs
Um grafo é conexo se existe um caminho entre qualquer par de vértices. Um grafo é desconexo quando não existe um caminho entre qualquer par de vértices.
Anterior | Próximo