Subgraphs and connected components

In particular restricting the arcs of G to a subset J c J and leaving N = N we obtain a factor (subgraph) of G if we take J = 0 then G is a set of isolated nodes n ( N = N). More generally, it can happen that some node n N (= N) is not endpoint of any j e J such node is then isolated in G . For example deleting arc y, in Fig. A-1 leaves node n, isolated in the factor subgraph. 

The further concepts introduced in this Section are independent of orientation. Let us begin with the notion of a path. From the possible formal definitions, let us adopt the simplest. We call path in graph G a sequence of nodes (n, —, ) such that is endpoint of some arc with the other endpoint 

So as to verify the connectedness of a graph, it is sufficient to select one (arbitrary) node n if for any other node n n) there exists a path of endpoints n and n then the graph is connected. 

Let G be a graph of node set N and arc set J. Then there exists a unique number K 1, a unique partition (disjoint union of parts) of the set N into nonempty subsets N (l k K), and a unique partition of the set J into subsets 

J (l k K) such that N, and J, are the respective node set and arc set of connected component G of G. Thus G is uniquely decomposed into K connected components Gj. If G is an isolated node then N is a one-element set and 

---