Please enable JavaScript.
Coggle requires JavaScript to display documents.
M (Caminhos e ciclos, Grafos, Representação de grafos em matrizes, Pesos…
M
Caminhos e ciclos
Um caminho infinito é uma sequência alternante do mesmo tipo descrito acima, mas sem um primeiro ou último vértice, enquanto um caminho semi-infinito tem um primeiro vértice {\displaystyle v{0}}v{0} mas nenhum último vértice.
Um grafo ponderado, também chamado de valorado, associa um valor (peso) a cada aresta no grafo. O peso de um caminho em um grafo ponderado é a soma dos pesos das arestas percorridas.
Um ciclo de comprimento r é um caminho constituído por r + 1 vértices, onde o primeiro vértice é igual ao último. Note que a escolha do vértice inicial em um ciclo é arbitrária.
Um caminho sem vértices repetidos é chamado de caminho simples e um ciclo sem vértices repetidos com exceção do inicial/final é um ciclo simples. Por vezes o termo "simples" é omitido de "caminho simples" e "ciclo simples", embora essa não seja a regra.
Um grafo é conexo se há caminhos contendo cada par de vértices, ou seja, se para quaisquer dois vértices, existe um caminho que começa em um e termina no outro.
Um gráfico direcionado é fortemente conectado se há caminhos direcionados opostos contendo cada par de vértices.
Um caminho que não há arestas do grafo conectando dois vértices não consecutivos é chamado de caminho induzido.
Um caminho que passa uma única vez em todos os vértices do grafo é conhecido como um caminho hamiltoniano.
-
Dois caminhos são independentes nos vértices se eles não têm qualquer vértice em comum. Da mesma forma, dois caminhos são independente nas arestas se eles não têm qualquer aresta em comum. Dois caminhos independentes nos vértices são independentes nas arestas, mas o inverso não é necessariamente verdadeiro.
A distância entre dois vértices em um grafo é o comprimento do caminho mais curto entre eles, se houver, caso contrário, a distância é infinita.
-
Grafos
Um grafo é uma que representação abstrata de um conjunto de objetos e das relações existentes entre eles. É definido por um conjunto de nós ou vértices, e pelas ligações ou arestas, que ligam pares de nós. Uma grande variedade de estruturas do mundo real podem ser representadas abstratamente através de grafos.
-
-
-
-
-
