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

[Borna66]

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

************
http://pnu-club.com/imported/2012/03/57.gif




چون http://pnu-club.com/imported/2012/03/58.gif عددی زوج است بنابراین داریم:http://pnu-club.com/imported/2012/03/59.gif پس :http://pnu-club.com/imported/2012/03/60.gif

[Borna66]

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



http://pnu-club.com/imported/2012/03/61.gif
گذری که مسیر نیست.
http://pnu-club.com/imported/2012/03/2.png

[Borna66]

سؤال 3) گراف G را دو بخشی گویند اگر و فقط اگر دارای دوری به طول فرد نباشد . عکس قضیه فوق را اثبات کنید . ************ اگر G همبند باشد، و دور فرد نداشته باشد، a را یک رأس دلخواه از گراف G در نظر میگیریم و قرار می دهیم :http://pnu-club.com/imported/2012/03/62.gif وhttp://pnu-club.com/imported/2012/03/63.gif در این صورت http://pnu-club.com/imported/2012/03/64.gif مجموعه http://pnu-club.com/imported/2012/03/65.gif را افراز میکنند .ادعا می کنیم http://pnu-club.com/imported/2012/03/66.gif مجموعه های مستقل هستند، اگر http://pnu-club.com/imported/2012/03/67.gif در این صورت طبق تعریف

http://pnu-club.com/imported/2012/03/68.gif ، مسیر های http://pnu-club.com/imported/2012/03/69.gif به طول زوج وجود دارند که
http://pnu-club.com/imported/2012/03/70.gif و http://pnu-club.com/imported/2012/03/71.gif حال اگر http://pnu-club.com/imported/2012/03/72.gif باشند آنگاه طول گشت بسته http://pnu-club.com/imported/2012/03/73.gif فرد است و لذا دارای دوری به طول فرد می باشد که با فرض در تناقض است. بنابراین هیچکام از رئوس مجموعه http://pnu-club.com/imported/2012/03/74.gifبا هم در ارتباط نیستند . همینطور ثابت می شود که اعضای مجموعه http://pnu-club.com/imported/2012/03/75.gif نیز با همدیگر رابطه ندارند . در نتیجه گرافhttp://pnu-club.com/imported/2012/03/76.gif دوبخشی است.

[Borna66]

ثابت کنید اگر G یک گراف مسطح باشد و محیط آن 5 باشد در اینصورتhttp://pnu-club.com/imported/2012/03/77.gif
(توجه: منظور از محیط طول کوتاهترین دور G است .)
************
اثبات: مجموعه S را شامل همه زوج مرتب هایhttp://pnu-club.com/imported/2012/03/78.gif میگیریم . این بدین معناست که مثلاً داریم که http://pnu-club.com/imported/2012/03/79.gif وجه اول است ، حال چون تعداد وجوه گراف http://pnu-club.com/imported/2012/03/80.gif ، http://pnu-club.com/imported/2012/03/81.gif تا است و هر وجه حداقل 5 یال دارد ، بنابراین مجموعه S حداقل شامل http://pnu-club.com/imported/2012/03/82.gif عضو است.و http://pnu-club.com/imported/2012/03/83.gif از طرفی چون داشتیم هر یال حداکثر متعلق به دو وجه است پس http://pnu-club.com/imported/2012/03/84.gif است .بنابراین داریم : http://pnu-club.com/imported/2012/03/85.gif و طبق فرمول اویلر داریم : http://pnu-club.com/imported/2012/03/86.gif در نتیجه : http://pnu-club.com/imported/2012/03/87.gif

[Borna66]

اگر کمترین وجه G را با http://pnu-club.com/imported/2012/03/88.gif و بیشترین آنرا با http://pnu-club.com/imported/2012/03/89.gif نمایش دهیم ، نشان دهید: http://pnu-club.com/imported/2012/03/90.gif
************
میدانیم که http://pnu-club.com/imported/2012/03/91.gifاما از طرفی چونhttp://pnu-club.com/imported/2012/03/92.gifبزرگترین درجه رئوس گراف میباشد داریم:http://pnu-club.com/imported/2012/03/93.gif همینطور برایhttp://pnu-club.com/imported/2012/03/94.gif چونhttp://pnu-club.com/imported/2012/03/94.gif کوچکترین درجه رئوس گراف میباشد داریم :
http://pnu-club.com/imported/2012/03/95.gif
که از این دو تساوی داریم:
http://pnu-club.com/imported/2012/03/90.gif

[Borna66]

اگر هرجفت از گزاره های زیر رخ دهد ثابت کنید سومی رخ خواهد داد.:
1) G همبند است . 2) G فاقد دور است. 3) http://pnu-club.com/imported/2012/03/96.gif ************
http://pnu-club.com/imported/2012/03/97.gif با توجه به تعریف درخت داریم که گراف همبند فاقد دور یک درخت است . حال ثابت می کنیم که http://pnu-club.com/imported/2012/03/96.gif استقرا : با استقرا بر روی v ثابت می کنیم. http://pnu-club.com/imported/2012/03/98.gif فرض می کنیم که حکم برای هر درخت با k رأس درست باشد . یعنی http://pnu-club.com/imported/2012/03/99.gif حال درخت با k+1 رأس را در نظر گرفته و با توجه به اینکه هر درخت حداقل دو رأس از درجه یک دارد اگر از این درخت یک رأس از درجه یک و یال مربوط به آن را حذف کنیم ، درختی پدید می آید با k رأس و طبق فرض استقرا دارای k-1 یال . پس درخت k+1 رأسی دارای k یال است . بدین ترتیب حکم ثابت شد.
************
http://pnu-club.com/imported/2012/03/100.gif برهان خلف : اگر گراف با مشخصات 2 و3 همبند نباشد ، بنابراین ناهمبند خواهد بود و دارای مؤلفه های همبندی که چون دارای دور نیست هر مؤلفه همبندی یک درخت خواهد بود . که برای هر مؤلفه داریم : http://pnu-club.com/imported/2012/03/101.gif بنابراین : http://pnu-club.com/imported/2012/03/102.gif که در آن n تعداد مؤلفه های همبندی است . و طبق فرض 3 داشتیم : http://pnu-club.com/imported/2012/03/96.gif بنابراین داریم : n=1 در نتیجه G همبند است و بنابراین حکم ثابت است .
************
http://pnu-club.com/imported/2012/03/103.gifبرهان خلف : فرض می کنیم http://pnu-club.com/imported/2012/03/104.gif دور داشته باشد بناباین یال e را که در دور واقع است حذف می کنیم . در اینصورت http://pnu-club.com/imported/2012/03/105.gif همبند است .اگر http://pnu-club.com/imported/2012/03/106.gifدور داشته باشد باز هم یالی را حذف می کنیم تا گراف http://pnu-club.com/imported/2012/03/107.gif بدون دور بدست آید .
http://pnu-club.com/imported/2012/03/108.gif
که تناقض است .

[Borna66]

در گراف زیر به کمک الگوریتم فلوری یک مدار اویلری برست آورید.
http://pnu-club.com/imported/2012/03/109.gif

[Borna66]

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

[Borna66]

نشان دهید که هر درخت حداکثر دو رأس مرکزی دارد.
************
جواب :با استقرا بر روی v ثابت می کنیم . برای درخت با یک رأس یک مرکز و برای درخت با دو رأس دو مرکز وجود دارد .
حال فرض می کنیم برای هر درخت T با کمتر یا مساوی k رأس حکم برقرار باشد . حال درخت http://pnu-club.com/imported/2012/03/110.gif را با k+1 رأس را در نظر می گیریم ، ثابت میکنیم که http://pnu-club.com/imported/2012/03/110.gif حداکثر یک یا دو مرکز دارد . برای این کار ابتدا تمام رأس های درجه یک گراف را حذف می کنیم . (چون هر درخت دارای حداقل دو رأس از درجه یک است ) درخت باقی مانده دارای حداکثر k-1 رأس است . که طبق فرض استقرا دارای حداکثر دو مرکز است .واضح است که گریز از مرکز هررأس فاصله آن از یک رأس درجه یک است . و نیز می دانیم که با اضافه کردن رئوس درجه یک ، به گریز از مرکز همه رئوس یک و فقط یک واحد افزوده می شود . بنابراین با اضافه کردن رئوس درجه یک به درخت k-1 رأسی مراکز درخت http://pnu-club.com/imported/2012/03/111.gif همان مراکز درخت http://pnu-club.com/imported/2012/03/110.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://pnu-club.com/imported/2012/03/112.gifکه n تعداد رئوس و m تعداد یال های G است .
************
برهان : با توجه به اینکه هر گراف مسطح ماکزیمال ، مثلثی است . داریم : http://pnu-club.com/imported/2012/03/113.gif

[Borna66]

عبارتی برای تعداد یالهای http://pnu-club.com/imported/2012/03/114.gif بر اساس درجات رئوس G بیابید.
************
با توجه به شکل مشاهده می شود به ازای هر رأس با درجه n تعداد http://pnu-club.com/imported/2012/03/115.gifیال درhttp://pnu-club.com/imported/2012/03/114.gifخواهیم داشت .
حال تعداد کل یالها http://pnu-club.com/imported/2012/03/114.gif از فرمول زیر بدست می آید که در آن http://pnu-club.com/imported/2012/03/116.gifدرجه رأس iام است
http://pnu-club.com/imported/2012/03/117.gif

[ehsan_elf]

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

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

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

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

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

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

[Borna66]

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

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

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

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

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

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

با سلام

متاسفانه در اين زمينه اطلاعي ندارم و كمكي از دست ما بر نمي ايد... شرمنده

روزگار خوش