رفتن به مطلب

ارسال های توصیه شده

سلام

سوال وجواب هایی دررابطه با موضوع گراف ها

امیدوارم به درد دوستان بخوره

سؤال 1 : بنا بر قضیه بالا نشان دهید تعداد رئوس فرد یک گراف زوج است.

************

CMAIN.1.gif

 

چون

CMAIN.2.gifعددی زوج است بنابراین داریم:CMAIN.3.gifپس :CMAIN.4.gif

لینک به دیدگاه

سؤال 2) می توان نشان داد که هر مسیر حتما گذر است ولی عکس آن برقرار نیست .

 

برای عکس مطلب فوق یک مثال بیاورید .

************

CMAIN.5.gif

 

گذری که مسیر نیست.

image001.png

لینک به دیدگاه

سؤال 3) گراف G را دو بخشی گویند اگر و فقط اگر دارای دوری به طول فرد نباشد .

عکس قضیه فوق را اثبات کنید .

************

اگر G همبند باشد، و دور فرد نداشته باشد، a را یک رأس دلخواه از گراف G در نظر میگیریم و قرار می دهیم :CMAIN.6.gifوCMAIN.7.gifدر این صورت CMAIN.8.gifمجموعه CMAIN.9.gif را افراز میکنند .ادعا می کنیم CMAIN.10.gifمجموعه های مستقل هستند، اگر CMAIN.11.gifدر این صورت طبق تعریف

CMAIN.12.gif ، مسیر های CMAIN.13.gif به طول زوج وجود دارند که

CMAIN.14.gif و CMAIN.15.gif

حال اگر CMAIN.16.gif باشند آنگاه طول گشت بسته CMAIN.17.gif فرد است و لذا دارای دوری به طول فرد می باشد که با فرض در تناقض است. بنابراین هیچکام از رئوس مجموعه CMAIN.18.gifبا هم در ارتباط نیستند . همینطور ثابت می شود که اعضای مجموعه CMAIN.19.gif نیز با همدیگر رابطه ندارند . در نتیجه گرافCMAIN.20.gif دوبخشی است

لینک به دیدگاه

سوال 5) ثابت کنید اگر G یک گراف مسطح باشد و محیط آن 5 باشد در اینصورت

CMAIN.22.gif

(توجه: منظور از محیط طول کوتاهترین دور G است .)

************

اثبات: مجموعه S را شامل همه زوج مرتب های

CMAIN.23.gif میگیریم . این بدین معناست که مثلاً داریم که CMAIN.24.gif وجه اول است ، حال چون تعداد وجوه گراف CMAIN.25.gif ، CMAIN.26.gif تا است و هر وجه حداقل 5 یال دارد ، بنابراین مجموعه S حداقل شامل CMAIN.27.gif عضو است.و CMAIN.28.gif از طرفی چون داشتیم هر یال حداکثر متعلق به دو وجه است پس CMAIN.29.gif است .بنابراین داریم : CMAIN.30.gif و طبق فرمول اویلر داریم : CMAIN.31.gif در نتیجه :

CMAIN.32.gif

لینک به دیدگاه

سؤال 6) اگر کمترین وجه G را با

CMAIN.33.gif و بیشترین آنرا با CMAIN.34.gif نمایش دهیم ، نشان دهید: CMAIN.35.gif

************

میدانیم که

Graph.1.gifاما از طرفی چونGraph.2.gifبزرگترین درجه رئوس گراف میباشد داریم:Graph.3.gif

 

 

همینطور برایGraph.4.gif چونGraph.4.gif کوچکترین درجه رئوس گراف میباشد داریم :

Graph.5.gif

که از این دو تساوی داریم:

CMAIN.35.gif

لینک به دیدگاه

سؤال 7) اگر هرجفت از گزاره های زیر رخ دهد ثابت کنید سومی رخ خواهد داد.:

1) G همبند است . 2) G فاقد دور است. 3) CMAIN.36.gif

************

CMAIN.37.gif با توجه به تعریف درخت داریم که گراف همبند فاقد دور یک درخت است . حال ثابت می کنیم که CMAIN.36.gif استقرا : با استقرا بر روی v ثابت می کنیم.

CMAIN.38.gif

 

فرض می کنیم که حکم برای هر درخت با k رأس درست باشد . یعنی CMAIN.39.gif

حال درخت با k+1 رأس را در نظر گرفته و با توجه به اینکه هر درخت حداقل دو رأس از درجه یک دارد اگر از این درخت یک رأس از درجه یک و یال مربوط به آن را حذف کنیم ، درختی پدید می آید با k رأس و طبق فرض استقرا دارای k-1 یال . پس درخت k+1 رأسی دارای k یال است . بدین ترتیب حکم ثابت شد.

************

CMAIN.40.gif برهان خلف :

اگر گراف با مشخصات 2 و3 همبند نباشد ، بنابراین ناهمبند خواهد بود و دارای مؤلفه های همبندی که چون دارای دور نیست هر مؤلفه همبندی یک درخت خواهد بود . که برای هر مؤلفه داریم : CMAIN.41.gif بنابراین :

CMAIN.42.gif

 

که در آن n تعداد مؤلفه های همبندی است . و طبق فرض 3 داشتیم : CMAIN.36.gif بنابراین داریم : n=1 در نتیجه G همبند است و بنابراین حکم ثابت است .

************

CMAIN.43.gifبرهان خلف :

فرض می کنیم CMAIN.44.gif دور داشته باشد بناباین یال e را که در دور واقع است حذف می کنیم . در اینصورت CMAIN.45.gif همبند است .اگر CMAIN.46.gifدور داشته باشد باز هم یالی را حذف می کنیم تا گراف CMAIN.47.gif بدون دور بدست آید .

CMAIN.48.gif

که تناقض است .

لینک به دیدگاه

سؤال 9) فرض کنید G گراف همبند باشد ، در هر یک از موارد زیر چه می توان گفت.

1) یالی که در هر درخت پوشای G ظاهر شود.

2) یالی که در هیچ درخت پوشای G ظاهر نشود.

************

در مورد اول چنین یالی یال برشی خواهد بود که باید مطمئناً در گراف فراگیر باشد چون در صورت حذف گراف ناهمبند خواهد شد.

در مورد دوم، چنین یالی وجود ندارد ، (برهان خلف) فرض می کنیم e چنین یالی باشد ، در این صورت دو حالت وجود دارد . اول اینکه e در هیچ دوری واقع نباشد لذا این یال یال برشی خواهد بود و امکان حذف آن وجود ندارد . دوم اینکه این یال در دوری واقع باشد . بنابر این با حذف یالی از دور به جزe میتوان درخت فراگیری تشکیل داد که شامل e باشد.بنابراین در هر صورت میتوان از e در تشکیل درخت فراگیر استفاده کرد .

لینک به دیدگاه

سؤال 10) نشان دهید که هر درخت حداکثر دو رأس مرکزی دارد.

************

جواب :با استقرا بر روی v ثابت می کنیم . برای درخت با یک رأس یک مرکز و برای درخت با دو رأس دو مرکز وجود دارد .

حال فرض می کنیم برای هر درخت T با کمتر یا مساوی k رأس حکم برقرار باشد . حال درخت CMAIN.50.gif را با k+1 رأس را در نظر می گیریم ، ثابت میکنیم که CMAIN.50.gif حداکثر یک یا دو مرکز دارد . برای این کار ابتدا تمام رأس های درجه یک گراف را حذف می کنیم . (چون هر درخت دارای حداقل دو رأس از درجه یک است ) درخت باقی مانده دارای حداکثر k-1 رأس است . که طبق فرض استقرا دارای حداکثر دو مرکز است .واضح است که گریز از مرکز هررأس فاصله آن از یک رأس درجه یک است . و نیز می دانیم که با اضافه کردن رئوس درجه یک ، به گریز از مرکز همه رئوس یک و فقط یک واحد افزوده می شود . بنابراین با اضافه کردن رئوس درجه یک به درخت k-1 رأسی مراکز درخت CMAIN.51.gif همان مراکز درخت CMAIN.50.gif میباشد.

لینک به دیدگاه

سؤال11) نشان دهید اگر G گرافی k-منتظم باشد L(G) گرافی 2k-2-منتظم خواهد بود.

************

چون هر یال در گراف G یک رأس در گراف L(G) است و هر یال به دو رأس از دو سر منتهی میشود، و همچنین چون درجه هر رأسG ، k است پس یال e از هر سر با k-1 یال دیگر در ارتباط است، بنابراین یال دلخواه e که در L(G) رأس e خواهد بود با (k-1+k-1)=2k-2 رأس دیگر در ارتباط است.

لینک به دیدگاه

سوال 12) : هر گراف مسطح ماکزیمال یک گراف مثلثی است .

************

برهان : (برهان خلف) فرض کنید گرافg مسطح ماکزیمال باشد اما مثلثی نباشد یعنی حداقل یک وجه آن دارای بیشتر از 3 یال باشد، که در این صورت میتوان با رسم یکی از اقطار این وجه گرافی مسطح بدست آورد که این با فرض مسطح ماکزیمال بودن g متناقض است.

لینک به دیدگاه

سؤال 13)اگر گراف مسطح ماکزیمال باشد در اینصورت

CMAIN.52.gifکه n تعداد رئوس و m تعداد یال های G است .

************

برهان : با توجه به اینکه هر گراف مسطح ماکزیمال ، مثلثی است . داریم :

CMAIN.53.gif

لینک به دیدگاه

سؤال14 ) ثابت کنید اگر گرافی ساده دارای دقیقاَ 2n+1 رأس باشد و نیز تعداد یال های G بیشتر از

Graph.54.gif باشد آنگاه :

Graph.55.gif

لینک به دیدگاه

سؤال 15) عبارتی برای تعداد یالهای

Graph.15.1.gif بر اساس درجات رئوس G بیابید.

************

با توجه به شکل مشاهده می شود به ازای هر رأس با درجه n تعداد

Graph.15.2.gifیال درGraph.15.1.gifخواهیم داشت .

حال تعداد کل یالها Graph.15.1.gif از فرمول زیر بدست می آید که در آن Graph.15.3.gifدرجه رأس iام است

Graph.15.4.gif

لینک به دیدگاه
×
×
  • اضافه کردن...