• Grafo
  • O que é um Grafo
  • Grau de uma Vértice
  • Aplicações
• Terminologia de Grafos
  • Grafo completo
  • Grafo Direcionado ou Orientado
  • Laço
  • Multigrafo
  • Grafo Simples
  • Ordem de um grafo
  • Sobre os Graus dos Vértices de um Grafo
  • Subgrafo
  • Passeio
  • Trilha
  • Caminho
  • Grafos Conexos/Desconexos
• Árvores
  • Árvore Livre
  • Floresta
  • Árvore Binária
  • Observações
  • Percursos
  • Caso de aplicação

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.