Definitions¶

A graph is a structure amounting to a set of vertices connected by edges. Formally:

class Graph:
    def __init__(self):
        self.vertices = {}  # Finglish comment (no change)
        self.edges = []     # لیست یالها (Persian comment - translate)

    def add_edge(self, u, v):
        # در صورت وجود رأس، یال اضافه کن (Persian comment - translate)
        if u in self.vertices and v in self.vertices:
            self.edges.append((u, v))

A simple graph prohibits loops and multiple edges between vertices. In contrast, a multigraph allows them.

Definition 3.1.1 (Directed Graph)¶

Suppose we have several cities connected by roads, and you are in city D and want to go to city A (Figure 1). To reach city A, we must traverse several roads, but since the roads can be one-way, we need a graph that shows the direction of each road, which we call a directed graph (Figure 2).

More precisely, a directed graph \(G\) is an ordered pair \((V, E)\) where \(V\) is the set of vertices. The set \(E\) contains ordered pairs of the form \((u, v)\), indicating a directed edge from \(u\) to \(v\) in the graph.

We call a directed graph \(G\) simple if it contains no multiple directed edges or loops. Note that \(G\) can be simple while \(E\) contains both \((u, v)\) and \((v, u)\), but it cannot have duplicate ordered pairs \((u, v)\).

Note: From this point forward, we will work with simple directed graphs. Unless explicitly stated otherwise, the term "directed graph" will refer to a simple directed graph.

درجه در گراف جهت دار¶

در یک گراف جهت دار، هر راس یک درجه ورودی و یک درجه خروجی دارد. برای مثال در شکل۲، درجه ورودی راس D برابر با ۳ و درجه خروجی آن برابر با ۱ است!

درجه ورودی راس \(v\) را با نماد \(d^{−}(v)\) یا \(deg^{−}(v)\) و درجه خروجی را با \(d^{+}(v)\) یا \(deg^{+}(v)\) نمایش می‌دهیم.

منظور از \(\delta^{+}, \delta^{-}\) به ترتیب مینیمم درجه ورودی و مینیمم درجه خروجی است.

به طور مشابه منظور از \(\Delta^{+}, \Delta^{-}\) به ترتیب ماکسیمم درجه ورودی و ماکسیمم درجه خروجی است.

Degree in Directed Graphs¶

In a directed graph, each vertex has an in-degree and an out-degree. For example, in Figure 2, the in-degree of vertex D is 3 and its out-degree is 1!

The in-degree of vertex \(v\) is denoted by the symbol \(d^{−}(v)\) or \(deg^{−}(v)\), and the out-degree is denoted by \(d^{+}(v)\) or \(deg^{+}(v)\).

The notation \(\delta^{+}, \delta^{-}\) refers to the minimum in-degree and minimum out-degree, respectively.

Similarly, the notation \(\Delta^{+}, \Delta^{-}\) refers to the maximum in-degree and maximum out-degree, respectively.

Cycles and Paths in Directed Graphs¶

Similar to simple graphs, in directed graphs, we have definitions such as walk, closed walk, trail, cycle, and path. For example, in Figure 2, a directed path could be a path like (D -> C -> B -> A) where the starting vertex is the origin (D) and the ending vertex is the destination (A). Note that when traversing edges, their direction must be respected. For example, when at vertex D, we cannot go directly to vertex A!

Additionally, a cycle in Figure 2 could be (D -> C -> B -> D). Obviously, when traversing a cycle, edge directions must be respected.

Similarly, the length of each of the above definitions equals the number of its edges.

More precisely:

Walk: A sequence \(v_{1}, v_{2}, ..., v_{l}\) is a walk in the directed graph \(G\) if for every \(1 \leq i < l\), the edge \((v_{i}, v_{i+1})\) exists in \(G\) (i.e., the edge belongs to the set \(E\)).

Closed Walk: If in the sequence we defined, \(v_{1} = v_{l}\), we call this walk a closed walk.

Trail: If in the sequence we defined, there are no repeated edges, we call this walk a trail.

Path: If in the sequence we defined, there are no repeated vertices (and consequently no repeated edges), the resulting walk is a path.

Cycle: Finally, if in a path, the starting and ending vertices are the same ( \(v_{1} = v_{l}\) ), we call the resulting walk a cycle.

Note that these definitions are exactly like those in simple graphs, with the difference that in directed graphs, edge directions must be correctly followed!

Theorems and Lemmas Used in This Section¶

A Few More Definitions¶

Underlying Graph: If we remove the directions from the edges of a directed graph, the resulting graph is called the underlying graph. For example, is the underlying graph for .