Please enable JavaScript.
Coggle requires JavaScript to display documents.
M10 - Coggle Diagram
M10
Grafos:
Grafo é uma estrutura formada pelo conjunto (não vazio) dos vértices e o conjunto aresta. Temos que: G = {V,A}.
Vértices:
São os pontos no plano.
Arestas:
Caminho entre 2 vertices.
Classificação:
Os grafos são classificados como:
Grafos não direcionados:
Um grafo é não direcionado se todas as suas arestas não são direcionadas. Ao conectarmos dois vértice, u e v, à uma aresta não direcionada, dizemos que: (u,v) == (v,u), ou seja, o caminho de u para v é o mesmo de v para u.
Grafos direcionados (dígrafos):
Ao conectarmos 2 vértices consecutivos, v e u, por uma aresta direcionada, temos então que: (v,u)!=(u,v), ou seja, a aresta que liga (v,u) é diferente da que liga (u,v), pois levamos em consideração seu sentido.
Propriedades:
1) Número máximo de aresta:
O número máximo de arestas em um grafo é dado por E = (v*(v-1))/2, onde v é o número de vértices.
2) Gráficos Ponderados:
São grafos com números (pesos/custos) atribuídos às suas arestas. Em matemática discreta usamos essa abordagem para encontrar o caminho mais curto se baseando pelo custo de cada aresta.
2) Caminho:
Um caminho do vértice u para o vértice v de um grafo, pode ser definido como uma sequencia de vértices adjacentes (conectados por uma aresta) que começa em u e termina em v.
Caminho Simples:
Quando todos os vértices de um caminho são distintos.
Comprimeto:
O comprimento do caminho (número total de arestas) é dado pelo número total de vértices que define o caminho menos 1.
3) Conexo:
Um grafo é dito conexo se para cada par de seus vértices u e v
existe um caminho de u a v, caso contrário, ele é desconexo.
4) Cíclico:
Um grafo é dito cíclico se existe um caminho que começa e termina
no mesmo vértice sem repetição de arestas. Caso contrário, é acíclico.
Representações de grafo:
Adjacency Matrix:
É uma matrix nxn, onde n é a quantidades de vértices. Cada linha e cada coluna representa um vértice. Um vértice localizado na coluna A e outro vértice localizado na linha C são conectados se a referência na matriz na posição, coluna A e linha C, for igual 1. Caso seja 0, não serão conectados.
Adjacency lists:
São uma coleção de listas ligadas, uma para cada vértice, onde nelas contém os vértices adjacentes ao vértice principal (vértice da lista), isto é, todos os vértices conectados ao vértice principal por uma aresta.
Travessia de Grafos:
Corresponde a dois algoritmos
que processam sistematicamente todos os vértices e arestas de um grafo.
Depth-First Search (DFS) ou Pesquisa em profundidade:
O algoritmo começa num nó arbitrário e explora tanto quanto possível cada um dos seus ramos, visitando cada nó por onde passa como visitado, antes de retroceder.
Breadth-First Search(BFS) ou Pesquisa em largura:
A busca em largura começa por um vértice. O algoritmo visita este vértice, depois visita todos os vizinhos deste vértice, depois todos os vizinhos dos vizinhos, e assim por diante...
Ordenação topológica:
É uma permutação dos vértices de um díagrafo acíclico de forma que para qualquer aresta (vi,vj), temos que i<j.