نظریه گراف و برخي سؤالات حل شده براي يادگيري بيشتر

[Borna66]

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

************
http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.1.gif




چون http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.2.gif عددی زوج است بنابراین داریم:http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.3.gif پس :http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.4.gif

[Borna66]

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



http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.5.gif
گذری که مسیر نیست.
http://com-edu.persiangig.com/Graph/IMAGE/image001.png

[Borna66]

سؤال 3) گراف G را دو بخشی گویند اگر و فقط اگر دارای دوری به طول فرد نباشد . عکس قضیه فوق را اثبات کنید . ************ اگر G همبند باشد، و دور فرد نداشته باشد، a را یک رأس دلخواه از گراف G در نظر میگیریم و قرار می دهیم :http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.6.gif وhttp://com-edu.persiangig.com/Graph/IMAGE/CMAIN.7.gif در این صورت http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.8.gif مجموعه http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.9.gif را افراز میکنند .ادعا می کنیم http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.10.gif مجموعه های مستقل هستند، اگر http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.11.gif در این صورت طبق تعریف

http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.12.gif ، مسیر های http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.13.gif به طول زوج وجود دارند که
http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.14.gif و http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.15.gif حال اگر http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.16.gif باشند آنگاه طول گشت بسته http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.17.gif فرد است و لذا دارای دوری به طول فرد می باشد که با فرض در تناقض است. بنابراین هیچکام از رئوس مجموعه http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.18.gifبا هم در ارتباط نیستند . همینطور ثابت می شود که اعضای مجموعه http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.19.gif نیز با همدیگر رابطه ندارند . در نتیجه گرافhttp://com-edu.persiangig.com/Graph/IMAGE/CMAIN.20.gif دوبخشی است.

[Borna66]

ثابت کنید اگر G یک گراف مسطح باشد و محیط آن 5 باشد در اینصورتhttp://com-edu.persiangig.com/Graph/IMAGE/CMAIN.22.gif
(توجه: منظور از محیط طول کوتاهترین دور G است .)
************
اثبات: مجموعه S را شامل همه زوج مرتب هایhttp://com-edu.persiangig.com/Graph/IMAGE/CMAIN.23.gif میگیریم . این بدین معناست که مثلاً داریم که http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.24.gif وجه اول است ، حال چون تعداد وجوه گراف http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.25.gif ، http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.26.gif تا است و هر وجه حداقل 5 یال دارد ، بنابراین مجموعه S حداقل شامل http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.27.gif عضو است.و http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.28.gif از طرفی چون داشتیم هر یال حداکثر متعلق به دو وجه است پس http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.29.gif است .بنابراین داریم : http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.30.gif و طبق فرمول اویلر داریم : http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.31.gif در نتیجه : http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.32.gif

[Borna66]

اگر کمترین وجه G را با http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.33.gif و بیشترین آنرا با http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.34.gif نمایش دهیم ، نشان دهید: http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.35.gif
************
میدانیم که http://com-edu.persiangig.com/Graph/IMAGE/Graph.1.gifاما از طرفی چونhttp://com-edu.persiangig.com/Graph/IMAGE/Graph.2.gifبزرگترین درجه رئوس گراف میباشد داریم:http://com-edu.persiangig.com/Graph/IMAGE/Graph.3.gif همینطور برایhttp://com-edu.persiangig.com/Graph/IMAGE/Graph.4.gif چونhttp://com-edu.persiangig.com/Graph/IMAGE/Graph.4.gif کوچکترین درجه رئوس گراف میباشد داریم :
http://com-edu.persiangig.com/Graph/IMAGE/Graph.5.gif
که از این دو تساوی داریم:
http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.35.gif

[Borna66]

اگر هرجفت از گزاره های زیر رخ دهد ثابت کنید سومی رخ خواهد داد.:
1) G همبند است . 2) G فاقد دور است. 3) http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.36.gif ************
http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.37.gif با توجه به تعریف درخت داریم که گراف همبند فاقد دور یک درخت است . حال ثابت می کنیم که http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.36.gif استقرا : با استقرا بر روی v ثابت می کنیم. http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.38.gif فرض می کنیم که حکم برای هر درخت با k رأس درست باشد . یعنی http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.39.gif حال درخت با k+1 رأس را در نظر گرفته و با توجه به اینکه هر درخت حداقل دو رأس از درجه یک دارد اگر از این درخت یک رأس از درجه یک و یال مربوط به آن را حذف کنیم ، درختی پدید می آید با k رأس و طبق فرض استقرا دارای k-1 یال . پس درخت k+1 رأسی دارای k یال است . بدین ترتیب حکم ثابت شد.
************
http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.40.gif برهان خلف : اگر گراف با مشخصات 2 و3 همبند نباشد ، بنابراین ناهمبند خواهد بود و دارای مؤلفه های همبندی که چون دارای دور نیست هر مؤلفه همبندی یک درخت خواهد بود . که برای هر مؤلفه داریم : http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.41.gif بنابراین : http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.42.gif که در آن n تعداد مؤلفه های همبندی است . و طبق فرض 3 داشتیم : http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.36.gif بنابراین داریم : n=1 در نتیجه G همبند است و بنابراین حکم ثابت است .
************
http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.43.gifبرهان خلف : فرض می کنیم http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.44.gif دور داشته باشد بناباین یال e را که در دور واقع است حذف می کنیم . در اینصورت http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.45.gif همبند است .اگر http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.46.gifدور داشته باشد باز هم یالی را حذف می کنیم تا گراف http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.47.gif بدون دور بدست آید .
http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.48.gif
که تناقض است .

[Borna66]

در گراف زیر به کمک الگوریتم فلوری یک مدار اویلری برست آورید.
http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.49.gif

[Borna66]

فرض کنید G گراف همبند باشد ، در هر یک از موارد زیر چه می توان گفت.
1) یالی که در هر درخت پوشای G ظاهر شود.
2) یالی که در هیچ درخت پوشای G ظاهر نشود.
************
در مورد اول چنین یالی یال برشی خواهد بود که باید مطمئناً در گراف فراگیر باشد چون در صورت حذف گراف ناهمبند خواهد شد.
در مورد دوم، چنین یالی وجود ندارد ، (برهان خلف) فرض می کنیم e چنین یالی باشد ، در این صورت دو حالت وجود دارد . اول اینکه e در هیچ دوری واقع نباشد لذا این یال یال برشی خواهد بود و امکان حذف آن وجود ندارد . دوم اینکه این یال در دوری واقع باشد . بنابر این با حذف یالی از دور به جزe میتوان درخت فراگیری تشکیل داد که شامل e باشد.بنابراین در هر صورت میتوان از e در تشکیل درخت فراگیر استفاده کرد .

[Borna66]

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

[Borna66]

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

[Borna66]

هر گراف مسطح ماکزیمال یک گراف مثلثی است .
************
برهان : (برهان خلف) فرض کنید گرافG مسطح ماکزیمال باشد اما مثلثی نباشد یعنی حداقل یک وجه آن دارای بیشتر از 3 یال باشد، که در این صورت میتوان با رسم یکی از اقطار این وجه گرافی مسطح بدست آورد که این با فرض مسطح ماکزیمال بودن G متناقض است.
(http://commenting.blogfa.com/?blogid=pn-un-birjand&postid=30&timezone=12642)

[Borna66]

اگر گراف مسطح ماکزیمال باشد در اینصورت http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.52.gifکه n تعداد رئوس و m تعداد یال های G است .
************
برهان : با توجه به اینکه هر گراف مسطح ماکزیمال ، مثلثی است . داریم : http://com-edu.persiangig.com/Graph/IMAGE/CMAIN.53.gif

[Borna66]

عبارتی برای تعداد یالهای http://com-edu.persiangig.com/Graph/IMAGE/Graph.15.1.gif بر اساس درجات رئوس G بیابید.
************
با توجه به شکل مشاهده می شود به ازای هر رأس با درجه n تعداد http://com-edu.persiangig.com/Graph/IMAGE/Graph.15.2.gifیال درhttp://com-edu.persiangig.com/Graph/IMAGE/Graph.15.1.gifخواهیم داشت .
حال تعداد کل یالها http://com-edu.persiangig.com/Graph/IMAGE/Graph.15.1.gif از فرمول زیر بدست می آید که در آن http://com-edu.persiangig.com/Graph/IMAGE/Graph.15.3.gifدرجه رأس iام است
http://com-edu.persiangig.com/Graph/IMAGE/Graph.15.4.gif

[ehsan_elf]

سلاام دوستان. شبتون بخیر

چندتا سوال داشتم نمیدونستم باید کجا مطرحشون کنم همینجا میپرسم

1: الگوریتمی بنویسید که یک گراف راگرفته مشخص کند که راس برشی دارد یا خیر.

2: حداکثر تعداد یال های یک گراف ناهمبند چقدر است؟

3: فرمولی که تعداد درخت های فراگیر یک گراف رامحاسبه کند.

ممنون میشم کمکم کنید. البته فقط تا فردا وقت دارم....تشکر:72: