تاريخ الرياضيات
الاعداد و نظريتها
تاريخ التحليل
تار يخ الجبر
الهندسة و التبلوجي
الرياضيات في الحضارات المختلفة
العربية
اليونانية
البابلية
الصينية
المايا
المصرية
الهندية
الرياضيات المتقطعة
المنطق
اسس الرياضيات
فلسفة الرياضيات
مواضيع عامة في المنطق
الجبر
الجبر الخطي
الجبر المجرد
الجبر البولياني
مواضيع عامة في الجبر
الضبابية
نظرية المجموعات
نظرية الزمر
نظرية الحلقات والحقول
نظرية الاعداد
نظرية الفئات
حساب المتجهات
المتتاليات-المتسلسلات
المصفوفات و نظريتها
المثلثات
الهندسة
الهندسة المستوية
الهندسة غير المستوية
مواضيع عامة في الهندسة
التفاضل و التكامل
المعادلات التفاضلية و التكاملية
معادلات تفاضلية
معادلات تكاملية
مواضيع عامة في المعادلات
التحليل
التحليل العددي
التحليل العقدي
التحليل الدالي
مواضيع عامة في التحليل
التحليل الحقيقي
التبلوجيا
نظرية الالعاب
الاحتمالات و الاحصاء
نظرية التحكم
بحوث العمليات
نظرية الكم
الشفرات
الرياضيات التطبيقية
نظريات ومبرهنات
علماء الرياضيات
500AD
500-1499
1000to1499
1500to1599
1600to1649
1650to1699
1700to1749
1750to1779
1780to1799
1800to1819
1820to1829
1830to1839
1840to1849
1850to1859
1860to1864
1865to1869
1870to1874
1875to1879
1880to1884
1885to1889
1890to1894
1895to1899
1900to1904
1905to1909
1910to1914
1915to1919
1920to1924
1925to1929
1930to1939
1940to the present
علماء الرياضيات
الرياضيات في العلوم الاخرى
بحوث و اطاريح جامعية
هل تعلم
طرائق التدريس
الرياضيات العامة
نظرية البيان
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
2234
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
(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 .
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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة

الآخبار الصحية
