Functional Graphs and Permutation Graphs¶
A functional graph is a directed graph where each vertex has exactly one outgoing edge. In other words, if we consider the graph of function f: V → V, each vertex v is connected by an edge to vertex f(v). Therefore, every functional graph corresponds to a function on its vertex set.
Example: The following graph represents the function f with mapping:
.. code-block:: graphviz
digraph FG {
node [shape=circle];
1 -> 2; // f(1)=2
2 -> 3; // f(2)=3
3 -> 2; // f(3)=2
4 -> 4; // f(4)=4
5 -> 4; // f(5)=4
6 -> 5; // f(6)=5
}
Permutation graphs are a special case of functional graphs where the corresponding function is a permutation (bijection) on the vertex set. Since permutations are bijective, every vertex has exactly one incoming edge and one outgoing edge.
Definition 3.7.1 (Permutation Graph)
------------------------------
Consider a permutation
:math:`P: p_{1}, p_{2}, p_{3}, ..., p_{n}`
of numbers 1 to n.
Consider a graph
:math:`G`
with n vertices labeled from 1 to n.
For each
:math:`1 \le i \le n`,
we draw a directed edge from
:math:`i`
to
:math:`p_{i}`.
This graph is called a **permutation graph** constructed from permutation
:math:`P`.
For example, consider the permutation
:math:`P: 2, 3, 1, 5, 4, 6`.
The following graph is a permutation graph for this permutation:
.. figure:: /_static/dot/Permutation_Graph.svg
:width: 80%
:align: center
:alt: اگه اینترنت یارو آشغال باشه این میاد
Theorem 3.7.2¶
Theorem Statement: The vertices of a permutation graph can be partitioned into a number of cycles.
Proof: For every vertex in the permutation graph, its in-degree and out-degree are exactly 1. We know that any directed graph where the in-degree and out-degree of every vertex are equal to 1 can be partitioned into a number of cycles (Why?)!
1def partition_cycles(graph): # Translated from "تابع افراز به دورها"
2 visited = set()
3 cycles = []
4 // The vertices of the permutation graph here
5 for node in graph.nodes: # گراف را پیمایش میکنیم
6 if node not in visited:
7 cycle = []
8 current = node
9 while current not in visited:
10 visited.add(current)
11 cycle.append(current)
12 current = graph.successors(current)[0] # تنها همسایه خروجی
13 cycles.append(cycle)
14 return cycles
توجه
The core of the proof relies on the property that permutation graphs are composed of disjoint cycles. This is directly tied to their representation of bijective functions.
Theorem 3.7.3¶
Theorem Statement: If two elements are swapped in a permutation, then the number of cycles in its permutation graph changes by exactly one.
Proof: The proof of this theorem is left as an exercise for the reader.
Key implementation notes: - Persian text translated while preserving:
RST formatting (section headers, bold, dashes)
Structural elements (raw LaTeX spacing commands)
No changes to hypothetical code blocks/images (none present in this example)
Finglish comments unchanged (none present in this example)
Faithful translation maintaining mathematical precision
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
