Connected and disconnected graph

in ths

1. MIRZA NASIR BAIG BS-Mathematics Fall (2018-22) PIASS COLLEGE KASUR

2. Connected and disconnected Graph

3. Definition A graph G is said to be a connected if every pair of vertices in G are connected. Otherwise, G is called a disconnected graph. Two vertices in G are said to be connected if there is at least one path from one vertex to the other. In other words, a graph G is said to be connected if there is at least one path between every two vertices in G and disconnected if G has at least one pair of vertices between which there is no path. A graph is connected if we can reach any vertex from any other vertex by travelling along the edges and disconnected otherwise .

4. For E xample the graphs in Figure 30(a, b, c, d, e) are connecte d .

5. whereas the graphs in Figure 31(a, b, c) are disconnected.

6. A complete graph is always connected, also, a null graph of more than one vertex is disconnected (see Fig. 32). All paths and circuits in a graph G are connected subgraphs of G. Every graph G consists of one or more connected graphs, each such connected graph is a subgraph of G and is called a component of G. A connected graph has only one component and a disconnected graph has two or more components. For example, the graphs in Figure 31(a, b) have two components each.

7. Matrix Representation of Graphs

8. Definition The adjacency matrix of the graph G = (V,E) is an n × n matrix D = ( dij ), where n is the number of vertices in G, V = {v1, . . . , vn } and d ij  = number of edges between vi and vj . In particular, dij = 0 if (vi, vj ) is not an edge in G. The matrix D is symmetric, i.e. DT = D.

9. Example Obviously, an adjacency matrix defines a graph completely up to an isomorphism. The adjacency matrix of a directed graph G is D = ( d ij ), where d ij  = number of arcs that come out of vertex vi and go into vertex vj

10. The all-vertex incidence matrix of a non-empty and loopless graph G = (V,E) is an n×m matrix A = ( a ij ), where n is the number of vertices in G, m is the number of edges in G and

11. The all-vertex incidence matrix of a non-empty and loopless directed graph G is A = ( aij ), where

12. Since every column of an all-vertex incidence matrix contains exactly two non-zero numbers, two ones, we can remove a row and still have enough information to define the graph. The incidence matrix of a graph is obtained by removing a row from the all-vertex incidence matrix. It is not unique because there are n possible rows to remove. The vertex corresponding to the row removed is called the reference vertex. Similarly, every column in the all-vertex incidence matrix of a digraph contains exactly two non-zero numbers, 1 and −1. We can remove a row from the all-vertex incidence matrix and obtain the incidence matrix. Notice that the rows of an all-vertex incidence matrix are linearly dependent because the sum of rows is a zero vector.

13. The End