Nomenclature for strongly-connected-like components in directed graphs
This question regards the nomenclature to some specific case in Graph theory:
Graph theory has its own dictionary for entities: vertex, edge, strongly connected components, trail, cycle, articulation points, bridges, and so on. Among others, there is a vertex case I fail to nominate. This vertex fulfills the following criteria:
- It belongs to a directed graph;
- It is neither a bridge end nor articulation point;
You may think: "well, it is an ordinary node. It resembles an element of a strongly connected component". However, since the graph is directed, the respective blob lacks strength to own this term.
I do not have a neat example to provide, but only an application-suitable example. You may consult the diagram here: https://cawemo.com/share/30b652c9-7133-42e3-b947-4e81087d09c8
and the NodeJS application here: https://github.com/dot-quiver/dot-quiver-api
{
'1': 0,
'91': 1,
'0-0C': 2,
'1-0L': 3,
'1-0LB': 4,
'1-1': 5,
'F0': 6,
'1-P': 7,
'1-1A': 8,
'1-PB': 9,
'1-1C': 10,
'1-1CB': 11,
'1-2': 12,
'1-2A': 13,
'F1': 14,
'6-1': 15,
'F2': 16,
'1-3A': 17,
'2-1': 18,
'1-3B': 19,
'1-3C': 20,
'1-4': 21,
'1-5': 22,
'1-5A': 23,
'1-6': 24,
'1-7': 25,
'6-1F': 26,
'6-1A': 27,
'6-1B': 28,
'6-1BA': 29,
'F3': 30,
'6-2': 31,
'7-1': 32,
'7-2': 33,
'7-2A': 34,
'6-2B': 35,
'6-2H': 36,
'F8': 37,
'F12': 38,
'2-1A': 39,
'2-2A': 40,
'3-1A': 41,
'3-1F': 42,
'3-3FB': 43,
'3-1B': 44,
'3-2A': 45,
'3-2B': 46,
'3-4A': 47,
'3-3B': 48,
'3-3A': 49,
'3-3B2': 50,
'3-4B': 51,
'F9': 52,
'2-2B': 53,
'2-2C': 54,
'2-3A': 55,
'2-3B': 56,
'F10': 57,
'2-3E': 58,
'2-3C': 59,
'2-3D': 60,
'2-4': 61,
'F11': 62,
'2-6A': 63,
'2-6B': 64
}
Interested vertices:
[
33, 34, 41, 43, 47, 48, 49,
50, 51, 52, 53, 54, 55, 56,
58, 60, 61, 62, 63, 64
]
Bridge ends:
[
[ 0, 2 ], [ 2, 3 ], [ 3, 4 ], [ 4, 5 ],
[ 5, 6 ], [ 6, 8 ], [ 6, 7 ], [ 7, 9 ],
[ 9, 10 ], [ 10, 11 ], [ 11, 12 ], [ 12, 13 ],
[ 13, 14 ], [ 14, 15 ], [ 15, 26 ], [ 26, 27 ],
[ 27, 28 ], [ 28, 29 ], [ 29, 30 ], [ 30, 32 ],
[ 30, 31 ], [ 31, 35 ], [ 35, 36 ], [ 26, 16 ],
[ 16, 18 ], [ 18, 37 ], [ 37, 39 ], [ 37, 38 ],
[ 38, 40 ], [ 57, 59 ], [ 42, 44 ], [ 44, 45 ],
[ 45, 46 ], [ 16, 17 ], [ 17, 19 ], [ 19, 20 ],
[ 20, 21 ], [ 21, 22 ], [ 22, 23 ], [ 23, 24 ],
[ 24, 25 ], [ 25, 1 ]
]
Articulation points:
[
26, 25, 24, 23, 22, 21, 20, 19,
17, 16, 15, 14, 13, 12, 11, 10,
9, 7, 6, 5, 4, 3, 2
]
Binding points:
[
59, 57, 46, 45, 44, 42, 40, 39, 38, 37, 36,
35, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23,
22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12,
11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,
0
]
Bridge ends / Articulation points:
{
'articulation,bridge_end': [
10, 11, 12, 13, 14, 15, 16, 17,
19, 2, 20, 21, 22, 23, 24, 25,
26, 3, 4, 5, 6, 7, 9
],
bridge_end: [
0, 1, 18, 27, 28, 29, 30,
31, 32, 35, 36, 37, 38, 39,
40, 42, 44, 45, 46, 57, 59,
8
]
}
Comments
Post a Comment