Usuário(a):MGromov/Testes68

Página inicial: Testes

Edições completas: Mecânica estatística • Modelo Hodgkin-Huxley • Neurociência computacional • Modelo probabilístico para redes neurais • Teoria de campo médio • Modelo FitzHugh–Nagumo • Processo Lévy • Cadeias de Markov • Processo de Poisson • Galves–Löcherbach model • Stochastic chains with memory of variable length • Lesão do plexo braquial • Somatotopia • Função densidade • Modelos de grafos aleatórios exponenciais • Processo de Gram-Schmidt • Equação de Chapman–Kolmogorov • Predefinição:Processos estocásticos • Algoritmo de autovalores • Transição de fase • Hipótese do cérebro crítico • Critical brain hypothesis • Passeio aleatório • Plasticidade sináptica • Potencial pós-sináptico excitatório • Potencial pós-sináptico inibitório • Modelo de Morris-Lecar • Plexo braquial • Processo gaussiano • Campo aleatório de Markov • Eletroencefalografia • Modelo de Hindmarsh-Rose • Sistemas de partícula em interação • Medida de Gibbs • Nervo escapular dorsal • Nervo radial • Nervo peitoral lateral • Nervo musculocutâneo • Medida de Dirac • Nervo torácico longo • Sigma-álgebra • Nervo peitoral medial • Nervo ulnar • Potencial evocado • Estimulação magnética transcraniana repetitiva • Teorema de Donsker • Desigualdade de Boole • Codificação neural • Aprendizado de máquina • Independência condicional • Inferência estatística • Nervo subclávio • Nervo supraescapular • Nervo mediano • Nervo axilar • Movimento browniano geométrico • Caminho autoevitante • Tempo local • Nervo subescapular superior • Nervo toracodorsal • Nervo subscapular inferior • Caminho (teoria dos grafos) • Campo aleatório • Lei do logaritmo iterado

Edições em andamento: Nervo cutâneo medial do braço (N) • Nervo cutâneo medial do antebraço (N) • Cérebro estatístico (N) • Statistician brain • Distribuição de probabilidade condicional (N) • Esperança condicional (N) • Integral de Itō (N) • Martingale • Variação quadrática (N) • Processo Ornstein–Uhlenbeck • Ruído branco • Teoria ergódica • Avalanche neuronal (N) • Teoria da percolação (N) • Função totiente de Euler • Ruído neuronal (N) • Distribuição de Poisson • Córtex cerebral • Estímulo (fisiologia)

Referência: Path (graph theory) e Caminho (teoria dos grafos)

Em teoria dos grafos, um caminho em um grafo é uma sequência finita ou infinita de vértices conectados por uma sequência de arestas que, na maioria das definições, são todos diferentes uns dos outros. O primeiro vértice é chamado de vértice inicial e o último é chamado de vértice final. Em um gráfico direcionado, um caminho dirigido (às vezes chamado de dipath^[1]) é uma sequência de arestas que se conectam a uma sequência de vértices, mas com a restrição de que as arestas sejam todas dirigidas no mesmo sentido.

Os caminhos são conceitos fundamentais de teoria de grafos, descrito nas seções introdutórias da maioria dos textos sobre teoria dos grafos.

Definição formal

Um passeio de distância $k$ em um grafo é uma sequência alternante de vértices e arestas $v_{0},e_{0},v_{1},e_{1},v_{2},\ldots ,v_{k-1},e_{k-1},v_{k}$ , que começa e termina em vértices. Um caminho é um passeio na qual todos os vértices (exceto possivelmente o primeiro e o último) são distintos, enquanto uma trilha é um passeio no qual todas as arestas (ou edges, em inglês) são distintas.

Certos autores requerem que as arestas e vértices sejam distintos. Alguns, porém, não procedem dessa forma, preferindo usar o termo caminho simples ao invés para se referir a um caminho que não repete vértices. Um caminho simples em um grafo $G$ é uma sequência de vértices de $G$ , por exemplo, $({v_{i_{1}},v_{j_{1}}},...,{v_{i_{r}},v_{j_{r}}})$ , tal que $v_{j_{a}}=v_{i_{a+1}}$ para todo $1\leq a\leq r-1$ .

Se o grafo é não dirigido, então os nós de $e_{i}$ são $v_{i}$ e $v_{i+1}$ . Se o grafo é dirigido, então $e_{i}$ é um arco de $v_{i}$ a $v_{i+1}$ .

Tipos de caminhos

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 $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.
Um ciclo simples que envolva todos os vértices de um grafo é chamado de ciclo 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.
O diâmetro do grafo é a maior distância (definida acima) entre os pares de vértices do grafo.

Encontrando caminhos

Vários algoritmos existem para encontrar os caminhos mais curto e mais longo em grafos, com a diferença de que o primeiro problema é computacionalmente mais fácil do que o último.

O algoritmo de Dijkstra produz uma lista de caminhos mais curtos de um vértice "fonte" a todos os outros vértices em grafos direcionados e não-direcionados com pesos não-negativos nas arestas (ou nenhum peso), enquanto o algoritmo de Bellman–Ford pode ser aplicado para grafos dirigidos com pesos negativos nas arestas. O algoritmo de Floyd–Warshall pode ser usado para encontrar o menor caminho entre todos os pares de vértices em grafos ponderados dirigidos.

Veja também

Referências

↑ Graph Structure Theory: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, Held June 22 to July 5, 1991,, p.205

Bibliografia

Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. [S.l.]: North Holland. pp. 12–21. ISBN 0-444-19451-7
Diestel, Reinhard (2005). Graph Theory 3rd ed. [S.l.]: Graduate Texts in Mathematics, vol. 173, Springer-Verlag. pp. 6–9. ISBN 3-540-26182-6
Gibbons, A. (1985). Algorithmic Graph Theory. [S.l.]: Cambridge University Press. pp. 5–6. ISBN 0-521-28881-9
Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; Schrijver, Alexander (Eds.) (1990). Paths, Flows, and VLSI-Layout. [S.l.]: Algorithms and Combinatorics 9, Springer-Verlag. ISBN 0-387-52685-4

Categoria:Conectividade de grafos

[1] Graph Structure Theory: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, Held June 22 to July 5, 1991,, p.205

[1]