گراف تابعی و گراف‌جایگشت
=============================================

تعریف 3.7.1 (گراف‌جایگشت)
------------------------------
جایگشت
:math:`P: p_{1}, p_{2}, p_{3}, ..., p_{n}`
از اعداد 1 تا n را در نظر بگیرید.

گراف
:math:`n`
راسی
:math:`G`
را در نظر بگیرید که راس های آن از 1 تا n شماره‌گذاری شده‌اند.

به ازای هر
:math:`1 \le i \le n`
یک یال جهت‌دار از
:math:`i`
به
:math:`p_{i}`
می‌زنیم. به این گراف، گراف‌جایگشت می‌گوییم که از جایگشت
:math:`P`
ساخته شده.

برای مثال، جایگشت 
:math:`P: 2, 3, 1, 5, 4, 6`
را در نظر بگیرید. گراف‌ زیر، یک گراف‌جایگشت برای این جایگشت است:

.. figure:: /_static/dot/Permutation_Graph.svg
   :width: 80%
   :align: center
   :alt: اگه اینترنت یارو آشغال باشه این میاد

قضیه 3.7.2
------------------------------
**صورت قضیه :** راس‌های گراف‌جایگشت، به تعدادی دور افراز می‌شوند.

**اثبات قضیه :** برای هر راس از گراف‌جایگشت، درجه ورودی و خروجی آن،‌ دقیقا یک می‌باشد و می‌دانیم گراف جهت داری که درجه ورودی و خروجی هر راس آن، برابر با یک باشد، به تعدادی دور افراز می‌شود(چرا؟)!


قضیه 3.7.3
------------------------------
**صورت قضیه :** اگر در یک جایگشت، جای 2 تا از اعضای آن جابه‌جا شود، آن‌گاه در گراف جایگشت آن، تعداد دور ها دقیقا یکی تغییر می‌کند.

**اثبات قضیه :** اثبات قضیه برعهده خودتان می‌باشد.