Page 46 - C112215
P. 46
سلاک رد راک
ِ
ِ
.دنا جوز سوئر مادک و درف سوئر مادک دینک صخشم و دیسیونب ار 8 لکش فارگ سوئر ریاس هجرد
ٔ
نینچمه .دشاب هتشاد دوجو لای کی زا شیب تسا نکمم فارگ کی زا سأر ود نیب
ِ
هب تروص نیا رد هک دیامن لصو سأر نآ دوخ هب ار سأر کی تسا نکمم لای کی
1
یفارگ .دنا هدش هداد شیامن 10 لکش رد دروم ود نیا .دوش یم هتفگ هقوط لای نیا
.مییوگ یم هداس فارگ ار دشاب هداتفین قافتا دروم ود نیا زا کی چیه نآ رد هک ار
رد ام .تسین هداس فارگ کی گربسگینوک لپ یزاس لدم زا لصاح فارگ هک میدید
10 لکش
زا نامروظنم دعب هب نیا زا و درک میهاوخ یسررب ار هداس یاه فارگ طقف باتک نیا
.تسا هداس فارگ ،فارگ
مییوگ رواجم ای هیاسمه ِ سأر ود ار v و u سأر ود :)هیاسمه( رواجم سأر ود
فارگ رد لاثم روط هب .u v ∈E (G ) ینعی ،دنشاب هدش لصو مه هب یلای طسوت هاگره
v و v و v سوئر اب v سأر و تسا هیاسمه v و v سوئر اب v سأر ،11 لکش
4 3 1 2 5 2 1
.تسا هیاسمه
ار شدوخ یلای چیه هک دیشاب هتشاد هجوت فارگ کی رادومن مسر نامز رد :هجوت
11 لکش تسین لای نآ رس ود هب طوبرم هک یسأر یور زا دیابن یلای چیه نینچمه و دنکن عطق
.دیامن روبع
لصتم v سأر هب هک G فارگ زا ییاه سأر هعومجم هب ،v ∈ V (G ) مینک ضرف :سأر کی یاه هیاسمه هعومجم
ٔ
ٔ
ِ
ِ
ِ
هتسب یگیاسمه« N G (v) هب v سأر دوخ ندرک هفاضا .میهد یم شیامن N G (v) اب و مییوگ یم »v سأر زاب یگیاسمه« ،دنتسه
ٔ
:داد شیامن ریز تروص هب ار هعومجم ود نیا ناوت یم .میهد یم شیامن N G [v] اب ار نآ هک دهد یم تسد هب ار »v سأر
N G (v) = {u ∈ V (G ) : uv ∈ E (G )}
v
[] N
v
Nv = G ( ) { }
G
:میراد 12 لکش فارگ رد لاثم روط هب
b
N G (a) = {b} N G [a] = {a , b}
c
a
N G (c) = {b , d , g} N G [c] = {b , c , d , g}
g
f N G (f ) = ∅ N G [ f ] = {f }
d
e
اهنآ یود ره هک دشاب هتشاد دوجو یسأر هاگره مییوگ رواجم ار لای ود :رواجم لای ود
12 لکش
.دنارواجم cd و bc یاه لای ،12 لکش رد لاثم روط هب .دنشاب لصتم نآ هب
1 ــ Loop
36 یزاس لدم و فارگ :مود لصف
