Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos - Coggle Diagram
Grafos
Caminhos & Ciclos
Conectividade
Um grafo é conectado se para cada par de seus vértices (u,v) existe um caminho de u para v.
Se um grafo não é conectado, tal modelagem vai ter várias peças conectadas que vão ser chamadas de componentes conectados do grafo. Um componente conectado é um subgrafo máximo conectado de um determinado grafo.
Acíclicidade
Um ciclo é um caminho de tamanho positivo que começa e termina no mesmo vértice e não caminha pela mesma aresta mais do que uma vez. Um grafo sem ciclos é acíclico.
Um caminho de um vértice u a um vértice v de um grafo G é uma sequência de vértices adjacentes que começa com u e termina com v.
-
Grafo é, informalmente, uma coleção de pontos em um plano chamados nós/vértices e conectados por segmentos de linhas chamados arcos/arestas
Formalmente, um grafo é definido por um par de dois conjuntos: Um conjunto não vazio de vértices V e outro de pares desses vértices chamado arestas E (edges)
Se os pares de vértices são desordenados então (u,v) = (v, u). Dois vértices u e v são adjacentes se eles são conectados por uma aresta não direcionada.
-
Grafos com peso
Um grafo com peso é um grafo que possui números associados com suas arestas, esses números são chamados de pesos ou custos.
Ambas as representações de grafos podem ser adaptadas para acomodar grafos com pesos, a matriz de adjacência não será booleana, mas sim guardará o peso de cada aresta (Matriz de peso), enquanto a cada nó da lista de adjacência vai incluir o peso da aresta correspondente.
Tal definição de grafo não proíbe laços ou arestas conectando vértices a si mesmos. Mas, ao não ser que seja explicitamente dito, consideramos que grafos não possuem loops.
Representações
Matriz de adjacência
Um grafo de N vértices é representado por uma matriz booleana NxN com uma coluna e uma linha para cada vértice do grafo. Ai,j = Aj,i. Se existe uma aresta conectando um vértice i a um vértice j, então Ai,j = 1, caso não Ai,j = 0.
Lista de adjacência
Uma coleção de listas ligadas, uma para cada vértice, que contém todos os vértices adjacentes a esse vértice.