Page 48 - C112215

v
یاه فارگ رد v سأر هجرد بیترت هب d G () و d G (v ) و دشاب نآ ِ سأر کی v و سأر n اب فارگ کی G رگا :1 هلئسم
ٔ
.دیروآ تسد هب ار d G () + d G ( ) رادقم ،دنشاب G و G
v
v
؟دشاب هتشاد دناوت یم لای دنچ رثکادح یسأر n فارگ کی :2 هلئسم
.دیروآ تسد هب ار () +qG qG
() رادقم ،دشاب یسأر n فارگ کی G رگا :3 هلئسم

اب ار یسأر n ِ لماک فارگ .میمان یم لماک فارگ دشاب رواجم ، ِ رگید ِ سوئر مامت اب نآ سأر ره هک ار یفارگ :لماک فارگ

ــ
.تسا مظتنم n - 1 و یسأر n فارگ کی K n تفگ ناوت یم .میهد یم شیامن K n
؟دراد لای دنچ یسأر p لماک فارگ کی :1 هلئسم

؟دراد دوجو K p و G ،G یاه فارگ یاه لای دادعت نیب یا هطبار هچ ،دشاب یسأر p فارگ کی G رگا :2 هلئسم
؟تسا یفارگ عون هچ لماک فارگ لمکم :3 هلئسم

ود هبود سوئر زا یا هلابند G رد )ریسم u ــ v کی( v هب u زا ریسم کی ،دنشاب G فارگ زا سأر ود v و u رگا :ریسم

لوط .دنشاب مه رواجم G رد هلابند نیا یلاوتم سأر ود ره هک یروط هب دوش یم متخ v هب و عورش u زا هک تسا G رد زیامتم
هک مینک یم دادرارق .)ریسم نآ رد دوجوم سوئر دادعت زا رتمک یکی( ریسم نآ رد دوجوم یاه لای دادعت اب تسا ربارب ریسم کی
.شدوخ هب v سأر زا رفص لوط اب تسا ریسم کی ،v ِ سأر کی اهنت زا لکشتم هلابند
ٔ
لاثم
.تسا 2 لوط هب ریسم u ــ v کی uwv

.تسا 4 لوط هب ریسم u ــ v کی u z y wv

17 لکش

.میهد یم شیامن P n اب دشاب هدش لیکشت یسأر n ِریسم کی زا اهنت هک ار یفارگ

.تسا هدش هداد شیامن 18 لکش رد P لاثم روط هب
18 لکش 5

کی ار تسا رواجم یدعب سأر اب سأر ره نآ رد هک زیامتم ود هب ود سوئر زا (n ≥ 3) v v v ... v n v هلابند :رود
1 2 3 1 ٔ
6 و 4 و 3 لوط اب بیترت هب ییاهرود x w v u z y x ،y w u z y ،u v w u 17 لکش فارگ رد لاثم روط هب .میمان یم n لوط هب رود

.دنتسه

.میهد یم شیامن C n اب ار دشاب هدش لیکشت یسأر n ِرود کی زا اهنت هک ار یفارگ
.تسا هدش هداد شیامن 19 لکش رد C لاثم روط هب
5

.دیبایب 5 لوط هب یرود ،17 لکش فارگ رد :هلئسم
19 لکش

38 یزاس لدم و فارگ :مود لصف