Page 45 - C112215

صخشم دیاب هک تسا نیا تسا مهم هچنآ .تسین رظندم ییاتکی شور )فارگ لکش( فارگ کی رادومن مسر یارب :هجوت
یاه هعومجم نتشون اب لاثم روط هب .تسا لصتم سوئر مادک هب لای مادک و دراد لای دنچ و سأر دنچ رظن دروم فارگ هک دشاب

.دنهد یم شیامن ار فارگ کی ود ره دیهد ناشن ،ریز یاه لکش زا کی ره یارب E (G ) و V (G )

7 لکش

V (G ) = { } V (G ) = { }
1 2
E (G ) = { } E (G ) = { }
1 2
()
شیامن p (G ) اب و مییوگ یم فارگ نآ هبترم ار VG ینعی G فارگ یاه سأر دادعت :فارگ کی ۀزادنا و هبترم
ٔ
()
راک یتحار یارب لاومعم .میهد یم شیامن q (G ) اب و مییوگ یم G فارگ هزادنا ار EG ینعی فارگ یاه لای دادعت و میهد یم
ً
ٔ
و 5 هبترم زا 7 لکش رد هدش هداد شیامن یاه فارگ لاثم روط هب .مینک یم هدافتسا q زا q (G ) یاج هب و p زا p (G ) یاج هب
ٔ
.q = 6 و p = 5 نیاربانب .دنتسه 6 هزادنا
ٔ
زا ییاه لای دادعت اب تسا ربارب G فارگ رد v سأر هجرد :سأر کی ۀجرد
ٔ
ای deg (v ) اب رت هداس روط هب ای deg G (v ) اب ار نآ و دنا لصتم v سأر هب هک G فارگ

دشاب جوز رگا و درف سأر ار نآ دشاب درف سأر کی هجرد رگا .میهد یم شیامن d (v )
ٔ
:میراد لباقم لکش رد لاثم روط هب .میمان یم جوز سأر ار نآ

deg (v ) = 3 , deg (v ) = 4
5
1
8 لکش
،دنشاب k ددع اب ربارب و یواسم مه اب نآ سوئر مامت هجرد هک ار یفارگ :مظتنم ـ K فارگ
ٔ
.تسا مظتنم - 3 ِ یسأر 6 فارگ کی 9 لکش فارگ لاثم .میمان یم مظتنم - k فارگ
ً

ای( اهنت سأر ،دشابن لصتم نآ هب یلای چیه ینعی ؛دشاب رفص نآ هجرد هک یسأر هب :اهنت سأر
ٔ
9 لکش
.مییوگ یم )هلوزیا

فارگ زا روظنم نیاربانب .میمان یم یهت فارگ ،دشاب هتشادن یلای چیه ینعی ،دنشاب اهنت سأر نآ سوئر مامت هک ار یفارگ
ِ
.تسا لای نودب و اهنت سأر n لماش یفارگ ،یسأر n ِ یهت

فارگ یفرعم :لّ وا سرد 35