Teoria dos Grafos

Teoria dos Grafos

1. Um grafo é um conjunto de objetos chamados vértices ou nós, ligados por retas chamadas arestas. Um grafo G é formado pelo par de conjunto V e E, sendo V o conjunto de vértices de G, e E

   • Um grafo pode ser representado por G = (V,E) ou G = (V(G), E(G)) ou G(V,E).
     • Qual a utilização na computação?
       • O Grafo é utilizado para solucionar problemas computáveis e buscar o desenvolvimento de algoritmos mais eficientes
   • Um grafo é composto por
     • Vértice
       • É uma das entidades representativa, podendo ser pessoa ou objetos
     • Arestas
       • Também chamado de "Arco" é o item de associação entre dois ou mais vértices
   • Propriedades do Grafo
     • Direções do Grafo
       • Direcionados ou Dígrafo
         • É um grafo que contem uma direção indicando o sentido da aresta
       • Não direcionados
         • São grafos que não existe nem uma orientação de direção.
     • Grau de um vértice: Denomina-se do numero de arestas que chegam ou que saem do vértice.
     • Grau de um Vértice: É o número de aresta que entram ou que saem de um vértice
     • Laços: É chamado de laço quando um vértice tem o porto de partida com a mesma origem de chegada.
     • Caminho: É uma sequência de vértices de modo que existe sempre uma aresta ligando o vértice anterior com o seguinte
     • Ciclo: É um caminho que começa e termina no mesmo vértice
     • Arestas múltiplas: É um grafo que permite mais de uma aresta conectando o mesmo par de vértices
   • Tipo de Grafos
     • Grafo trivial: é um grafo com um único vértice e sem arestas
     • Grafo simples: é um grafo não direcionado, sem laços e sem arestas paralelas
     • Grafo completo: é um grafo simples onde cada vértice se conecta a todos os outros vértices
     • Grafo regular: é um grafo onde todos os vértices possuem o mesmo grau
     • Subgrafo: um grafo Gs(Vs, As) é chamado de subgrafo de G(V,A) se: Vs está contido em V As está contido em A
     • Grafo bipartido: é um grafo cujos vértices podem ser dividido em dois conjuntos
     • Grafo conexo: existe um caminho partindo qualquer vértices até qualquer outro vértice do grafo
     • Grafo desconexo: não existe um caminho ligando dois vértices selecionados
     • Grafos isomorfos: dois grafos, "G1(V1,A1)" e "G2(V2,A2)", são ditos isomorfos se existe uma função que faça o mapeamento de vértices e arestas de modo que os dois grafo se tornem coincidentes
     • Grafo ponderado: é o grafo que possui "pesos" associados a cada uma de suas arestas
     • Grafo hamiltoniano: é o grafo que possui um caminho que visita cada vértice apenas uma vez
     • Grafo Euleriano: é o grafo que possui um ciclo que visita cada aresta apenas uma vez
     • Grafo semi-euleriano: é o grafo que possui um caminho que visita cada "aresta" apenas uma vez
   • Representação dos Grafos
     • Matriz de Adjacência
     • Lista de Adjacência