Connected & Disconnected Graphs
Connected & Disconnected Graphs
·
Connected Graph:
o
A graph is considered "connected" if
there is a path between every pair of vertices in the graph.
o
In a connected graph, it is possible to travel
from any vertex to any other vertex by following a sequence of edges.
o
If a graph is not connected, it may consist of
multiple connected components, each of which is itself a connected subgraph.
§
These connected components are disjoint, meaning
there are no paths between vertices in different components.
o
Example: A tree is a classic example of a
connected graph. In a tree, there is a unique path between any two vertices.
o
·
Disconnected Graph:
o
A graph is "disconnected" if it is not
connected, which means there are at least two vertices that have no path
connecting them.
o
A disconnected graph may consist of multiple
connected components (subgraphs), each of which is connected internally but not
to vertices outside its component.
o
Example: Consider two separate trees.
§
If you combine them into a single graph, it
becomes a disconnected graph with two connected components.
o
