Page 44 - C112215

ِ
.داد باوج نآ هب ناوتب لبق لاثم فارگ رادومن ندید اب هک دینک حرطم یرگید لاؤس :هلئسم
طاقن زا یا هعومجم زا تسا لکشتم فارگ کی میدید هک روط نامه

ره هب و سأر طاقن نیا زا کی ره هب هک ،اه طخ هراپ زا یا هعومجم و
ًامتح تسین مزلا اه لای هک دینک هجوت .مییوگ یم لای اه طخ هراپ زا کی

ره رد و دنشاب زین ینحنم تروص هب دنناوت یم و دنشاب تسار طخ هراپ
ار فارگ کی میدید هک روط نامه .دشاب هتشاد رارق یسأر دیاب لای ِ رس

یاهدامن اب ار نآ ناوت یم زین و داد ناشن نآ ِ رادومن مسر اب ناوت یم
G
و یتامدقم فیرعت دنچ هداس یلکش هب همادا رد .درک یفرعم یضایر
5 لکش
.مینک یم یسررب ار فارگ کی شیامن هوحن
ٔ

.مییامن یم حرطم زین ار فیراعت یخرب نآ یسررب اب و میریگ یم رظن رد ،5 لکش دننام ،لای 10 و سأر 9 اب ار G فارگ
1
یضایر یاهدامن اب ،لااب لکش اب نآ شیامن یاج هب ناوت یم تساه لای و سوئر زا یا هعومجم فارگ کی هکنیا هب هجوت اب
.داد شیامن ریز تروص هب ار نآ سوئر و اه لای هعومجم
ٔ
2
G فارگ یاه سأر هعومجم V (G ) = {v , v , ... , v , v }
ٔ
9
8
2
1
3
G فارگ یاه لای هعومجم E (G ) = {v v , v v , v v , v v , v v , v v , v v , v v , v v , v v }
ٔ
6 8
2 3
1 8
4 6
5 7
2 5
4 5
7 8
1 2
1 4
هعومجم ود نتشاد اب نینچمه و دیسیونب ار E (G ) و V (G ) یاه هعومجم دیناوت یم امش ،فارگ ِ لکش نتشاد اب ،حوضو هب
ٔ
()
)میهد یم شیامن زین VG اب ار نآ هک V (G ) هعومجم یاضعا دادعت( ( ()nV G ) دادعت هب ادتبا دیناوت یم E (G ) و V (G )
ٔ
.دییامن لصو مه هب ار رظانتم یاه سأر E (G ) هب هجوت اب سپس و دییامن صخشم )سأر( هطقن
.مینک نییعت تهج اه لای یارب تسا مزلا تاقوا یهاگ دیدرک هظحلام لابتوف یاه میت لاثم رد هک روط نامه
تلاح نیا رد .مییوگ یم راد تهج فارگ ،دشاب هدش نییعت تهج نآ یاه لای یارب هک یفارگ هب
بترم جوز اب ار اه لای تسا سأر مادک تمس هب سأر مادک تمس زا لای کی تهج هکنیا شیامن یارب
شیامن هنوگ نیا ار 6 لکش راد تهج فارگ یاه لای و سوئر هعومجم لاثم روط هب .میهد یم شیامن
ٔ
.میهد یم
a
c
E
db
6 لکش V = {a , b , c , d} {( , ),( , ),( , )( , ) }
ac
a
b
سلاک رد راک
.دیشکب ار رظن دروم فارگ لکش اهنآ هب هجوت اب .دنا هدش هداد ریز تروص هب E (G ) و V (G ) هعومجم ود ــ
ٔ
V (G ) = {v , v , ... , v } V (G ) = {a , b , c , d}
فلا( 1 2 6 ب(
E (G ) = {v v , v v , v v , v v } E (G ) = {(a , b) , (b , c) , (c , b) , (c , d ) , (d , a)}
6 1
2 5
1 4
5 1
.دوش یم هتفرگ رظن رد یهتان هراومه فارگ سوئر هعومجم ــ1
2 ــ Vertex 3 ــ Edge
34 یزاس لدم و فارگ :مود لصف