<< add_node_data Nodes - Vertices con_nodes >>

metanet >> metanet > Nodes - Vertices > articul

articul

finds one or more articulation points

Calling Sequence

nart = articul([i],g)

Parameters

g

:a graph (see graph_data_structure).

i

integer

nart

integer row vector

Description

An articulation of a connected graph is a node whose removal will disconnect the graph. In general, an articulation vertex is a node of a graph whose removal increases the number of components.

articul finds one or more articulation points (if they exist) of the graph g. nart is the row vector of numbers of articulation nodes: deleting one of these nodes increases the number of connected components of the graph. i is the optional node number from which the algorithm starts. The default is 1. Note that the result depends strongly on this starting node.

Examples

ta=[2  1 3 2 2 4 4 5 6 7 8 8 9 10 10 10 10 11 12 13 14 15 16 17 17];
he=[1 10 2 5 7 3 2 4 5 8 6 9 7  7 11 13 15 12 13 14 11 16 17 14 15];
g=make_graph('foo',1,17,ta,he);
g.nodes.graphics.x=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642]/2;
g.nodes.graphics.y=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301]/2;
show_graph(g);
nart = articul(g)
hilite_nodes(nart);

Bibliography

Chartrand, G. "Cut-Vertices and Bridges." ยง2.4 in Introductory Graph Theory. New York: Dover, pp. 45-49, 1985.

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.


Report an issue
<< add_node_data Nodes - Vertices con_nodes >>