Grafo

Grafo

Representação gráfica de um problema
1. Formas para representar elementos do problema
2. Setas para representar ligações entre elementos
Conceitos
1. Ordem = número de vértices
2. Grau = número de arestas
  1. Grau mínimo = menor grau entre os vértices
  2. Grau máximo = maior grau entre vértices
  3. Grau médio = média dos graus entre os vértices
  4. Grau de recepção = número de arestas que chegam no vértice
  5. Grau de emissão = número de arestas que saem no vértice
3. "Pontas" do grafo são chamadas de vértices
4. Conexões entre vértices são arestas
Tipos
1. Digrafo (grafo orientado)
  1. Arcos são setas que indicam o fluxo
  2. Arestas (conexões) são chamadas de arcos
  3. Possui obrigatoriamente pares ordenados
    1. As ligações têm um fluxo que deve ser respeitado
2. Grafo Simples
  1. Arestas são apenas linhas que ligam os vertices
  2. Os pares não possuem ordem definida
Representação
1. Matriz de adjacências
  1. Indica quais vértices estão ligados
    1. 1. Na imagem v1 e v2 estão ligados, então coloca-se 1 no índice correspondente, v1 e v4 não estão, portanto coloca-se 0
  2. Em grafos não ordenados há simetria entre os elementos
    1. Utiliza-se apenas a matriz triangular superior ou inferior para economizar memória
  3. Desvantagem
    1. Ocupa muito espaço (todas as relações precisam ser listadas)
      1. Se há poucas arestas grande parte da matriz é ocupada com 0, portanto é inútil
    2. Não é capaz de representar grafos orientados
  4. Propriedades
    1. Representa um grafo sem ambiguidade
    2. Simétrico para grafo não direcionado
    3. Número de posições de memória é n², onde n é o número de vértices
      1. Alto custo para armazenamento
    4. Tempo de processamento é constante, não aumenta conforme o número de vértices/arestas
      1. Sempre eficiente pois acessa diretamente o índice x e y da matriz
  5. Grafos ponderados
    1. O peso do arco do nó IxJ é colocado na matriz
2. Matriz de incidências
  1. Indica relação entre vértices e arestas
    1. Linhas são vértices e colunas são arestas
      1. Na imagem v1 e v2 estão conectados pela aresta e1, portanto coloca-se 1 nos dois índices
      2. Para grafos orientados é possível marcar as relações de forma diferente para indicar origem e destino do arco
        +1 indica origem -1 indica destino
      3. Grafos ponderados
        O peso do arco é inserido na matriz com valor positivo ou negativo para indicar destino e origem, respectivamente
  2. Propriedades
    1. Tamanho VxA
    2. Necessário "varrer" a coluna até achar a conexão entre as arestas
3. Lista de adjacências
  1. Vetor que indica as ligações entre os vértices
    1. Cada posição representa um vértice e possui uma lista de conexões
      1. Cada nó na lista representa uma conexão
  2. Para grafos simples as conexões são repetidas na lista
  3. Para digrafos as conexões são sinalizadas apenas na origem
  4. Desvantagens
    1. Custo relativo ao número de ligações no vértice
      1. Se um vértice liga a outros 4, então o custo para percorrer a lista é 4 (maior grau do grafo)
  5. Grafos ponderados
    1. O peso do arco é colocado no nó da lista

Next up

Description

Resource summary

Media attachments

Similar

	Created by Paulo Stanize over 7 years ago