گراف

[spow 44,195]

سلام

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

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

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

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

 

چون

عددی زوج است بنابراین داریم:پس :

[spow 44,195]

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

 

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

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

 

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

[spow 44,195]

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

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

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

اگر G همبند باشد، و دور فرد نداشته باشد، a را یک رأس دلخواه از گراف G در نظر میگیریم و قرار می دهیم :ودر این صورت مجموعه را افراز میکنند .ادعا می کنیم مجموعه های مستقل هستند، اگر در این صورت طبق تعریف

، مسیر های به طول زوج وجود دارند که

و

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

[spow 44,195]

سؤال 4) فرض کنید که G یک گراف r-منتظم باشد ، رابطه ای برای

پیدا کنید.

[spow 44,195]

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

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

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

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

میگیریم . این بدین معناست که مثلاً داریم که وجه اول است ، حال چون تعداد وجوه گراف ، تا است و هر وجه حداقل 5 یال دارد ، بنابراین مجموعه S حداقل شامل عضو است.و از طرفی چون داشتیم هر یال حداکثر متعلق به دو وجه است پس است .بنابراین داریم : و طبق فرمول اویلر داریم : در نتیجه :

[spow 44,195]

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

و بیشترین آنرا با نمایش دهیم ، نشان دهید:

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

میدانیم که

اما از طرفی چونبزرگترین درجه رئوس گراف میباشد داریم:

 

 

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

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

[spow 44,195]

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

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

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

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

 

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

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

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

برهان خلف :

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

 

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

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

برهان خلف :

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

که تناقض است .

[spow 44,195]

سؤال 8)در گراف زیر به کمک الگوریتم فلوری یک مدار اویلری برست آورید.

[spow 44,195]

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

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

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

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

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

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

[spow 44,195]

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

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

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

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

[spow 44,195]

سؤال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 رأس دیگر در ارتباط است.

[spow 44,195]

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

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

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

[spow 44,195]

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

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

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

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

[spow 44,195]

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

باشد آنگاه :

[spow 44,195]

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

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

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

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

یال درخواهیم داشت .

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