Read More
Date: 4-5-2022
1359
Date: 15-3-2022
1161
Date: 19-4-2022
1846
|
A block is a maximal connected subgraph of a given graph that has no articulation vertex (West 2000, p. 155). If a block has more than two vertices, then it is biconnected. The blocks of a loopless graph are its isolated points, bridges, and maximal 2-connected subgraphs (West 2000, p. 155; Gross and Yellen 2006, p. 241). Examples of graphs with their corresponding blocks due to Harary (1994, p. 26) and West (2000, p. 155) are illustrated above.
If a graph is connected and has no articulation vertices, then itself is called a block (Harary 1994, p. 26; West 2000, p. 155).
Blocks arise in graph theoretical problems such as finding unit-distance graphs and the graph genus of connected graphs. For example, a connected graph is unit-distance if and only if each of its blocks is unit-distance and the graph coarseness of a graph is the sum of the coarsenesses of its blocks.
Aho, A. V.; Hopcroft, J. E.; and Ullman, J. D. The Design and Analysis of Computer Algorithms. Reading, MA: Addison-Wesley, 1974.
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. "Biconnected Components." §5.1.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 175-177, 1990.
West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 155-158, 2000.
|
|
علامات بسيطة في جسدك قد تنذر بمرض "قاتل"
|
|
|
|
|
أول صور ثلاثية الأبعاد للغدة الزعترية البشرية
|
|
|
|
|
العتبة الحسينية تطلق فعاليات المخيم القرآني الثالث في جامعة البصرة
|
|
|