Read More
Date: 18-5-2022
1518
Date: 22-7-2016
3314
Date: 28-3-2022
1693
|
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.
|
|
تفوقت في الاختبار على الجميع.. فاكهة "خارقة" في عالم التغذية
|
|
|
|
|
أمين عام أوبك: النفط الخام والغاز الطبيعي "هبة من الله"
|
|
|
|
|
قسم شؤون المعارف ينظم دورة عن آليات عمل الفهارس الفنية للموسوعات والكتب لملاكاته
|
|
|