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

[Borna66]

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

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

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

[Borna66]

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




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

[Borna66]

سؤال 3) گراف G را دو بخشی گویند اگر و فقط اگر دارای دوری به طول فرد نباشد . عکس قضیه فوق را اثبات کنید . ************

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

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

و

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

[Borna66]

ثابت کنید اگر G یک گراف مسطح باشد و محیط آن 5 باشد در اینصورت
(توجه: منظور از محیط طول کوتاهترین دور G است .)

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

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

[Borna66]

اگر کمترین وجه G را با و بیشترین آنرا با نمایش دهیم ، نشان دهید:

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

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

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

[Borna66]

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

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

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

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

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

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

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

که تناقض است .

[Borna66]

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

[Borna66]

فرض کنید G گراف همبند باشد ، در هر یک از موارد زیر چه می توان گفت.
1) یالی که در هر درخت پوشای G ظاهر شود.
2) یالی که در هیچ درخت پوشای G ظاهر نشود.

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

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

[Borna66]

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

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

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

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