To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Camino (teoría de grafos)

De Wikipedia, la enciclopedia libre

En teoría de grafos, un camino (en inglés, walk, y en ocasiones traducido también como recorrido)[1]​ es una sucesión de vértices y aristas dentro de un grafo, que empieza y termina en vértices, tal que cada vértice es incidente con las aristas que le siguen y le preceden en la secuencia.[2]​ Dos vértices están conectados o son accesibles si existe un camino que forma una trayectoria para llegar de uno al otro; en caso contrario, los vértices están desconectados o bien son inaccesibles.[1]

Dos vértices pueden estar conectados por varios caminos. La longitud de un camino es su número de aristas. Así, en un grafo no dirigido, los vértices adyacentes están conectados por un camino de longitud 1, los segundos vecinos por un camino de longitud 2, y así sucesivamente. Un grafo no dirigido es conexo si todos sus vértices están conectados a través de un camino.[2]​ Un grafo conexo cuyos vértices y aristas permiten definir un camino es un grafo camino.

Definición formal

Dado un grafo , un camino es una sucesión de vértices y aristas tales que (en caso de que el grafo sea no dirigido), o bien (en caso de que sea dirigido), para todo . La longitud del camino es .[2][1]

Tipos de trayectorias relacionadas

Conceptos de conectividad en grafos, derivados de la noción de camino. En gris se mencionan traducciones alternativas del castellano. En cursivas el término original en inglés.
Conceptos de conectividad en grafos, derivados de la noción de camino. En gris se mencionan traducciones alternativas del castellano. En cursivas el término original en inglés.

Existen varios conceptos derivados del de camino:[2]

  • Un recorrido (en inglés, trail, a veces traducido como rastro)[1]​ es un camino sin aristas repetidas.
  • Un camino cerrado es un camino cuyo vértice inicial y final coinciden.
  • Un camino abierto es un camino cuyo vértice inicial y final no coinciden.
  • Un camino simple (en inglés, path, a veces traducido como camino)[1]​ es un camino sin vértices repetidos, salvo quizás el primero y el último (por lo tanto, es un tipo especial de recorrido, pues tampoco tiene aristas repetidas).
  • Un circuito (en inglés, circuit) es un recorrido que además es un camino cerrado.
  • Un ciclo (en inglés, cycle) es un camino simple que además es un camino cerrado.
  • Un ciclo euleriano es un ciclo que pasa por todas las aristas del grafo una única vez.
  • Un ciclo hamiltoniano es un ciclo que pasa por todos los vértices del grafo una única vez (en caso de que el vértice inicial y final no coinciden, se suele hablar también de camino hamiltoniano).

Trayectorias en grafos dirigidos

Las definiciones de trayectorias anteriores también se aplican a grafos dirigidos, siempre y cuando los caminos respeten la dirección de las aristas entre cada vértice y el siguiente. Sin embargo, si en un grafo dirigido se desea prescindir de la dirección de las aristas y considerar sus trayectorias como si se tratara de un grafo no dirigido, entonces a los caminos se les conoce como semicaminos, a los recorridos como semirrecorridos, a los ciclos como semiciclos, etc.[1]

Trayectorias en grafos ponderados

En el contexto del análisis de redes sociales, para las redes sociales representadas como grafos ponderados, es decir, con pesos en las aristas, el valor de un camino o semicamino puede definirse como el valor mínimo de todas las aristas que contiene.[3]​ Un camino a nivel c es un camino entre un par de vértices tal que todas las aristas que contiene son mayores o iguales al valor c.[4]​ Dos vértices son accesibles a nivel c si existe un camino a nivel c entre ellos.[5]​ La longitud de un camino en un grafo ponderado corresponde a la suma de los valores de las aristas incluidas en dicho camino.[6][1]

Véase también

Referencias

  1. a b c d e f g Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.
  2. a b c d Carrasco Pacheco, José Luis; Contreras Ordaz, Marco Antonio (2017). Modelado dinámico por inspección para convertidores de potencia CD a CD commutados: Un enfoque basado en grafos. Universidad Tecnológica de la Mixteca. Consultado el 25 de abril de 2021. 
  3. Peay, E. R. (1980). «Connectedness in a general model for valued networks». Social Networks 2. pp. 385-410. doi:10.1016/0378-8733(80)90005-2. 
  4. Doreian, P. (1969). «A note on the detection of cliques in valued graphs». Sociometry 32. pp. 237-242. doi:10.2307/2786266. 
  5. Doreian, P. (1974). «On the connectivity of social networks». Journal of Mathematical Society 3. pp. 245-258. doi:10.1080/0022250X.1974.9989837. 
  6. Flament, C. (1972) [1963]. «Teoría de grafos y estructura de grupos» [Applications of graph theory to group structure]. Madrid: Tecnos. 

Bibliografía

  • Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053. 
Esta página se editó por última vez el 1 may 2022 a las 20:26.
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.