91Ó°ÊÓ

A directed graph, also known as a digraph, is a fundamental concept in graph theory. It consists of two main parts: vertices (or nodes) and directed edges (or arcs).
Vertices are points in the graph, and edges are ordered pairs of vertices that indicate a direction from one vertex to another. The direction is crucial because it specifies a one-way relationship between the nodes.
Understanding directed graphs involves visualizing how the vertices connect and interact through these directed edges.
Each edge in a directed graph has a clear origin (starting vertex) and a clear destination (ending vertex). This directionality distinguishes directed graphs from undirected graphs where edges don't have a direction.

A bijection is a one-to-one and onto function between two sets. When we say two directed graphs are isomorphic, we mean there exists a bijection between their vertex sets that also preserves the graph structure.
Formally, for two directed graphs G and H, a bijection f: V(G) → V(H) is required. This function should map each vertex in G to a unique vertex in H and vice versa, ensuring every vertex in both graphs is paired with exactly one vertex from the other graph.
In simpler terms, each vertex in one graph corresponds to exactly one vertex in the other, creating a perfect 'matching' between the vertices of the two graphs.

Adjacency relationships in directed graphs refer to how vertices are connected through directed edges.
When discussing isomorphism, it is crucial that these relationships are preserved by the bijection. If a vertex u in graph G is connected to a vertex v through a directed edge (u, v), the corresponding vertices f(u) in graph H must also be connected by a directed edge f(u) → f(v).
This means the direction and connection pattern between the vertices in G must match the connection pattern in H after applying the bijection. Maintaining adjacency relationships ensures that the structure and 'shape' of the graph are retained.

The vertex set is the collection of all vertices in a graph. For a graph G, this set is denoted as V(G).
In the context of graph isomorphism, we are interested in finding a bijection between the vertex sets of two graphs G and H, signified as V(G) and V(H).
The role of the bijection is to create a corresponding relationship between every vertex in V(G) and V(H). Ensuring that every vertex in G maps uniquely to a vertex in H and vice versa is essential for confirming isomorphism.

Edge preservation is crucial to determining the isomorphism of directed graphs.
When two directed graphs are said to be isomorphic, every directed edge in the first graph must correspond to a directed edge in the second graph after applying the bijection.
More formally, if there is an edge (u, v) in graph G, then there should be a corresponding edge (f(u), f(v)) in graph H. This preserves the original connectivity and directionality of the graphs.
Without edge preservation, even if there is a bijection between the vertex sets, the graphs may not truly be isomorphic because their connectivity structures would differ.