Graph

Definition

A graph is a mathematical structure consisting of a set of nodes (also called vertices) and a set of edges, where each edge relates a pair of nodes.

Basic Concepts

• Adjacent: Two vertices are adjacent if there is an edge between them.
• Outgoing Edge: In a directed graph, an outgoing edge from a node $v$ is any edge $(v,u)$ for any node $u$.
• Path: A path between two nodes is a sequence of edges and nodes between two endpoints. When the graph is directed, the path typically follows outgoing edges only.
• Cycle: A cycle is any non-trivial path that starts and ends at the same node.

Types of Graphs

• Undirected Graph: Edges are unordered pairs.
• Directed Graph: Edges are ordered pairs.
• Labelled Graph: Edges and nodes may be assigned labels.
• Simple Graph: No self-loops and at most one edge between any two nodes.
• Tree: A graph without cycles.
• Directed Acyclic Graph: A directed graph with no directed cycles.
• Rooted Tree: A directed acyclic graph with exactly one path from the root to any node.