تعداد ۶-دورها در گراف پترسن را بیابید.

Question

ثابت کنید گراف پترسن دقیقا دارای ۱۰ تا ۶-دور است. راهنمایی: یک نگاشت دوسویی بین ۶_دورهای گراف پترسن و ۶-دورهای گراف $K_{1,3}$ برقرار کنید.

Comments

@Rad1999 احتمالا از روی کتابی متن پرسش را نوشتید، درست است؟ اگر بلی می‌توانید نام کتاب به همراه نام نویسنده و مشخصات تمرین (شمارهٔ تمرین و فصل) را در مرجع قرار دهید. بعلاوه خودتان برای این پرسش چه تلاشی کرده‌اید؟ رویِ راهنمایی داده‌شده فکر کرده‌اید؟

---

@amirhoseonاز منبع اطلاعات لازم را ندارم.ولی به احتمال زیاد از کتاب وست است...متاسفانه هیچ ایده ای برای پاسخ سوال ندارم

---

@Rad1999 گراف Petersen را رسم کرده‌اید و حداقل یکی از ۶-دورهایش را نگاه کنید؟

---

@amir hoseim بله دقیقا  ده۶-دورش رو مشاهده کردم.ولی نمیدونم چطور اثباتش کنم

---

@Rad1999 اگر نام کاربری را با املایی متفاوت بنویسید آنگاه هیچ اطلاع‌رسانی به کاربر خطاب‌شده ارسال نمی‌شود. شناسهٔ کاربری من AmirHosein است نه دو نسخهٔ دیگری که در دو دیدگاه‌تان آورده‌اید.
ابتدا اینکه در متن پرسش‌تان احتمالا اشتباه نوشتاری (تایپی) دارید، $K_{3,3}$ باید باشد نه $K_{1,3}$. و اما کاری که باید بکنید. یکی از این ۶-دورها را به دلخواه بردارید چیزی شبیه به $K_{3,3}$ نمی‌بینید؟

Answer 1

شکل گراف پترسن را در نظر داشته باشید.

پنج گره و یال درون داریم به شکل ستاره که تحت عنوان حلقهٔ درونی از آن یاد خواهم کرد. پنج گره و یال بیرون داریم که با لفظ حلقهٔ بیرونی از آن یاد خواهم کرد. پنج یال میانجی نیز داریم که نه در حلقهٔ درونی و نه در حلقهٔ بیرونی هستند. تعداد ۶-دورها را در چند حالت مجزا می‌شماریم که در نتیجه تعداد کل ۶-دورهای گرافمان برابر با جمع تعداد ۶-دورها در تک‌تک این حالت‌ها خواهد شد.

1. آیا یک ۶-دور شامل هر پنج یال بیرونی وجود دارد؟ خیر، زیرا یک ۵-دور می‌سازد و افزودن یک یال دیگر یا گراف ناهمبند می‌سازد یا یک ۵-دور و یک یال زائد.

2. آیا یک ۶-دور شامل ۴ یال از یال‌های بیرونی وجود دارد؟ ۵ حالت ۴ تا یال از حلقهٔ بیرونی می‌توان انتخاب کرد که بنا به تقارن (یا دقیق‌تر با یک خودریختی) با هم یکسان هستند. پس یکی از این ۵ حالت را برمی‌داریم. یال‌های غیر از شمال شرقی. روشن است که هیچ ۲ یالی نمی‌توان یافت که به این مسیر افزود تا یک دور شود و به طبع ۶-دوری نخواهیم داشت.

3. آیا یک ۶-دور شامل ۳ یال از یال‌های بیرونی وجود دارد؟ به دو روش ۳ تا یال می‌توان انتخاب کرد، یا پشت‌سرهم (یک مسیر) یا یکی ناهمسایه با دو تای دیگر که همسایه (مجاور) هم هستند.

   1. حالت مسیر به درازای ۳ از حلقهٔ بیرونی: به ۵ حالت که همگی با هم نتایج یکسانی را برای ما به دنبال خواهند داشت هست. حالت سه یال سمال غربی تا جنوب را در نظر بگیرید. دقیقا فقط یک حالت یکتا وجود دارد که با افزودن ۳ یال دیگر یک ۶-دور شود. پس این مرحله به ما ۵ تا ۶-دور می‌دهد.

   2. یک یال و سپس دو یالی که همسایه‌اش نیستند: این کار هم به ۵ حالت با نتایج یکسان میسر است. یال‌های شمال غربی، جنوبی و جنوب شرقی را در نظر بگیرید. هیچ ۳ یالی نمی‌توان یافت که با افزودنش به ۳ یال انتخاب شده یک دور بدهد.

4. آیا یک ۶-دور شامل تنها ۲ یال از حلقهٔ بیرونی وجود دارد؟ دو حالت داریم یا مسیر به درازای ۲ یا دو یال ناهمسایه.

   1. حالت مسیر به درازای ۲: ۵ حالت یکسان. یالهای جنوب غربی و جنوبی را در نظر بگیرید. هیچ ۴ یالی نیست که با آنها دور تشکیل بدهند.

   2. دو یال ناهمسایه: یال شمال غربی و یال جنوبی را در نظر بگیرید. هیچ ۴ یالی نیست که با آنها تشکیل دور بدهند.

5. آیا ۶-دوری هست که تنها یک یال از حلقهٔ درونی را داشته‌باشد؟ ۵ حالت یکسان. یال جنوبی را در نظر بگیرید. تنها یک ۶-دور یکتا برایش شامل آن وجود دارد. پس این حالت به ما ۵ تا ۶-دور می‌دهد.

6. آیا ۶-دوری هست که هیچ یالی از حلقهٔ بیرونی نداشته‌باشد؟ خیر. گراف‌مان منهای حلقهٔ بیرونی یک دور به درازای ۵ با ۵ تا برگ آویزان است که هیچ دور دیگری ندارد که بخواهد درازای ۶ داشته باشد یا خیر.

حالت دیگری وجود ندارد، یک ۶-دور اشتراکش با حلقهٔ بیرونی فقط می‌تواند یکی از عددهای ۵، ۴، ۳، ۲، ۱، ۰ باشد که در ۶ حالت بالا بررسی شدند. چون مجزا از هم نیز هستند پس تعداد کل ۶-دورها برابر است با

$$0+0+5+0+5+0=10$$