Distance Between Vertices and Connected Components of Graphs

 

If there is walk (and  hence a path from u to vin given graph G).

Let 

dG(u,v)= min { k  | u --- k-->v} be the distance between u and v.

 Disconnected

dG(u,v) =∞ by convention ,when thereis no walk

 

Note: A graph G is connected if dG(u,v) <∞ for all u,v∈G and disconnected otherwise.

The maximal connected sub graphs of G areits connected components

     c(G)=# of connected component of G

here c(G) is 2.

 

what maximality condition mean is ?

Maximality condition means that a sub graph H ⊆ G is a connected sub graph and for any w ∈ V(G) w ∉ H

then G[V(H) ∪{w}] is disconnected.

0Comment