�ݺ�ߣ

‫گراف‬ ‫ی‬‫ر‬‫تئو‬
GRAPH THEORY
‫دهنده‬‫ائه‬‫ر‬‫ا‬:
‫سید‬‫امین‬‫اتابک‬
(‫دکترا‬‫دانشجو‬‫مخابرات‬ ‫ق‬‫بر‬ ‫ی‬ ‫تخصص‬)
(‫ی‬ ‫مجلس‬‫شهر‬‫واحد‬ ‫اسالمی‬ ‫اد‬‫ز‬‫آ‬ ‫دانشگاه‬)
‫اهنما‬‫ر‬ ‫استاد‬:
‫نژاد‬‫ی‬‫مصر‬‫فرهاد‬‫دکتر‬
‫پاییز‬1396
‫نور‬ ‫نام‬ ‫به‬
aminatabak@gmail.com
1

‫ها‬ ‫سرفصل‬
‫اف‬‫ر‬‫گ‬ ‫اولیه‬‫مفاهیم‬ ‫و‬ ‫یف‬‫ر‬‫تعا‬
‫دار‬ ‫جهت‬ ‫اف‬‫ر‬‫گ‬
‫خت‬‫ر‬‫د‬
‫مسطح‬ ‫اف‬‫ر‬‫گ‬
‫اف‬‫ر‬‫گ‬‫ی‬‫آمیز‬ ‫نک‬‫ر‬
2

‫اف‬‫ر‬‫گ‬‫تعریف‬(1)
‫یک‬‫اف‬‫ر‬‫گ‬G‫ت‬‫ر‬‫عبا‬‫است‬‫از‬‫ج‬‫و‬‫ز‬( V(G),E(G) ):
V(G):‫مجموعه‬‫ئوس‬‫ر‬‫اف‬‫ر‬‫گ‬G
E(G):‫مجموعه‬‫یالهای‬‫اف‬‫ر‬‫گ‬G
V(G)= 𝑉1,𝑉2,𝑉3,𝑉4,𝑉5,𝑉6
E(G)= 𝑉1 𝑉2,𝑉1 𝑉5,𝑉1 𝑉6,𝑉2 𝑉5,𝑉2 𝑉3,𝑉3 𝑉5,𝑉5 𝑉6,𝑉4 𝑉5
3

‫اف‬‫ر‬‫گ‬‫تعریف‬(2)-‫ساده‬ ‫اف‬‫ر‬‫گ‬
‫اگر‬‫اف‬‫ر‬‫گ‬G‫ای‬‫ر‬‫دا‬‫یال‬‫چندگانه‬‫و‬‫طوقه‬‫نباشد‬‫گوییم‬‫اف‬‫ر‬‫گ‬‫ساده‬‫است‬.
‫یال‬‫چندگانه‬:‫اگر‬‫چند‬‫یال‬‫ی‬‫مواز‬‫هم‬‫بین‬‫دو‬‫اس‬‫ر‬‫اف‬‫ر‬‫گ‬‫وجود‬‫داشته‬‫باش‬‫د‬
‫مانند‬‫یال‬‫های‬‫چند‬‫گانه‬‫بین‬‫ئوس‬‫ر‬a‫و‬b
‫طوقه‬:‫اگر‬‫یک‬‫یال‬‫از‬‫یک‬‫اس‬‫ر‬‫به‬‫خودش‬‫باشد‬‫یک‬‫طوقه‬‫تشکیل‬‫میش‬‫ود‬
‫مانند‬‫طوقه‬‫اس‬‫ر‬c
4

‫اف‬‫ر‬‫گ‬‫تعریف‬(3)-‫متنهای‬ ‫اف‬‫ر‬‫گ‬
‫اگر‬‫هر‬‫دو‬‫مجموعه‬‫ئوس‬‫ر‬(V(G))‫و‬‫مجموعه‬‫یالها‬(E(G))‫متنهای‬،‫باشند‬
‫اف‬‫ر‬‫گ‬G‫یک‬‫اف‬‫ر‬‫گ‬‫متنهای‬‫است‬.‫و‬‫در‬‫غیر‬‫این‬‫ت‬‫ر‬‫صو‬‫نامتناهی‬‫است‬.
5

‫اف‬‫ر‬‫گ‬‫تعریف‬(4)-‫شده‬‫ی‬‫گذار‬ ‫برچسب‬ ‫اف‬‫ر‬‫گ‬
‫اگر‬n‫اس‬‫ر‬‫اف‬‫ر‬‫گ‬‫ا‬‫ر‬‫با‬‫برچسب‬‫های‬𝑉4,𝑉3,𝑉2,𝑉1‫و‬...‫و‬𝑉𝑛‫برچسب‬‫بدهیم‬(
‫ی‬‫نامگذار‬‫کنیم‬)،‫آنگاه‬‫اف‬‫ر‬‫گ‬‫برچسبدار‬‫میشود‬.
6

‫اف‬‫ر‬‫گ‬‫تعریف‬(5)–‫اف‬‫ر‬‫گ‬‫ه‬‫ز‬‫اندا‬‫و‬ ‫مرتبه‬
‫مرتبه‬‫اف‬‫ر‬‫گ‬=‫تعداد‬‫ئوس‬‫ر‬‫اف‬‫ر‬‫گ‬G=(V,E)=n
‫ه‬‫ز‬‫اندا‬‫اف‬‫ر‬‫گ‬=‫تعداد‬‫یالهای‬‫اف‬‫ر‬‫گ‬G=(V,E)=m
7
n = 7
m = 9

‫اف‬‫ر‬‫گ‬‫تعریف‬(6)–‫اف‬‫ر‬‫گ‬‫ئوس‬‫ر‬‫جه‬‫ر‬‫د‬
‫تعداد‬‫یالهای‬‫متصل‬‫به‬‫اس‬‫ر‬V‫ا‬‫ر‬‫جه‬‫ر‬‫د‬‫اس‬‫ر‬V‫گویند‬.
‫اگر‬‫اس‬‫ر‬‫ای‬‫ر‬‫دا‬‫طوقه‬،‫باشد‬‫در‬‫محاسبه‬‫جه‬‫ر‬‫د‬‫آن‬،‫اس‬‫ر‬‫هر‬‫طوقه‬‫دو‬‫یال‬
‫نظر‬‫ر‬‫د‬‫گرفته‬‫میشود‬
‫اس‬‫ر‬‫با‬‫جه‬‫ر‬‫د‬‫صفر‬‫ا‬‫ر‬‫اس‬‫ر‬‫تنها‬‫گویند‬
‫اس‬‫ر‬‫با‬‫جه‬‫ر‬‫د‬‫یک‬‫ا‬‫ر‬‫برگ‬‫گویند‬
‫کوچکترین‬‫و‬‫گترین‬‫ر‬‫بز‬‫جه‬‫ر‬‫د‬‫ئوس‬‫ر‬‫اف‬‫ر‬‫گ‬G‫ا‬‫ر‬‫به‬‫ترتیب‬‫با‬𝛿 𝐺‫و‬∆(𝐺)
‫نشان‬‫میدهیم‬.
8

‫اف‬‫ر‬‫گ‬‫تعریف‬(7)–‫اف‬‫ر‬‫گ‬K‫منتظم‬
‫اگر‬‫جه‬‫ر‬‫د‬‫تمام‬‫ئوس‬‫ر‬‫یک‬‫اف‬‫ر‬‫گ‬K،‫باشد‬‫آنگاه‬‫اف‬‫ر‬‫گ‬K‫منتظم‬‫نامیده‬‫میشود‬.
‫اف‬‫ر‬‫گ‬3-‫منتظم‬
9

‫اف‬‫ر‬‫گ‬‫تعریف‬(8)–‫کامل‬ ‫اف‬‫ر‬‫گ‬𝐾 𝑛
‫یک‬‫اف‬‫ر‬‫گ‬‫ساده‬‫با‬n‫اس‬‫ر‬‫که‬‫جه‬‫ر‬‫د‬‫هر‬‫اس‬‫ر‬n-1‫باشد‬‫ا‬‫ر‬‫اف‬‫ر‬‫گ‬‫کامل‬‫گوییم‬.
10

‫اف‬‫ر‬‫گ‬‫تعریف‬(9)–‫اف‬‫ر‬‫گ‬ ‫وقوع‬‫و‬ ‫ت‬‫ر‬‫مجاو‬ ‫ماتریس‬
‫ماتریس‬‫ت‬‫ر‬‫مجاو‬A(G)‫اف‬‫ر‬‫گ‬G‫با‬n،‫اس‬‫ر‬‫ی‬ ‫ماتریس‬‫است‬
‫که‬‫در‬‫آن‬‫ایه‬‫ر‬‫د‬𝑎𝑖𝑗‫ابر‬‫ر‬‫ب‬‫تعداد‬‫یالهای‬‫بین‬‫دو‬‫اس‬‫ر‬𝑉1‫و‬𝑉2
‫است‬.
‫اف‬‫ر‬‫گ‬G‫با‬n‫اس‬‫ر‬‫و‬m‫یال‬‫ای‬‫ر‬‫دا‬‫ماتریس‬‫وقوع‬M(G)
‫است‬‫و‬‫ایه‬‫ر‬‫د‬𝑚𝑖𝑗‫در‬‫تی‬‫ر‬‫صو‬‫یک‬‫است‬‫که‬‫اس‬‫ر‬i‫بر‬‫ی‬‫و‬‫ر‬‫یال‬
j‫واقع‬‫شده‬‫باشد‬.‫لذا‬‫این‬‫ماتریس‬n‫سطر‬‫و‬m‫ن‬‫ستو‬‫د‬‫ر‬‫دا‬.
11

‫اف‬‫ر‬‫گ‬‫تعریف‬(10)–‫یکریخت‬ ‫اف‬‫ر‬‫گ‬‫دو‬
‫اگر‬‫دو‬‫اف‬‫ر‬‫گ‬G(V1,E1)‫و‬H(V2,E2)‫یکریخت‬،‫باشند‬‫آنگاه‬:
𝑓: 𝑉 𝐺 → 𝑉 𝐻 uv ∈ 𝐸 𝐺 ↔ 𝑓 𝑣 𝑓 𝑢 ∈ 𝐸(𝐻)
𝑓 𝑎 = 𝑢
𝑓 𝑐 = 𝑦
𝑓 𝑏 = 𝑣
𝑓 𝑑 = 𝑥
12

‫اف‬‫ر‬‫گ‬‫تعریف‬(11)–‫یکریخت‬ ‫اف‬‫ر‬‫گ‬‫دو‬
‫مثال‬:
13
𝑓 0 = 𝑑
𝑓 1 = 𝑎
𝑓 4 = 𝑐
𝑓 7 = 𝑏
𝑓 2 = ℎ
𝑓 3 = 𝑒
𝑓 5 = 𝑔
𝑓 6 = 𝑓
𝐺 ≅ 𝐻1

‫اف‬‫ر‬‫گ‬‫تعریف‬(12)–‫اف‬‫ر‬‫گ‬‫یک‬ ‫یختی‬‫ر‬‫خود‬
‫یک‬‫یختی‬‫ر‬‫خود‬‫از‬‫اف‬‫ر‬‫گ‬G‫جایگشتی‬‫از‬‫مجموعه‬‫ئوس‬‫ر‬G،‫است‬‫که‬‫یک‬‫یکریختی‬
‫از‬G‫به‬G‫ایجاد‬‫میکند‬.
‫افی‬‫ر‬‫گ‬‫که‬‫فقط‬‫یک‬‫یختی‬‫ر‬‫خود‬‫د‬‫ر‬‫دا‬‫ا‬‫ر‬‫همانی‬‫گویند‬.
14
𝑓 𝑎 = 𝑎
𝑓 𝑏 = 𝑏
𝑓 𝑐 = 𝑐
𝑓 𝑑 = 𝑑
𝑓 𝑎 = 𝑑
𝑓 𝑑 = 𝑎
𝑓 𝑏 = 𝑐
𝑓 𝑐 = 𝑑 𝑓 𝑐 = 𝑐
𝑓 𝑑 = 𝑑
𝑓 𝑏 = 𝑏
𝑓 𝑎 = 𝑎
𝑓 𝑒 = 𝑒
𝑓 𝑓 = 𝑓
𝑓 𝑔 = 𝑔

‫اف‬‫ر‬‫گ‬‫تعریف‬(13)–‫اف‬‫ر‬‫گ‬ ‫یک‬‫یختی‬‫ر‬‫خود‬
‫مثال‬
15
𝑓 𝑎 = 𝑎
𝑓 𝑏 = 𝑏
𝑓 𝑐 = 𝑐
𝑓 𝑑 = 𝑑
𝑓 𝑒 = 𝑒
𝑓 𝑎 = 𝑎
𝑓 𝑏 = 𝑐
𝑓 𝑐 = 𝑏
𝑓 𝑑 = 𝑒
𝑓 𝑒 = 𝑑

‫اف‬‫ر‬‫گ‬‫تعریف‬(14)–‫ت‬‫ر‬‫مجاو‬ ‫ماتریس‬ ‫با‬ ‫یکریختی‬ ‫تشخیص‬
‫اگر‬A(G)‫ماتریس‬‫ت‬‫ر‬‫مجاو‬‫اف‬‫ر‬‫گ‬G‫و‬A(H)‫ماتریس‬‫ت‬‫ر‬‫مجاو‬‫اف‬‫ر‬‫گ‬H،‫باشد‬
‫حال‬‫اگر‬‫با‬‫اعمال‬‫جایگشت‬‫بر‬‫ی‬‫و‬‫ر‬‫سطرها‬‫و‬‫ن‬‫ستو‬‫های‬‫ماتریس‬A(G)‫به‬‫ماتریس‬
A(H)‫برسیم‬،‫آنگاه‬‫دو‬‫اف‬‫ر‬‫گ‬G‫و‬H‫یکریخت‬‫هستند‬.
16

‫اف‬‫ر‬‫گ‬‫تعریف‬(15)–‫اف‬‫ر‬‫گ‬‫دو‬ ‫یکریختی‬‫م‬‫ز‬‫ال‬ ‫ایط‬‫ر‬‫ش‬
‫یکسان‬‫ن‬‫بو‬‫جه‬‫ر‬‫د‬‫ئوس‬‫ر‬
‫یر‬‫ز‬‫اف‬‫ر‬‫گ‬‫های‬‫یکسان‬
‫تعداد‬‫های‬‫ر‬‫دو‬‫یکسان‬‫به‬‫ل‬‫طو‬‫مشخص‬
‫تعداد‬‫اس‬‫ر‬‫های‬‫یکسان‬‫دو‬‫به‬‫دو‬‫غیر‬‫ر‬‫مجاو‬
‫دو‬‫اف‬‫ر‬‫گ‬‫باید‬‫مسطح‬‫باشند‬
‫اگر‬‫اف‬‫ر‬‫گ‬‫دو‬‫ی‬ ‫بخش‬‫باشد‬‫یکریخت‬‫نیستند‬.
17

‫اف‬‫ر‬‫گ‬‫تعریف‬(16)–‫اف‬‫ر‬‫گ‬‫دو‬ ‫یکریختی‬‫م‬‫ز‬‫ال‬ ‫ایط‬‫ر‬‫ش‬
‫مثال‬
‫اف‬‫ر‬‫گ‬G‫دو‬‫ی‬ ‫بخش‬‫نیست‬‫ولی‬‫اف‬‫ر‬‫گ‬H‫دو‬‫ی‬ ‫بخش‬‫است‬.
‫اف‬‫ر‬‫گ‬G‫یک‬‫اف‬‫ر‬‫گ‬‫مسطح‬‫است‬(‫هیچ‬‫دو‬‫یالی‬‫یکدیگر‬‫ا‬‫ر‬‫قط‬‫نکرده‬‫اند‬)‫و‬‫لی‬
‫اف‬‫ر‬‫گ‬H‫مسطح‬‫نیست‬.
‫در‬‫اف‬‫ر‬‫گ‬G‫ر‬‫دو‬‫به‬‫ل‬‫طو‬5‫میتوانیم‬‫داشته‬،‫باشیم‬‫اما‬‫در‬‫اف‬‫ر‬‫گ‬H‫ر‬‫دو‬‫به‬‫ل‬‫طو‬
‫حداکثر‬4‫میتوانیم‬‫داشته‬‫باشیم‬.
18

‫اف‬‫ر‬‫گ‬‫تعریف‬(17)–‫مکمل‬ ‫اف‬‫ر‬‫گ‬
‫فرض‬‫کنید‬G=(V,E)‫یک‬‫اف‬‫ر‬‫گ‬‫ساده‬‫باشد‬.‫مکمل‬G‫که‬‫با‬‫نماد‬𝐺‫نشان‬‫داده‬
،‫میشود‬‫اف‬‫ر‬‫گ‬‫ساده‬‫ایست‬‫که‬‫مجموعه‬‫ئوس‬‫ر‬‫آن‬V‫است‬‫و‬‫دو‬‫اس‬‫ر‬v‫و‬u‫در‬
‫تی‬‫ر‬‫صو‬‫با‬‫هم‬‫هستند‬‫ر‬‫مجاو‬‫اگر‬‫و‬‫تنها‬‫اگر‬v‫و‬u‫در‬G‫با‬‫هم‬‫ر‬‫مجاو‬‫نباشند‬.
19

‫اف‬‫ر‬‫گ‬‫تعریف‬(18)–‫مکمل‬ ‫اف‬‫ر‬‫گ‬
‫ای‬‫ر‬‫ب‬‫تشخیص‬‫یکریختی‬‫دو‬
‫اف‬‫ر‬‫گ‬،‫اگر‬‫در‬‫مکمل‬‫آنها‬
‫یکریختی‬‫وجود‬‫داشت‬‫آن‬‫د‬‫و‬
‫اف‬‫ر‬‫گ‬‫نیز‬‫یکریخت‬‫خواهن‬‫د‬
‫بود‬.
20

‫اف‬‫ر‬‫گ‬‫تعریف‬(19)–‫مکمل‬‫خود‬ ‫اف‬‫ر‬‫گ‬
‫اف‬‫ر‬‫گ‬G=(V,E)‫خود‬‫مکمل‬‫است‬‫اگر‬𝐺‫و‬𝐺‫یکریخت‬‫باشند‬.
21
𝑓 𝑥 = 𝑐
𝑓 𝑦 = 𝑑
𝑓 𝑤 = 𝑎
𝑓 𝑧 = 𝑏

‫اف‬‫ر‬‫گ‬‫تعریف‬(20)–‫اف‬‫ر‬‫گ‬ ‫جات‬‫ر‬‫د‬‫دنباله‬
‫دنباله‬‫غیر‬‫صعودی‬d=(𝑑1,𝑑2, …, 𝑑 𝑛)‫از‬‫جه‬‫ر‬‫د‬‫ئوس‬‫ر‬‫یک‬‫اف‬‫ر‬‫گ‬‫شامل‬
‫اعداد‬‫صحیح‬‫نامنفی‬‫ا‬‫ر‬‫دنباله‬‫جات‬‫ر‬‫د‬‫اف‬‫ر‬‫گ‬‫میگوییم‬.
‫دنباله‬‫غیر‬‫صعودی‬
‫تعداد‬‫جات‬‫ر‬‫د‬‫فرد‬‫در‬‫این‬‫دنباله‬‫باید‬‫یک‬‫عدد‬‫ج‬‫و‬‫ز‬‫باشد‬.
‫گترین‬‫ر‬‫بز‬‫عضو‬‫دنباله‬(‫شامل‬n‫عدد‬)‫میتواند‬n-1‫باشد‬.
‫در‬‫یک‬‫اف‬‫ر‬‫گ‬‫حداقل‬‫دو‬‫اس‬‫ر‬‫با‬‫جه‬‫ر‬‫د‬‫یکسان‬‫وجود‬‫د‬‫ر‬‫دا‬.
22
𝑑 = (3,3,2,2,1,1)

‫مثال‬
𝑑 = (5,5,5,3,2,2,1,1)
23

‫یتم‬‫ر‬‫الگو‬‫ل‬‫هاو‬–‫حکیمی‬(Havel – Hakimi)
‫دنباله‬‫غیر‬‫صعودی‬d=(𝑑1,𝑑2, …, 𝑑 𝑛)‫از‬‫اعداد‬‫صحیح‬‫نامنفی‬‫افیکی‬‫ر‬‫گ‬
‫است‬‫اگر‬‫و‬‫تنها‬‫اگر‬‫دنباله‬
𝑑=(𝑑2 − 1,𝑑3 − 1, …, 𝑑 𝑑1+1 − 1, 𝑑 𝑑1+1, …, 𝑑 𝑛)
‫افیکی‬‫ر‬‫گ‬‫باشد‬.
‫مثال‬:‫دنباله‬5 4 3 2 1 1‫نمیتواند‬‫یک‬‫دنباله‬‫افیکی‬‫ر‬‫گ‬‫باشد‬.
5 4 3 2 1 1
∗ 3 2 1 0 0
∗ ∗ 1 0 ∗ ∗
24

‫اف‬‫ر‬‫گ‬‫تعریف‬(23)–‫ی‬ ‫بخش‬‫دو‬ ‫اف‬‫ر‬‫گ‬
‫اف‬‫ر‬‫گ‬G=(V,E)‫دو‬‫ی‬ ‫بخش‬‫است‬‫اگر‬‫مجموعه‬‫ئوس‬‫ر‬‫آن‬‫ا‬‫ر‬‫بتوان‬‫به‬‫دو‬‫مجموعه‬
V1‫و‬V2‫چنان‬‫از‬‫ر‬‫اف‬‫کرد‬‫که‬‫هر‬‫یال‬‫در‬‫مجموعه‬E‫یک‬‫اسش‬‫ر‬‫در‬V1‫و‬‫اس‬‫ر‬
‫دیگرش‬‫در‬‫مجموعه‬V2‫باشد‬.
‫اگر‬‫هر‬‫اس‬‫ر‬‫از‬‫مجموعه‬V1‫با‬‫تمام‬‫ئوس‬‫ر‬‫مجموعه‬V2‫ر‬‫مجاو‬‫باشد‬‫آنگاه‬‫اف‬‫ر‬‫گ‬
G‫دو‬‫ی‬ ‫بخش‬‫کامل‬‫است‬.
25

‫اف‬‫ر‬‫گ‬‫تعریف‬(24)–‫ی‬ ‫بخش‬‫دو‬ ‫اف‬‫ر‬‫گ‬
‫هر‬‫اف‬‫ر‬‫گ‬‫دو‬‫ی‬ ‫بخش‬2-‫نگ‬‫ر‬‫پذیر‬‫است‬.
‫میتوان‬‫ئوس‬‫ر‬‫اف‬‫ر‬‫گ‬‫ا‬‫ر‬‫با‬‫دو‬‫نگ‬‫ر‬‫ی‬‫ر‬‫طو‬‫نگ‬‫ر‬‫ی‬‫آمیز‬‫کنیم‬‫که‬‫دو‬‫اس‬‫ر‬‫ر‬‫مجاو‬‫هم‬‫ر‬‫نگ‬
‫نباشند‬.
26

‫اف‬‫ر‬‫گ‬‫تعریف‬(25)–‫خاص‬ ‫های‬ ‫اف‬‫ر‬‫گ‬
1)‫اف‬‫ر‬‫گ‬‫سیکل‬(𝐶 𝑛)
‫تعداد‬‫یالها‬=n
‫تعداد‬‫ئوس‬‫ر‬=n
𝐶 𝑛‫در‬‫تی‬‫ر‬‫صو‬‫دو‬‫ی‬ ‫بخش‬‫است‬‫که‬‫تعداد‬‫ئوس‬‫ر‬‫اف‬‫ر‬‫گ‬‫ج‬‫و‬‫ز‬‫باشد‬.
𝑛 = 2𝑘
27

2)‫اف‬‫ر‬‫گ‬‫چرخ‬(𝑊𝑛)
‫تعداد‬‫یالها‬=𝑛 + 𝑛 = 2𝑛
‫تعداد‬‫ئوس‬‫ر‬=𝑛 + 1

28

3)‫اف‬‫ر‬‫گ‬𝑄 𝑛(n-cube)(‫مکعب‬n)
‫تعداد‬‫ئوس‬‫ر‬=2 𝑛
‫اف‬‫ر‬‫گ‬𝑄 𝑛‫یک‬‫اف‬‫ر‬‫گ‬–n‫منتظم‬‫است‬(‫جه‬‫ر‬‫د‬‫هر‬‫اس‬‫ر‬‫ابر‬‫ر‬‫ب‬n)
‫تعداد‬‫یالها‬=
𝑛2 𝑛
2
= 𝑛2 𝑛−1
29

4)‫اف‬‫ر‬‫گ‬‫مسیر‬𝑃𝑛
‫افی‬‫ر‬‫گ‬‫است‬‫که‬‫دو‬‫اس‬‫ر‬‫ابتدا‬‫و‬‫انتها‬‫از‬‫جه‬‫ر‬‫د‬1‫بوده‬‫و‬‫سایر‬‫ئوس‬‫ر‬‫وسط‬‫جه‬‫ر‬‫د‬2
‫ند‬‫ر‬‫دا‬.
‫تعداد‬‫یالها‬=𝑛 − 1
‫تعداد‬‫ئوس‬‫ر‬=𝑛
30

‫اف‬‫ر‬‫گ‬‫تعریف‬(29)–‫اف‬‫ر‬‫گ‬‫یر‬‫ز‬
‫یر‬‫ز‬‫گراف‬:‫اف‬‫ر‬‫گ‬H‫ا‬‫ر‬‫یر‬‫ز‬‫اف‬‫ر‬‫گ‬G‫نامیم‬‫هرگاه‬
‫اگر‬V(H)=V(G)،‫باشد‬‫آنگاه‬‫یر‬‫ز‬‫گراف‬‫فراگیر‬‫است‬.
‫یر‬‫ز‬‫گراف‬‫القائی‬‫ی‬ ‫اس‬‫ر‬:‫فرض‬‫کنید‬G=(V,E)‫و‬S‫یر‬‫ز‬‫مجموعه‬‫غیر‬‫تهی‬‫از‬
V(G)،‫باشد‬‫آنگاه‬‫اف‬‫ر‬‫یرگ‬‫ز‬H=G[S]=(S,E’)‫از‬G‫ا‬‫ر‬‫یر‬‫ز‬‫اف‬‫ر‬‫گ‬‫القایی‬‫ی‬ ‫اس‬‫ر‬
‫گویند‬‫که‬‫در‬‫آن‬E’‫تمامی‬‫یالها‬‫از‬G‫که‬‫هر‬‫دو‬‫اس‬‫ر‬‫آنها‬‫در‬‫مجموعه‬S‫است‬.
‫یر‬‫ز‬‫گراف‬‫القائی‬‫یالی‬:‫فرض‬‫کنید‬E’‫یر‬‫ز‬‫مجموعه‬E(G)‫و‬V’‫یر‬‫ز‬‫مجموعه‬
V(G)‫باشند‬‫به‬‫یکه‬‫ر‬‫طو‬V’‫شامل‬‫همه‬‫اس‬‫ر‬‫های‬‫دو‬‫ی‬‫سر‬‫یالها‬‫در‬E’‫باشد‬.‫در‬
‫این‬‫ت‬‫ر‬‫صو‬‫اف‬‫ر‬‫گ‬H=(V’,E’)‫ا‬‫ر‬‫یر‬‫ز‬‫اف‬‫ر‬‫گ‬‫القائی‬‫یالی‬‫گویند‬.
31

‫اف‬‫ر‬‫گ‬‫تعریف‬(30)–‫اف‬‫ر‬‫گ‬‫در‬ ‫گشت‬
‫یک‬‫گشت‬‫در‬‫اف‬‫ر‬‫گ‬G،‫دنباله‬‫ای‬‫از‬‫اس‬‫ر‬‫ها‬‫مانند‬
𝑣0 𝑒1 𝑣1 𝑒2…𝑣 𝑘−1 𝑒 𝑘 𝑣 𝑘‫میباشد‬.‫به‬‫یکه‬‫ر‬‫طو‬𝑣𝑖‫و‬𝑣𝑗‫اسهای‬‫ر‬‫یال‬𝑒𝑖
‫میباشند‬.
‫تعداد‬‫یالهای‬‫این‬‫گشت‬‫ا‬‫ر‬‫ل‬‫طو‬‫گشت‬‫گوییم‬.
‫اگر‬‫ابتدا‬‫و‬‫انتهای‬‫این‬‫گشت‬‫اس‬‫ر‬‫یکسانی‬‫باشد‬‫آنگاه‬‫گشت‬‫بسته‬‫و‬‫در‬‫غ‬‫یر‬‫این‬
‫ت‬‫ر‬‫صو‬‫گشت‬‫باز‬‫است‬.
‫در‬‫تی‬‫ر‬‫صو‬‫که‬‫در‬‫یک‬‫گشت‬‫تمامی‬‫یالها‬‫متمایز‬‫باشند‬‫ا‬‫ر‬‫آن‬‫گذر‬‫گوییم‬‫و‬‫در‬‫و‬‫تی‬‫ر‬‫صو‬
‫که‬‫همه‬‫اس‬‫ر‬‫ها‬‫در‬‫یک‬‫گشت‬‫متمایز‬‫باشند‬‫ا‬‫ر‬‫آن‬‫مسیر‬‫گوییم‬.
‫هر‬‫مسیر‬‫یک‬‫گذر‬‫است‬.
‫هر‬‫مسیر‬‫بسته‬‫یک‬‫ر‬‫دو‬‫است‬.
32

‫اف‬‫ر‬‫گ‬‫تعریف‬(31)–‫اف‬‫ر‬‫گ‬‫در‬ ‫گشت‬
‫مثال‬
33
‫گشت‬
𝑣1 𝑣2 𝑣5 𝑣4 𝑣3 𝑣2 𝑣1 𝑣7
‫گذر‬
𝑣1 𝑣2 𝑣5 𝑣4 𝑣3 𝑣2 𝑣6
‫مسیر‬
𝑣1 𝑣2 𝑣6 𝑣5 𝑣8
‫ر‬‫دو‬
𝑣2 𝑣5 𝑣6 𝑣7 𝑣1 𝑣2

‫اف‬‫ر‬‫گ‬‫تعریف‬(32)–‫متصل‬ ‫اس‬‫ر‬‫دو‬(‫دسترس‬ ‫قابل‬)
‫دو‬‫اس‬‫ر‬u‫و‬v‫ا‬‫ر‬‫متصل‬،‫گویند‬‫اگر‬‫بین‬‫آنها‬‫یک‬‫مسیر‬(‫گشت‬)‫وجود‬‫داشته‬‫ب‬‫اشد‬.
‫اف‬‫ر‬‫گ‬G‫همبند‬‫است‬‫اگر‬‫هر‬‫دو‬‫اس‬‫ر‬‫در‬‫اف‬‫ر‬‫گ‬‫متصل‬‫باشند‬.
34

‫اف‬‫ر‬‫گ‬‫تعریف‬(33)–‫اف‬‫ر‬‫گ‬‫دو‬ ‫اجتماع‬
‫اف‬‫ر‬‫گ‬G=(V,E)‫که‬‫در‬‫آن‬𝑉 = 𝑉1 ∪ 𝑉2‫و‬𝐸 = 𝐸1 ∪ 𝐸2‫ا‬‫ر‬‫اجتماع‬‫دو‬
‫اف‬‫ر‬‫گ‬G1‫و‬G2‫گویند‬.‫و‬‫با‬𝐺1 ∪ 𝐺2‫نشان‬‫میدهند‬.
‫اگر‬‫مجموعه‬‫ئوس‬‫ر‬G1‫و‬G2‫ا‬‫ز‬‫مج‬،‫باشند‬‫آنگاه‬‫اجتماه‬‫آندو‬‫ا‬‫ر‬‫به‬‫ت‬‫ر‬‫صو‬
G1+G2‫نشان‬‫میدهند‬.
35

‫اف‬‫ر‬‫گ‬‫تعریف‬(34)–‫اف‬‫ر‬‫گ‬‫دو‬ ‫پیوند‬
‫پیوند‬‫دو‬‫اف‬‫ر‬‫گ‬G1‫و‬G2‫افی‬‫ر‬‫گ‬‫است‬‫که‬‫در‬‫آن‬‫هر‬‫اس‬‫ر‬‫در‬G1‫به‬‫هر‬‫اس‬‫ر‬‫در‬
G2‫متصل‬‫شده‬‫است‬.‫و‬‫آن‬‫ا‬‫ر‬‫با‬𝐺1V 𝐺2‫نشان‬‫میدهند‬.(‫ترکیب‬‫فصلی‬)
36

‫اف‬‫ر‬‫گ‬‫دار‬ ‫جهت‬(1)–‫تعریف‬
‫یک‬‫اف‬‫ر‬‫گ‬‫جهتدار‬D‫تست‬‫ر‬‫عبا‬‫از‬‫ج‬‫و‬‫ز‬(V(D),A(D))‫که‬‫در‬‫آن‬
‫مجموعه‬V(D)‫مجموعه‬‫ئوس‬‫ر‬‫اف‬‫ر‬‫گ‬‫است‬
‫مجموعه‬A(D)‫یالهای‬‫جهت‬‫دار‬‫اف‬‫ر‬‫گ‬‫است‬.
‫جه‬‫ر‬‫د‬‫جی‬‫و‬‫خر‬(𝒅 𝑫
+
(𝒗)):‫ای‬‫ر‬‫ب‬‫هر‬‫اس‬‫ر‬v‫از‬‫اف‬‫ر‬‫گ‬‫جهتدار‬D‫جه‬‫ر‬‫د‬‫جی‬‫و‬‫خر‬‫ابر‬‫ر‬‫ب‬
‫است‬‫با‬‫تعداد‬‫یالهایی‬‫که‬‫اس‬‫ر‬v‫ابتدای‬‫آنها‬‫ار‬‫ر‬‫ق‬‫د‬‫ر‬‫دا‬.
‫جه‬‫ر‬‫د‬‫ودی‬‫ر‬‫و‬(𝒅 𝑫
−
(𝒗)):‫ای‬‫ر‬‫ب‬‫هر‬‫اس‬‫ر‬v‫از‬‫اف‬‫ر‬‫گ‬‫جهتدار‬D‫جه‬‫ر‬‫د‬‫ودی‬‫ر‬‫و‬‫ابر‬‫ر‬‫ب‬
‫است‬‫با‬‫تعداد‬‫یالهایی‬‫که‬‫اس‬‫ر‬v‫انتهای‬‫آنها‬‫ار‬‫ر‬‫ق‬‫د‬‫ر‬‫دا‬.
37

‫اف‬‫ر‬‫گ‬‫دار‬ ‫جهت‬(2)–‫تعریف‬
38
𝒅 𝑫
+
𝒗 𝟏 = 𝟎
𝒅 𝑫
+
𝒗 𝟐 = 𝟐
𝒅 𝑫
+
𝒗 𝟑 = 𝟏
𝒅 𝑫
+
𝒗 𝟒 = 𝟏
𝒅 𝑫
+
𝒗 𝟓 = 𝟎
𝒅 𝑫
+
𝒗 𝟔 = 𝟏
𝒅 𝑫
+
𝒗 𝟕 = 𝟏
𝒅 𝑫
+
𝒗 𝟖 = 𝟐
𝒅 𝑫
+
𝒗 𝟗 = 𝟏
𝒅 𝑫
+
𝒗 𝟏𝟎 = 𝟐
𝒅 𝑫
−
𝒗 𝟏 = 𝟐
𝒅 𝑫
−
𝒗 𝟐 = 𝟎
𝒅 𝑫
−
𝒗 𝟑 = 𝟑
𝒅 𝑫
−
𝒗 𝟒 = 𝟏
𝒅 𝑫
−
𝒗 𝟓 = 𝟐
𝒅 𝑫
−
𝒗 𝟔 = 𝟏
𝒅 𝑫
−
𝒗 𝟕 = 𝟏
𝒅 𝑫
−
𝒗 𝟖 = 𝟐
𝒅 𝑫
−
𝒗 𝟗 = 𝟏
𝒅 𝑫
−
𝒗 𝟏𝟎 = 𝟎

‫اف‬‫ر‬‫گ‬‫دار‬ ‫جهت‬(3)–‫وقوع‬‫و‬ ‫ت‬‫ر‬‫مجاو‬ ‫ماتریس‬
‫ماتریس‬‫ت‬‫ر‬‫مجاو‬A(D):‫اگر‬D‫یک‬‫اف‬‫ر‬‫گ‬‫جهتدار‬‫فاقد‬‫طوقه‬‫باشد،در‬‫این‬
‫ت‬‫ر‬‫صو‬‫ماتریس‬‫ت‬‫ر‬‫مجاو‬D،‫یک‬‫ماتریس‬n*n‫است‬‫که‬‫سطرها‬‫و‬‫ن‬‫ستو‬‫های‬‫آن‬‫با‬
‫اس‬‫ر‬‫ها‬‫ی‬‫نامگذار‬‫میشوند‬‫و‬‫ایه‬‫ر‬‫د‬ij‫ابر‬‫ر‬‫ب‬‫است‬‫با‬‫تعداد‬‫کمان‬‫ها‬‫از‬‫اس‬‫ر‬𝑣𝑖‫به‬‫اس‬‫ر‬
𝑣𝑗‫است‬.
‫ی‬ ‫ماترس‬‫وقوع‬M(D):‫اگر‬D‫یک‬‫اف‬‫ر‬‫گ‬‫جهتدار‬،‫باشد‬‫ماتریس‬‫وقوع‬D،‫یک‬
‫ماتریس‬n*m‫است‬‫که‬‫اگر‬‫سطرها‬‫با‬‫اس‬‫ر‬‫ها‬‫و‬‫ن‬‫ستو‬‫ها‬‫با‬‫کمان‬‫ها‬‫ی‬‫نامگذار‬
،‫شوند‬‫ایه‬‫ر‬‫د‬ij‫ابر‬‫ر‬‫ب‬‫یک‬‫است‬‫اگر‬‫اس‬‫ر‬𝑣𝑖‫ابتدای‬‫کمان‬𝑒𝑖،‫باشد‬‫و‬‫ایه‬‫ر‬‫د‬ij‫ابر‬‫ر‬‫ب‬-
1‫است‬‫اگر‬‫اس‬‫ر‬𝑣𝑖‫انتهای‬‫کمان‬𝑒𝑖‫باشد‬‫و‬‫در‬‫غیر‬‫ت‬‫ر‬‫اینصو‬‫ایه‬‫ر‬‫د‬ij‫ابر‬‫ر‬‫ب‬‫صفر‬
‫خواهد‬‫بود‬.
39

‫اف‬‫ر‬‫گ‬‫دار‬ ‫جهت‬(4)–‫وقوع‬‫و‬ ‫ت‬‫ر‬‫مجاو‬ ‫ماتریس‬
40

‫خت‬‫ر‬‫د‬(1)–‫تعریف‬
‫اف‬‫ر‬‫گ‬T=(V,E)‫ا‬‫ر‬‫خت‬‫ر‬‫د‬‫گوییم‬،‫هرگاه‬‫ن‬‫بدو‬‫جهت‬،‫ن‬‫بدو‬‫طوقه‬،‫همبند‬،‫و‬‫بد‬‫ن‬‫و‬
‫ر‬‫دو‬‫باشد‬.
‫در‬‫هر‬‫خت‬‫ر‬‫د‬‫یک‬‫مسیر‬‫یکتا‬‫بین‬‫هر‬‫دو‬‫اس‬‫ر‬‫متمایز‬‫وجود‬‫د‬‫ر‬‫دا‬.
𝑉 = 𝐸 + 1
‫هر‬‫خت‬‫ر‬‫د‬T=(V,E)‫با‬𝑉 > 1‫حداقل‬‫دو‬‫اس‬‫ر‬‫یان‬‫ز‬‫آو‬‫د‬‫ر‬‫دا‬.
41

‫خت‬‫ر‬‫د‬(2)–‫ندار‬‫ز‬‫و‬ ‫اف‬‫ر‬‫گ‬
‫اگر‬‫در‬‫اف‬‫ر‬‫گ‬‫همبند‬‫و‬‫ن‬‫بدو‬‫طوقه‬G،‫به‬‫هر‬‫یال‬‫یک‬‫عدد‬‫حقیقی‬‫نسبت‬،‫دهیم‬
‫اف‬‫ر‬‫گ‬‫ندار‬‫ز‬‫و‬‫گفته‬‫میشود‬‫و‬‫به‬‫عدد‬‫نسبت‬‫داده‬‫شده‬‫ن‬‫ز‬‫و‬‫آن‬‫یال‬‫گویند‬.
42

‫خت‬‫ر‬‫د‬(3)–‫کمینه‬ ‫اگیر‬‫ر‬‫ف‬‫خت‬‫ر‬‫د‬
‫در‬‫یک‬‫اف‬‫ر‬‫گ‬‫ندار‬‫ز‬‫و‬G،‫ختی‬‫ر‬‫د‬‫که‬‫شامل‬‫تمام‬‫ئوس‬‫ر‬‫اف‬‫ر‬‫گ‬‫باشد‬‫و‬‫مجموع‬‫ن‬‫ز‬‫و‬‫یال‬‫ها‬
‫از‬‫سایر‬‫خت‬‫ر‬‫د‬‫های‬‫دیگر‬‫کمتر‬،‫باشد‬‫ا‬‫ر‬‫خت‬‫ر‬‫د‬‫اگیر‬‫ر‬‫ف‬‫کمینه‬‫گویند‬.
‫دو‬‫یتم‬‫ر‬‫الگو‬‫ای‬‫ر‬‫ب‬‫یافتن‬‫خت‬‫ر‬‫د‬‫اگیر‬‫ر‬‫ف‬‫کمینه‬‫وجود‬‫د‬‫ر‬‫دا‬
‫یتم‬‫ر‬‫الگو‬‫اسکال‬‫ر‬‫ک‬
‫یتم‬‫ر‬‫الگو‬‫پریم‬

43

‫خت‬‫ر‬‫د‬(4)–‫اگیر‬‫ر‬‫ف‬‫خت‬‫ر‬‫د‬‫کمینه‬-‫اسکال‬‫ر‬‫ک‬‫یتم‬‫ر‬‫الگو‬
‫افی‬‫ر‬‫گ‬‫که‬n‫اس‬‫ر‬‫د‬‫ر‬‫دا‬‫خت‬‫ر‬‫د‬‫د‬‫ر‬‫مو‬‫نظر‬‫باید‬n-1‫یال‬‫داشته‬‫باشد‬.
‫مرحله‬1.𝑖 = 1‫و‬‫یال‬‫با‬‫کوچکترین‬‫ن‬‫ز‬‫و‬‫ا‬‫ر‬‫انتخاب‬‫میکنیم‬.
‫مرحله‬2.‫ای‬‫ر‬‫ب‬1 ≤ 𝑖 ≤ 𝑛 − 2‫اگر‬‫یالهای‬𝑒1‫و‬𝑒2‫و‬𝑒3‫و‬...𝑒𝑖‫قبال‬‫انتخاب‬
‫شده‬‫اند‬‫یال‬𝑒𝑖+1‫ا‬‫ر‬‫از‬‫میان‬‫یالهای‬‫باقیمانده‬‫به‬‫ت‬‫ر‬‫صو‬‫یر‬‫ز‬‫انتخاب‬‫میکنیم‬.
‫ن‬‫ز‬‫و‬‫یال‬𝑒𝑖+1‫از‬‫بین‬‫یالهای‬‫باقیمانده‬‫کمتر‬‫باشد‬
‫اف‬‫ر‬‫یرگ‬‫ز‬‫تشکیل‬‫دهنده‬‫توسط‬‫یالهای‬𝑒1‫و‬𝑒2‫و‬𝑒3‫و‬...𝑒𝑖‫و‬𝑒𝑖+1
‫تشکیل‬‫ر‬‫دو‬‫ندهد‬.
‫مرحله‬3.𝑖 ← 𝑖 + 1
‫مرحله‬4.‫اگر‬𝑖 = 𝑛 − 1‫یر‬‫ز‬‫اف‬‫ر‬‫گ‬‫ایجاد‬‫شده‬‫یک‬‫خت‬‫ر‬‫د‬‫اگیر‬‫ر‬‫ف‬‫کمینه‬‫از‬‫اف‬‫ر‬‫گ‬
‫ندار‬‫ز‬‫و‬G‫است‬‫در‬‫غیر‬‫این‬‫ت‬‫ر‬‫صو‬‫به‬‫مرحله‬2‫و‬‫بر‬.
44

‫خت‬‫ر‬‫د‬(5)–‫کمینه‬ ‫اگیر‬‫ر‬‫ف‬‫خت‬‫ر‬‫د‬-‫اسکال‬‫ر‬‫ک‬‫یتم‬‫ر‬‫الگو‬
45

‫خت‬‫ر‬‫د‬(6)–‫کمینه‬ ‫اگیر‬‫ر‬‫ف‬‫خت‬‫ر‬‫د‬-‫اسکال‬‫ر‬‫ک‬‫یتم‬‫ر‬‫الگو‬
‫خت‬‫ر‬‫د‬‫اگیر‬‫ر‬‫ف‬‫کمینه‬‫با‬‫یتم‬‫ر‬‫الگو‬‫اسکال‬‫ر‬‫ک‬‫یک‬‫خت‬‫ر‬‫د‬‫یکتا‬‫نخواهد‬‫بود‬‫و‬‫م‬‫یتواند‬‫هر‬
‫خت‬‫ر‬‫د‬‫ی‬‫دیگر‬‫نیز‬‫طبق‬‫این‬‫یتم‬‫ر‬‫الگو‬‫نیز‬‫انتخاب‬‫شود‬.
‫خت‬‫ر‬‫د‬‫بدست‬‫آمده‬‫با‬‫یتم‬‫ر‬‫الگو‬‫اسکال‬‫ر‬‫ک‬‫در‬‫حین‬‫تشکیل‬‫آن‬‫ناهمبندی‬‫د‬‫ر‬‫دا‬‫د‬‫ر‬
‫تی‬‫ر‬‫صو‬‫که‬‫در‬‫یتم‬‫ر‬‫الگو‬‫پریم‬‫از‬‫ابتدای‬‫تشکیل‬‫این‬‫خت‬‫ر‬‫د‬‫همبندی‬‫آن‬‫عای‬‫ر‬‫ت‬‫میگردد‬.
46

‫خت‬‫ر‬‫د‬(7)–‫کمینه‬ ‫اگیر‬‫ر‬‫ف‬‫خت‬‫ر‬‫د‬–‫پریم‬‫یتم‬‫ر‬‫الگو‬
‫مرحله‬1:𝑖 ← 1‫و‬‫یک‬‫اس‬‫ر‬‫دلخواه‬𝑣1 ∈ 𝑉‫ا‬‫ر‬‫در‬‫مجموعه‬P‫ار‬‫ر‬‫ق‬‫میدهیم‬.
𝑁 = 𝑉 − 𝑣1 , 𝑇 = ∅
‫مرحله‬2:‫به‬‫ای‬‫ز‬‫ا‬1 ≤ 𝑖 ≤ 𝑛 − 1‫که‬‫در‬‫آن‬𝑉 = 𝑛‫فرض‬‫کنیم‬
𝑃 = 𝑣1, 𝑣2, … , 𝑣𝑖
T = 𝑒1, 𝑒2, … , 𝑒𝑖−1
𝑁 = 𝑉 − 𝑃
‫کوتاهترین‬‫یال‬‫در‬G‫ا‬‫ر‬‫که‬‫واصل‬‫ی‬ ‫اس‬‫ر‬‫مانند‬x‫در‬P‫و‬‫ی‬ ‫اس‬‫ر‬‫مانند‬y‫در‬N‫است‬‫ا‬‫ر‬‫به‬
T‫اضافه‬‫میکنیم‬‫سپس‬y‫ادر‬‫ر‬P‫یم‬‫ر‬‫میگذا‬‫و‬‫ا‬‫ر‬‫آن‬‫از‬N‫حذف‬‫میکنیم‬.
‫مرحله‬3:𝑖 ← 𝑖 + 1.‫اگر‬𝑖 = 𝑛‫آنگاه‬‫یر‬‫ز‬‫اف‬‫ر‬‫گ‬‫بدست‬‫آمده‬‫خت‬‫ر‬‫د‬‫اگیر‬‫ر‬‫ف‬‫کمین‬‫ه‬
‫ای‬‫ر‬‫ب‬G‫میباشد‬‫در‬‫ت‬‫ر‬‫اینصو‬‫ر‬‫غی‬‫به‬‫مرحله‬2‫میرویم‬.
47

48
𝑃 = 𝑎
𝑁 = 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ, 𝑖, 𝑗
𝑃 = 𝑎, 𝑐
𝑁 = 𝑏, 𝑑, 𝑒, 𝑓, 𝑔, ℎ, 𝑖, 𝑗
𝑃 = 𝑎, 𝑐, 𝑒
𝑁 = 𝑏, 𝑑, 𝑓, 𝑔, ℎ, 𝑖, 𝑗

49
𝑃 = 𝑎, 𝑐, 𝑒, 𝑏
𝑁 = 𝑑, 𝑓, 𝑔, ℎ, 𝑖, 𝑗
𝑃 = 𝑎, 𝑐, 𝑒, 𝑏, 𝑑
𝑁 = 𝑓, 𝑔, ℎ, 𝑖, 𝑗

‫خت‬‫ر‬‫د‬(10)–‫کمینه‬ ‫اگیر‬‫ر‬‫ف‬ ‫خت‬‫ر‬‫د‬–‫پریم‬‫یتم‬‫ر‬‫الگو‬
50
𝑃 = 𝑎, 𝑐, 𝑒, 𝑏, 𝑑, 𝑓
𝑁 = 𝑔, ℎ, 𝑖, 𝑗

‫خت‬‫ر‬‫د‬(11)–‫اس‬‫ر‬‫دو‬‫بین‬ ‫مسیر‬‫کوتاهترین‬
‫یتم‬‫ر‬‫الگو‬‫ا‬‫ر‬‫دیکست‬(‫ا‬‫ر‬‫دایجست‬-Dijkstra's)
‫مرحله‬1:‫نده‬‫ر‬‫شما‬𝑖 ← 1‫و‬‫فرض‬‫میکنیم‬𝑆0 = 𝑣0،𝑣0‫ا‬‫ر‬‫با‬(0,−)‫و‬‫هر‬𝑣
≠ 𝑣0‫ا‬‫ر‬‫با‬(∞,−)‫عالمت‬‫میدهیم‬.
‫اگر‬n=1،‫در‬‫ت‬‫ر‬‫اینصو‬𝑉 = 𝑣0‫و‬‫یتم‬‫ر‬‫الگو‬‫تمام‬‫است‬.
‫اگر‬𝑛 > 1،‫به‬‫مرحله‬2‫میرویم‬.
‫مرحله‬2:‫ای‬‫ر‬‫ب‬‫هر‬v‫در‬‫ت‬‫ر‬‫صو‬،‫امکان‬‫به‬‫جای‬‫نشان‬‫موجود‬‫ای‬‫ر‬‫ب‬v‫نشان‬‫جدید‬
(𝐿 𝑣 ,𝑦)‫ا‬‫ر‬‫ار‬‫ر‬‫ق‬‫میدهیم‬.‫که‬‫در‬‫آن‬:
𝐿 𝑣 = min
𝑢∈𝑆𝑖
{𝐿 𝑣 , 𝐿 𝑢 + 𝑤𝑡 𝑢, 𝑣 }
‫و‬y‫ی‬ ‫اس‬‫ر‬‫متعلق‬‫به‬𝑆𝑖‫است‬‫که‬‫مینیمم‬L(v)‫ا‬‫ر‬‫میدهد‬
𝑆𝑖+1 = 𝑆𝑖 ∪ {𝑦}
‫مرحله‬3:‫در‬‫تیکه‬‫ر‬‫صو‬𝑖 = 𝑛 − 1،‫توقف‬‫کنید‬.‫در‬‫غیر‬‫ت‬‫ر‬‫اینصو‬𝑖 = 𝑖 + 1
51

‫کوتاهترین‬‫مسیر‬‫که‬‫اس‬‫ر‬a‫ا‬‫ر‬‫به‬‫ئوس‬‫ر‬i‫و‬f‫و‬c‫وصل‬‫میکند‬‫ا‬‫ر‬‫بیابید‬.
52

‫ن‬‫چو‬i=0‫است‬‫ی‬ ‫ئوس‬‫ر‬‫که‬‫از‬‫اس‬‫ر‬a‫بدن‬‫هیچ‬‫واسطه‬‫ای‬‫در‬‫دسترس‬‫هستند‬‫ا‬‫ر‬
‫مشخص‬‫میکنیم‬.
L(b)=14 L(g)=10 L(h)=17 L(c)=L(f)=L(i)=∞
‫به‬‫هر‬‫کدام‬‫از‬‫این‬‫ئوس‬‫ر‬‫یک‬‫برچسب‬‫میدهیم‬
b:(14,a) g:(10,a) h:(17,a)
‫ن‬‫چو‬‫اس‬‫ر‬g‫کمترین‬‫ن‬‫ز‬‫و‬‫ا‬‫ر‬‫د‬‫ر‬‫دا‬‫اس‬‫ر‬g‫ا‬‫ر‬‫انتخاب‬‫میکنیم‬.
53
𝑆0 = 𝑎
𝑎 = 𝑣0
𝑖 = 0
𝑎 ∶ 0, −
𝑏, 𝑐, 𝑓, 𝑔, ℎ, 𝑖 ∶ (∞, −)
𝑆0 = {𝑏, 𝑐, 𝑓, 𝑔, ℎ, 𝑖 }

L(b)=min{14,10+3}=13 : (13,g)
L(h)=min{17,10+6}=16 : (16,g)
L(i)=min{∞,10+4}=14 : (14,g)
L(c)=L(f)=∞
‫ن‬‫چو‬‫اس‬‫ر‬b‫کمترین‬‫ن‬‫ز‬‫و‬‫ا‬‫ر‬‫د‬‫ر‬‫دا‬‫اس‬‫ر‬b‫ا‬‫ر‬‫انتخاب‬‫میکنیم‬.
54
𝑣1 = 𝑔
𝑆1 = 𝑎, 𝑔
𝑖 = 1
𝑆1 = {𝑏, 𝑐, 𝑓, ℎ, 𝑖 }

L(c)=22 : (22,b)
L(f)=23 : (23,b)
L(h)=16 : (16,g)
L(i)=14 : (14,g)
‫ن‬‫چو‬‫اس‬‫ر‬i‫کمترین‬‫ن‬‫ز‬‫و‬‫ا‬‫ر‬‫د‬‫ر‬‫دا‬‫اس‬‫ر‬i‫ا‬‫ر‬‫انتخاب‬‫میکنیم‬.
55
𝑣2 = 𝑏
𝑆2 = 𝑎, 𝑔, 𝑏
𝑖 = 2
𝑆2 = {𝑐, 𝑓, ℎ, 𝑖 }

L(c)=22 : (22,b)
L(f)=21 : (21,i)
L(h)=15 : (15,i)
‫ن‬‫چو‬‫اس‬‫ر‬h‫کمترین‬‫ن‬‫ز‬‫و‬‫ا‬‫ر‬‫د‬‫ر‬‫دا‬‫اس‬‫ر‬h‫ا‬‫ر‬‫انتخاب‬‫میکنیم‬.
56
𝑣3 = 𝑖
𝑆3 = 𝑎, 𝑔, 𝑏, 𝑖
𝑖 = 3
𝑆3 = {𝑐, 𝑓, ℎ }

L(c)=22 : (22,b)
L(f)=21 : (21,i)
‫ن‬‫چو‬‫اس‬‫ر‬f‫کمترین‬‫ن‬‫ز‬‫و‬‫ا‬‫ر‬‫د‬‫ر‬‫دا‬‫اس‬‫ر‬f‫ا‬‫ر‬‫انتخاب‬‫میکنیم‬.
57
𝑣4 = ℎ
𝑆4 = 𝑎, 𝑔, 𝑏, 𝑖, ℎ
𝑖 = 4
𝑆4 = {𝑐, 𝑓}

L(c)=22 : (22,b)
‫ن‬‫چو‬‫اس‬‫ر‬c‫آخرین‬‫اس‬‫ر‬‫باقیمانده‬‫است‬‫در‬‫مرحله‬‫آخر‬‫نیز‬‫این‬‫اس‬‫ر‬‫ا‬‫ر‬‫انتخاب‬‫میکن‬‫یم‬.
58
𝑣5 = 𝑓
𝑆5 = 𝑎, 𝑔, 𝑏, 𝑖, ℎ, 𝑓
𝑖 = 5
𝑆5 = {𝑐}

59
𝑣5 = 𝑐
𝑆6 = 𝑎, 𝑔, 𝑏, 𝑖, ℎ, 𝑓, 𝑐
𝑖 = 6 = 𝑛 − 1
𝑆5 = {}

‫خت‬‫ر‬‫د‬(20)–

60

�ݺ�ߣ

Graph theory

More Related Content

Graph theory