Please enable JavaScript.
Coggle requires JavaScript to display documents.
27-31 Grafos - Coggle Diagram
27-31 Grafos
definição
informal
Coleção de pontos num plano chamados de "verticies" ou "nodos" alguns destes são conectados por segmentos de linhas e são chamados de "arestas" ou "arcos"
formal
Um grafo G = (V,E) é definido por um par de conjuntos: um finito não vazio de itens chamados vertices (V) e um conjunto (E) de pares desses itens chamados arestas
Se um par de vertices é não ordenado isso é um par de vertices (u,v) é o mesmo que (v,u) nós dizemos que u e v são adjacentes e são conectados por uma aresta não direcionada
Chama-se os vertices u e v de pontos finais da aresta (u,v) e u e v incidentes à essa aresta. A aresta (u,v) é incidente a seus pontos finais u e v
-
Se um par de vertices (u,v) não é o mesmo que (v,u) diz-se que a aresta(u,v) é direcionada do vertice u, chamado de cauda da aresta, ao vertice v, chamado de cabeça da aresta
Também se diz que a aresta (u,v) sai de u e entra em v
-
-
-
-
Um grafo com relativamente poucas arestas possíveis faltando é chamado de denso; um grafo com poucas arestas em relação ao número de seus vértices é chamado esparso
Representação
-
Listas de adjacencia
Uma coleção de listas encadeadas uma para cada vertice contendo todos os vertices adjacentes, isso é ligados por uma aresta, ao vertice da lista
-
-
Caminhos ou ciclos
Um caminho de um vertice u até o v de um grafo pode ser definido como uma sequecnia de vertices adjacentes que começam em u e acabam em v
-
o comprimento de um caminho é o numero total de vertices na sequencia que define o caminho menos 1 que é o mesmo que o numero de arestas no caminho
um caminho direcionado éuma sequencia de vertices na qual a direção das arestas é do vertice anterior ao proximo
-
Um ciclo é um caminho de comprimento positivo que começa e termina no mesmo vertice e não se passa pela mesma aresta mais de uma vez
-