Read More
Date: 20-4-2022
1426
Date: 17-4-2022
1145
Date: 21-4-2022
2101
|
An articulation vertex of a connected graph, also called a cut-vertex (Harary 1994, p. 26; West 2000; Gross and Yellen 2006) or "cutpoint" (Harary 1994, p. 26), is a vertex whose removal will disconnect the graph (Chartrand 1985). More generally, an articulation vertex of a not-necessarily-connected graph is a vertex whose removal increases the connected component count (Harary 1994, p. 26; West 2000, p. 23). An example graph due to West (2000, pp. 22-23) is illustrated above with its articulation vertices and indicated.
A graph on two or more vertices possessing no articulation vertices is called a biconnected graph. A vertex is an articulation vertex iff it appears in two biconnected components.
A maximal connected subgraph of a given graph that has no articulation vertex is called a block (West 2000, p. 155).
The endpoints of a graph bridge are articulation vertices unless they both have vertex degree 1. On the other hand, it is possible for a non-bridge edge to have both endpoints be articulation vertices.
The Wolfram Language function FindVertexCut[g] returns a vertex cut set of smallest size for a connected graph , which corresponds to an articulation vertex if the set is of size 1.
The analog of an articulation vertex for edges is called a graph bridge.
Chartrand, G. "Cut-Vertices and Bridges." §2.4 in Introductory Graph Theory. New York: Dover, pp. 45-49, 1985.
Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.
Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 175, 1990.
West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.
|
|
مخاطر خفية لمكون شائع في مشروبات الطاقة والمكملات الغذائية
|
|
|
|
|
"آبل" تشغّل نظامها الجديد للذكاء الاصطناعي على أجهزتها
|
|
|
|
|
المجمع العلميّ يُواصل عقد جلسات تعليميّة في فنون الإقراء لطلبة العلوم الدينيّة في النجف الأشرف
|
|
|