Graph
A Graph is a non-linear data structure that represents a set of nodes (vertices) and links (edges) between them.
It is denoted as:
where:
- V = set of vertices
- E = set of edges
Connected Graph
A graph is said to be connected if there exists at least one path between every pair of distinct vertices of the graph.
Path
A path in a graph is a sequence of edges that connects a source vertex to a destination vertex.
Hamiltonian Circuit (Cycle)
A Hamiltonian Circuit is a cycle in a graph that:
- Passes through each vertex exactly once, and
- Returns to the starting vertex (terminal one)
If a graph contains a Hamiltonian circuit, then the graph is called a Hamiltonian Graph.
Tree
A Tree is a connected graph without any cycle.
- Acyclic + Connected = Tree
- A tree with n nodes has (n − 1) edges
Spanning Tree
A Spanning Tree is a subgraph of a connected graph that:
- Includes all the vertices of
- Contains no cycles
- Is a tree
Let be a connected graph. A graph is a Spanning Tree of G if:
is a subgraph of
- is a Tree
(Connected and acyclic)
(All vertices of G must be in H)