GRAFOS

GRAFOS

1. Definição

   • Conjunto de objetos, ligados por arestas
   • Permite codificar relacionamentos

2. Aplicação

   • Solucionar problemas e buscar desenvolver algoritmos mais eficientes

3. Composição

   • Vértice
   • Aresta

4. Propriedades do Grafo

   • Direção das arestas
     • Grafo direcionado ou Dígrafo
       • Se uma aresta liga A e B, podemos ir de A para B, mas não ao contrário
     • Grau de um vértice
       • Número de arestas que chegam ou partem dele
     • Laço
       • Se o vértice de partida é o mesmo que o de chegada
     • Caminho
       • Uma sequência de Vértices, sempre existe uma aresta ligando o vertice anterior ao próximo
     • Ciclo
       • É um caminho que começa e termina no mesmo vértice
     • Arestas múltiplas
       • Permite mais de uma resta conectando o mesmo par de vértices

5. Tipos de Grafo

   • Grafo Trivial
     • Único vértice, sem aresta
   • Grafo Simples
     • Grafo não direcionado, sem laços e arestas
   • Grafo completo
     • Grafo simples, cada vértice se conecta a todos vértices
   • Grafo Regular
     • Todos os vértices possuem o mesmo grau
   • Grafo bipartido
     • Vértices podem ser divididos em dois conjuntos
   • Grafo conexo
     • Um caminho partindo qualquer vértices ate qualquer outro vértice do grafo
   • Grafo desconexo
     • Não existe um caminho ligando dois vértices
   • Grafo Euleriano
     • Possui um ciclo que visita cada aresta apenas uma vez
   • Grafo semi euleriano
     • Possui um caminho que visita cada aresta apenas uma vez

6. Representação

   • Matriz de Adjacência
   • Lista de Adjacência