Tour theory
Introduction
In graph theory, a walk (in English, walk, and sometimes also translated as tour)[1] is a succession of vertices "Vertex (graph theory)") and edges "Edge (graph theory)") within a graph, which begins and ends at vertices, such that each vertex is incident with the edges that follow and precede it in the sequence.[2] Two vertices are connected or accessible if there is a path that forms a trajectory to get from one to the other; Otherwise, the vertices are disconnected or inaccessible.[1].
Two vertices can be connected by multiple paths. The length of a path is its number of edges. Thus, in an undirected graph, adjacent vertices are connected by a path of length 1, the second neighbors "Neighborhood (graph theory)") by a path of length 2, and so on. An undirected graph is connected if all its vertices are connected through a path.[2] A connected graph whose vertices and edges allow a path to be defined is a path graph.
formal definition
Given a graph, a path is a sequence of vertices and edges such that (in case the graph is undirected), or (in case it is directed), for all . The length of the path is .[2][1].
Types of related trajectories
Contenido
Existen varios conceptos derivados del de camino:[2].
Trajectories in directed graphs
The above definitions of paths also apply to directed graphs, as long as the paths respect the direction of the edges between each vertex and the next. However, if in a directed graph you want to ignore the direction of the edges and consider their trajectories as if it were an undirected graph, then the paths are known as semipaths, the paths as semipaths, the cycles as semicycles, etc.[1].
Trajectories in weighted graphs
In the context of social network analysis, for social networks represented as weighted graphs, that is, with weights on the edges, the value of a path or half-path can be defined as the minimum value of all the edges it contains.[3] A path at level c is a path between a pair of vertices such that all the edges it contains are greater than or equal to the value c.[4] Two vertices are accessible at level c if there is a path at level c between them.[5] The length of a path in a weighted graph corresponds to the sum of the values of the edges included in said path.[6][1].
References
- [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.: http://repositorio.utm.mx:8080/jspui/handle/123456789/175
- [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. Falta la |url= (ayuda).: https://dx.doi.org/10.1016%2F0378-8733%2880%2990005-2
- [4] ↑ Doreian, P. (1969). «A note on the detection of cliques in valued graphs». Sociometry 32. pp. 237-242. doi:10.2307/2786266. Falta la |url= (ayuda).: https://dx.doi.org/10.2307%2F2786266
- [5] ↑ Doreian, P. (1974). «On the connectivity of social networks». Journal of Mathematical Society 3. pp. 245-258. doi:10.1080/0022250X.1974.9989837. Falta la |url= (ayuda).: https://dx.doi.org/10.1080%2F0022250X.1974.9989837
- [6] ↑ Flament, C. (1972) [1963]. «Teoría de grafos y estructura de grupos» [Applications of graph theory to group structure]. Madrid: Tecnos. Falta la |url= (ayuda).