spow 44198 ارسال شده در 11 اردیبهشت، 2011 سلام سوال وجواب هایی دررابطه با موضوع گراف ها امیدوارم به درد دوستان بخوره سؤال 1 : بنا بر قضیه بالا نشان دهید تعداد رئوس فرد یک گراف زوج است. ************ چون عددی زوج است بنابراین داریم:پس :
spow 44198 مالک ارسال شده در 11 اردیبهشت، 2011 سؤال 2) می توان نشان داد که هر مسیر حتما گذر است ولی عکس آن برقرار نیست . برای عکس مطلب فوق یک مثال بیاورید . ************ گذری که مسیر نیست.
spow 44198 مالک ارسال شده در 11 اردیبهشت، 2011 سؤال 3) گراف G را دو بخشی گویند اگر و فقط اگر دارای دوری به طول فرد نباشد . عکس قضیه فوق را اثبات کنید . ************ اگر G همبند باشد، و دور فرد نداشته باشد، a را یک رأس دلخواه از گراف G در نظر میگیریم و قرار می دهیم :ودر این صورت مجموعه را افراز میکنند .ادعا می کنیم مجموعه های مستقل هستند، اگر در این صورت طبق تعریف ، مسیر های به طول زوج وجود دارند که و حال اگر باشند آنگاه طول گشت بسته فرد است و لذا دارای دوری به طول فرد می باشد که با فرض در تناقض است. بنابراین هیچکام از رئوس مجموعه با هم در ارتباط نیستند . همینطور ثابت می شود که اعضای مجموعه نیز با همدیگر رابطه ندارند . در نتیجه گراف دوبخشی است
spow 44198 مالک ارسال شده در 11 اردیبهشت، 2011 سؤال 4) فرض کنید که G یک گراف r-منتظم باشد ، رابطه ای برای پیدا کنید.
spow 44198 مالک ارسال شده در 11 اردیبهشت، 2011 سوال 5) ثابت کنید اگر G یک گراف مسطح باشد و محیط آن 5 باشد در اینصورت (توجه: منظور از محیط طول کوتاهترین دور G است .) ************ اثبات: مجموعه S را شامل همه زوج مرتب های میگیریم . این بدین معناست که مثلاً داریم که وجه اول است ، حال چون تعداد وجوه گراف ، تا است و هر وجه حداقل 5 یال دارد ، بنابراین مجموعه S حداقل شامل عضو است.و از طرفی چون داشتیم هر یال حداکثر متعلق به دو وجه است پس است .بنابراین داریم : و طبق فرمول اویلر داریم : در نتیجه :
spow 44198 مالک ارسال شده در 11 اردیبهشت، 2011 سؤال 6) اگر کمترین وجه G را با و بیشترین آنرا با نمایش دهیم ، نشان دهید: ************ میدانیم که اما از طرفی چونبزرگترین درجه رئوس گراف میباشد داریم: همینطور برای چون کوچکترین درجه رئوس گراف میباشد داریم : که از این دو تساوی داریم:
spow 44198 مالک ارسال شده در 11 اردیبهشت، 2011 سؤال 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 44198 مالک ارسال شده در 11 اردیبهشت، 2011 سؤال 8)در گراف زیر به کمک الگوریتم فلوری یک مدار اویلری برست آورید.
spow 44198 مالک ارسال شده در 11 اردیبهشت، 2011 سؤال 9) فرض کنید G گراف همبند باشد ، در هر یک از موارد زیر چه می توان گفت. 1) یالی که در هر درخت پوشای G ظاهر شود. 2) یالی که در هیچ درخت پوشای G ظاهر نشود. ************ در مورد اول چنین یالی یال برشی خواهد بود که باید مطمئناً در گراف فراگیر باشد چون در صورت حذف گراف ناهمبند خواهد شد. در مورد دوم، چنین یالی وجود ندارد ، (برهان خلف) فرض می کنیم e چنین یالی باشد ، در این صورت دو حالت وجود دارد . اول اینکه e در هیچ دوری واقع نباشد لذا این یال یال برشی خواهد بود و امکان حذف آن وجود ندارد . دوم اینکه این یال در دوری واقع باشد . بنابر این با حذف یالی از دور به جزe میتوان درخت فراگیری تشکیل داد که شامل e باشد.بنابراین در هر صورت میتوان از e در تشکیل درخت فراگیر استفاده کرد .
spow 44198 مالک ارسال شده در 11 اردیبهشت، 2011 سؤال 10) نشان دهید که هر درخت حداکثر دو رأس مرکزی دارد. ************ جواب :با استقرا بر روی v ثابت می کنیم . برای درخت با یک رأس یک مرکز و برای درخت با دو رأس دو مرکز وجود دارد . حال فرض می کنیم برای هر درخت T با کمتر یا مساوی k رأس حکم برقرار باشد . حال درخت را با k+1 رأس را در نظر می گیریم ، ثابت میکنیم که حداکثر یک یا دو مرکز دارد . برای این کار ابتدا تمام رأس های درجه یک گراف را حذف می کنیم . (چون هر درخت دارای حداقل دو رأس از درجه یک است ) درخت باقی مانده دارای حداکثر k-1 رأس است . که طبق فرض استقرا دارای حداکثر دو مرکز است .واضح است که گریز از مرکز هررأس فاصله آن از یک رأس درجه یک است . و نیز می دانیم که با اضافه کردن رئوس درجه یک ، به گریز از مرکز همه رئوس یک و فقط یک واحد افزوده می شود . بنابراین با اضافه کردن رئوس درجه یک به درخت k-1 رأسی مراکز درخت همان مراکز درخت میباشد.
spow 44198 مالک ارسال شده در 11 اردیبهشت، 2011 سؤال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 44198 مالک ارسال شده در 11 اردیبهشت، 2011 سوال 12) : هر گراف مسطح ماکزیمال یک گراف مثلثی است . ************ برهان : (برهان خلف) فرض کنید گرافg مسطح ماکزیمال باشد اما مثلثی نباشد یعنی حداقل یک وجه آن دارای بیشتر از 3 یال باشد، که در این صورت میتوان با رسم یکی از اقطار این وجه گرافی مسطح بدست آورد که این با فرض مسطح ماکزیمال بودن g متناقض است.
spow 44198 مالک ارسال شده در 11 اردیبهشت، 2011 سؤال 13)اگر گراف مسطح ماکزیمال باشد در اینصورت که n تعداد رئوس و m تعداد یال های G است . ************ برهان : با توجه به اینکه هر گراف مسطح ماکزیمال ، مثلثی است . داریم :
spow 44198 مالک ارسال شده در 11 اردیبهشت، 2011 سؤال14 ) ثابت کنید اگر گرافی ساده دارای دقیقاَ 2n+1 رأس باشد و نیز تعداد یال های G بیشتر از باشد آنگاه :
spow 44198 مالک ارسال شده در 11 اردیبهشت، 2011 سؤال 15) عبارتی برای تعداد یالهای بر اساس درجات رئوس G بیابید. ************ با توجه به شکل مشاهده می شود به ازای هر رأس با درجه n تعداد یال درخواهیم داشت . حال تعداد کل یالها از فرمول زیر بدست می آید که در آن درجه رأس iام است
ارسال های توصیه شده