Read More
Date: 1-4-2022
1478
Date: 26-4-2022
1522
Date: 22-7-2016
1261
|
A path in a graph is a subgraph of that is a path graph (West 2000, p. 20). The length of a path is the number of edges it contains.
In most contexts, a path must contain at least one edge, though in some applications (e.g., defining the path covering number), "degenerate" paths of length 0 consisting of a single vertex are allowed (Boesch et al. 1974).
An -path is a path whose endpoints (vertices of degree 1) are the vertices with distinct indices and . (The symbols and are also commonly used.) A single -path may be found in the Wolfram Language using FindPath[g, s, t], while FindPath[g, s, t, kspec, n] finds at most paths of length kspec (where kspec may be Infinity and may be All).
For a simple graph, a path is equivalent to a trail and is completely specified by an ordered sequence of vertices. For a simple graph , a Hamiltonian path is a path that includes all vertices of (and whose endpoints are not adjacent).
The number of (undirected) -walks from vertex to vertex in a graph with adjacency matrix is given by the element of (Festinger 1949). In order to compute the number of graph paths, all closed -walks that are not paths must be subtracted.
The first few matrices of -paths can be given in closed form by
(1) |
|||
(2) |
|||
(3) |
(Luce and Perry 1949, Katz 1950, Ross and Harary 1952, Perepechko and Voropaev), where is the matrix formed from the diagonal elements of and denotes matrix element-wise multiplication.
Furthermore, the number of -cycles is related to by
(4) |
where denotes the trace.
Giscard et al. (2016) gave the formula for the path matrix giving the number of -paths from to as
(5) |
where the sum is over connected induced subgraphs of containing both and , denotes the number of neighbors of in (namely vertices of which are not in and such that there exists at least one edge from to a vertex of ), denotes the matrix trace, and is the th element of the th matrix power of the adjacency matrix of restricted to the connected induced subgraph , namely
(6) |
with .
Boesch, F. T.; Chen, S.; and McHugh, J. A. M. "On Covering the Points of a Graph with Point Disjoint Paths." In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). Berlin: Springer-Verlag, pp. 201-212, 1974.
Giscard, P.-L. and Rochet, P. "Enumerating Simple Paths from Connected Induced Subgraphs." 1 Jun 2016. https://arxiv.org/abs/1606.00289.
Giscard, P.-L.; Kriege, N.; and Wilson, R. C. "A General Purpose Algorithm for Counting Simple Cycles and Simple Paths of Any Length." 16 Dec 2016. https://arxiv.org/pdf/1612.05531.pdf.
Festinger, L. "The Analysis of Sociograms Using Matrix Algebra." Human Relations 2, 153-158, 1949.
Katz, L. "An Application of Matrix Algebra to the Study of Human Relations Within Organizations." Institute of Statistics, University of North Carolina, Mimeograph Series, 1950.
Luce, R. D. and Perry, A. D. "A Method of Matrix Analysis of Group Structure." Psychometrika 14, 95-116, 1949.
Perepechko, S. N. and Voropaev, A. N. "The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths."Roberts, B. and Kroese, D. P. "Estimating the number of Paths in a Graph." J. Graph Algorithms Appl. 11, 195-214, 2007.
Ross, I. C. and Harary, F. "On the Determination of Redundancies in Sociometric Chains." Psychometrika 17, 195-208, 1952.
Valiant, L. G. "The Complexity of Enumeration and Reliability Problems." SIAM J. Computing 8, 410-421, 1979.
West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 20, 2000.
|
|
دراسة يابانية لتقليل مخاطر أمراض المواليد منخفضي الوزن
|
|
|
|
|
اكتشاف أكبر مرجان في العالم قبالة سواحل جزر سليمان
|
|
|
|
|
اتحاد كليات الطب الملكية البريطانية يشيد بالمستوى العلمي لطلبة جامعة العميد وبيئتها التعليمية
|
|
|