Graphs: Basic Definitions - rFronteddu/general_wiki GitHub Wiki
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.