Page 49 - C112215

هتشاد دوجو ریسم کی لقادح نآ ِ سأر ود ره نیب هاگره میمان یم دنبمه ار G فارگ :فارگ کی یدنبمهان و یدنبمه
لاثم اریز تسا دنبمهان G فارگ و دنبمه 20 لکش رد H فارگ لاثم روط هب .میمان یم دنبمهان ار نآ تروص نیا ریغ رد ،دشاب
ً
.درادن دوجو یریسم چیه w و v سوئر نیب

20 لکش

تیلاعف

.دینک مسر هاوخلد فارگ هس 1
.دینک هبساحم دیا هدرک مسر هک ار یفارگ 3 زا کی ره سوئر تاجرد عومجم 2
.دییامن هبساحم ار فارگ 3 زا کی ره یاه لای دادعت 3

.دراد دوجو فارگ کی سوئر تاجرد عومجم و اه لای دادعت نیب یا هطبار هچ دینز یم سدح 4

.دینک ثحب هراب نیا رد و هدرک حرطم ناتناتسود اب ار دوخ خساپ 5

تیلاعف

.دیریگب رظن رد e m و ... , e , e لای m و v n و ... , v , v ِ سأر n اب G دننام هاوخلد فارگ کی 1
2
1
2
1
.دینک فذح ار G فارگ یاه لای مامت 2
یطابترا هچ ددع ود نیا و تسا دنچ لصاح فارگ یاه لای دادعت ؟تسا دنچ لصاح فارگ سوئر مامت تاجرد عومجم 3
؟دنراد مه اب

3 لاؤس هب و دیهد رارق )تشاد رارق اهنآ نیب ندش فذح زا لبق e هک یسأر ود نامه نیب( دوخ یاج رد ار e لای 4
1
1
.دیهد باوج
ره ندرک هفاضا زا سپ و دیسرب G هیلوا فارگ هب ات دیهد رارق دوخ یاج رد یکی یکی ار e m و ... , e , e یاه لای مامت 5
ٔ
3
2
.دیهد باوج 3 لاؤس هب هدش هتخاس دیدج فارگ یارب ًاددجم لای
؟ارچ ؟دشاب درف یددع دناوت یم فارگ کی سوئر تاجرد عومجم ایآ 6
n
+
=
v
v
.دییامن نایب ار دوخ للادتسا ∑ deg( ) deg( ) deg( ) + v 2 + deg( ) = v n 2 m یواست یارب 7
i
1
i=1
.دومن نایب ار ریز هیضق ناوت یم ،میدروآ تسد هب تیلاعف نیا رد هچنآ هب هجوت اب
ٔ
:هاگنآ ،دنشاب نآ سوئر هعومجم V = {v , v , ... , v p} و q هزادنا و p هبترم اب فارگ کی G رگا :هیضق
ٔ
ٔ
ٔ
1
2
p
∑ degv = 2 q
i
i=1
فارگ یفرعم :لّ وا سرد 39