Graphs: Basic Definitions

• A Directed Graph (G) consists of a set of vertices (V) and a set of edges (E), where edges have direction and are represented by arrows. It is simple if it has no self-loops.
• An Undirected Graph has unordered pairs of vertices as edges, meaning edges have no direction, and self-loops are not allowed.
• For a directed edge (u,v):
  • it leaves or is incident from u and enters or is incident to v
  • v is adjacent to u (this is symmetric in undirected graphs)
• The degree of a vertex in an undirected graph is the number of edges connected to it. A vertex is isolated if its degree is 0. In directed graphs, we distinguish between in-degree (edges entering) and out-degree (edges leaving).
• A path of length k from u to u' is a sequence of vertices ( $v_0$, $v_1$, ..., $v_k$ ), were $v_0$ = u, $v_k$ = u', and all the vertices are part of the graph. The length of a path is the number of vertices in the path.
• A simple path has all distinct vertices. A simple path in an undirected graph has no repeated vertices except for the starting and ending vertices (if it's a cycle).
• An undirected graph is connected if every vertex is reachable from every other vertex.
• A component is a connected subgraph of an undirected graph that isn't part of a larger connected subgraph. The connected components are equivalence classes of vertices under the "is reachable from" relation.
• A undirected graph is connected if it has exactly one connected component.
• A directed graph is strongly connected if every vertex is reachable from every other vertex. Its strongly connected components are equivalence classes of vertices under the "are mutually reachable" relation.
• Two graphs are isomorphic if their vertices can be relabeled such that the edges in one graph correspond to the edges in the other.
• A forest is an undirected, acyclic graph where each connected component is a tree. It can also be seen as a collection of disjoint trees.
• The adjacency matrix of a graph is a 2D array where matrix[i][j] represents the presence or weight of an edge between vertices i and j.
• The adjacency list of a graph is an array of lists where each list contains the neighbors of a vertex.