Definitions and Basic Properties
- A graph is a collection of vertices (also called nodes) and edges (also called links) that connect pairs of vertices.
- Graphs can be directed (where edges have a direction) or undirected (where edges do not have a direction).
- The degree of a vertex in a graph is the number of edges incident to it.
- A tree is a connected, acyclic graph.
- Trees have many useful properties, such as the fact that any two vertices in a tree are connected by a unique path.
- Binary trees are trees where each node has at most two children.
- Trees can be used to model hierarchical relationships, such as family trees or organizational charts.
- Spanning trees are trees that include all the vertices of a graph.
Spanning Trees
{% hint style="info" %} The spanning trees are trees that include all the vertices of a graph. {% endhint %}
- Finding spanning trees using depth-first search and breadth-first search algorithms
DFS and BFS can be used to find spanning trees in a graph