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

تعریف 3.7.1 (گراف‌جایگشت)¶

جایگشت \(P: p_{1}, p_{2}, p_{3}, ..., p_{n}\) از اعداد 1 تا n را در نظر بگیرید.

گراف \(n\) راسی \(G\) را در نظر بگیرید که راس های آن از 1 تا n شماره‌گذاری شده‌اند.

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

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

قضیه 3.7.2¶

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

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

قضیه 3.7.3¶

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

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