کد: 38874

پرسش

باعرض سلام.
لطفا به سوال زیر پاسخ دهید.
باتشكر.
آیا در گراف از مرتبه P می توان دوری به طول بزرگتر از P یافت؟

پاسخ

سلام،با عرض پوزش از تاخیری كه پیش آمد،سوالات شما حد اكثر یك یا دو روز بعد جواب داده می شود.پس سوالات دیگری كه دارید را مطرح كنید.
در گراف با مرتبه p فرض كنید دوری با طول مثلا p+1 وجود دارد.هردور در گراف را می توان با دنباله ای از رئوس متوالی نشان داد.مثلا یك دور با طول 3 بین سه راس را می توان با p0 p1 p2 p0 نشان داد.در این دور با طول p+1 قاعدتا باید p+1 راس متمایز باشند اما در دنباله رئوس متناظر با دور بر اساس اصل لانه كبوتری راس تكراری موجود خواهد بود كه خلاف تعریف دور ساده در یك گراف است.پس دوری با طول بیش از p وجود تدارد.
سلام،با عرض پوزش از تاخیری كه پیش آمد،سوالات شما حد اكثر یك یا دو روز بعد جواب داده می شود.پس سوالات دیگری كه دارید را مطرح كنید.
در گراف با مرتبه p فرض كنید دوری با طول مثلا p+1 وجود دارد.هردور در گراف را می توان با دنباله ای از رئوس متوالی نشان داد.مثلا یك دور با طول 3 بین سه راس را می توان با p0 p1 p2 p0 نشان داد.در این دور با طول p+1 قاعدتا باید p+1 راس متمایز باشند اما در دنباله رئوس متناظر با دور بر اساس اصل لانه كبوتری راس تكراری موجود خواهد بود كه خلاف تعریف دور ساده در یك گراف است.پس دوری با طول بیش از p وجود تدارد.

مشاور : ۰ بهبودي | پرسش : يکشنبه 9/9/1382 | پاسخ : شنبه 15/9/1382 | پیش دانشگاهی | | 0 سال | رياضي | تعداد مشاهده: 16 بار

تگ ها :

UserName