Graph Path
المؤلف:
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
الجزء والصفحة:
...
11-5-2022
2423
Graph Path
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
(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
![(A|_H)_(ij)=<span style=]() {A_(ij) for i,j in H; 0 otherwise, " src="https://mathworld.wolfram.com/images/equations/GraphPath/NumberedEquation3.svg" style="height:57px; width:192px" /> |
(6)
|
with 
.
REFERENCES
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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
