|
در مورد كدام‌يك از موضوعات مطرح شده مايل به كسب اطلاعات بيشتر هستيد؟
|
ارائه نظر |
|
| | گراف‌هاي چندگانه (مسابقه‌ي شماره‌ي 54) ويژه‌ي ايام‌الله دهه‌ي فجر |
| | گراف‌هاي چندگانه (مسابقه‌ي شماره‌ي 54) ويژه‌ي ايام‌الله دهه‌ي فجرمسابقه كامپيوتر | | | |  | | قضيه‌ي اولري
| آن‌چه با عنوان «چكيده» در اول مسابقه‌ها و زنگ تفريح‌ها مشاهده مي‌كنيد صرفاً مخصوص معلمان، مربيان، كارشناسان محترم آموزشي و ساير علاقه‌مندان است.
اهداف آموزشي
 اهداف آموزشي در حوزه‌ي شناختي – دانش
- «دانش امور جزوي» > «دانش اصطلاح‌ها»
- «دانش امور جزوي» > «دانش واقعيت‌هاي مشخص»
- «دانش راه‌ها و وسايل برخورد با امور جزوي» > «دانش روش‌ها و روش‌شناسي»
- «دانش امور كلي و مسائل انتزاعي يك رشته» > «دانش اصل‌ها و تعميم‌ها»
اهداف آموزشي در حوزه‌ي شناختي - توانايي‌ها و مهارت‌هاي ذهني
- « فهميدن» > «ترجمه» > «تفسير»
- « فهميدن» > «ترجمه» > «درون‌يابي»
- « فهميدن» > «ترجمه» > «كاربستن»
- « فهميدن» > «ترجمه» > «تحليل» > «تحليل روابط»
- « فهميدن» > «ترجمه» > «تحليل» > «توليد يك نقشه يا مجموعه اقدام‌هاي پيشنهادي»
- « فهميدن» > «ترجمه» > «تركيب» > «استنتاج مجموعه‌اي از روابط انتزاعي»
نتايج مورد نظر
- آشنايي با قضيه‌ي اولر در مورد گراف‌هاي چندگانه
- شناخت روش اثبات قضايا در مورد گراف‌ها
محتواي آموزشي
- نظريه‌ي گراف‌ها |
در نظريه‌ي گراف‌ها، مسيري از يك گراف كه در آن مسير از هر «يال» تنها يك‌بار بگذرد «مسير اولري» ناميده مي‌شود.
گرافي «اولري» است كه داراي «مسير اولري» باشد.
هم‌چنين مي‌دانيم «مدار اولري» مداري است كه كه در آن يك «مسير اولري» از يك نقطه آغاز و به همان نقطه ختم مي‌شود.
گرافي «نيمه‌اولري» است كه «مسير اولري» وجود داشته باشد ولي يك «مدار اولري» نباشد.
ثابت كنيد:
| - شرط لازم و كافي براي اين‌كه يك گراف چندگانه‌ي همبند  و  «اولري» باشد آن است كه هر رأس داراي مرتبه‌ي «زوج» باشد.
| | - شرط لازم و كافي براي آن‌كه يك گراف چندگانه‌ي همبند «نيمه اولري» باشد آن است كه دقيقاً داراي مرتبه‌ي «فرد» باشد. |
|
| |
| فرستنده : |
|
علیرضا شفائی |
 |
 |
1386/11/27 |
| | | | | مـتـن : |
سلام
الف) لازم است زیرا: وقتی از راس اول شروع میکنیم به هر راسی وارد میشویم یک بار هم از آن خارج میشویم و همچنین در پایان به راس اول بر میگردیم. وقتی به هر راس در ازای هر ورود یک خروج خواهیم داشت پس درجه راسهای میانی زوج است. در پایان به راس ابتدا بر میگردیم. پس راس درجه اول نیز باید زوج باشد. بنابراین باید تمام درجه ها زوج باشد.
کافی است . اثبات:
لم: هر گراف با درجه راس حداقل 2 یک دور داره!.
اثبات:طولانی ترین مسیر را در نظر میگیریم. راس ابتدای مسیر را در نظر بگیرید. مسیر طولانی ما باید از حداقل یک همسایه دیگه اش عبور کرده باشه. چون درجه حداقل 2 است و اگر هم عبور نکرده باشه با فرض اولیه مون یعنی انتخاب طولانی ترین مسیر در تناقضه چون در این حالت میتوان با شروع از همسایه اون راس مسیر طولانی تری را به وجود آورد.
پس میتوان دوری داشت. به این صورت که از راس مورد نظر حرکت میکنیم. زمانی که به راس همسایه اش رسیدیم به همان راس برمیگردیم.اینطوری یک دور زده ایم.
استقرا میخوام بزنم تریپ قوی! به روی تعداد یالها.
زمانی که e=0 باشد طبق فرض مسئله برای حفظ شرط همبندی باید یک راس داشته باشیم که حکم مسئله را ثابت میکنید
فرض میکنیم برای تمام e های کوچکتر از n بر قرار باشه.
میریم سره خوده n. توی این گراف طبق لم مون یک دور داریم. چون درجه هر راس زوجه و درجه هیچ راسی هم 0 نیست .(چون همبنده) پس حداقل درجه 2 است پس طبق لم یک دور داریم.
میاییم این دور را جدا میکنیم. گراف باقی مونده تعدادی مولفه است که درجه ی تمام روس آن نیز زوجه. چون با حذف دور، از درجه هر راس زوج تا حذف میشه. طبق فرض استقرامون تمام این مولفه های کوچیک شرط مسئله را بر قرار میکنند. حالا میاییم و اون دوری که بر داشته بودیم را میزاریم سر جاش.
از یکی از مولفه ها شروع به حرکت میکنیم به این صورت که در دور اویلری گراف کوچک تر حرکت میکنیم. زمانی که به راسی رسیدیم که در دور شرکت داشت داخل اون میشیم. در دور به حرکت میپردازیم زمانی که به راسی رسیدیم که در یک مولفه دیگه نیز حضور داشته. وارد آن میشویم سپس دور اویلری اون را ادامه میدیم و .... زمانی که دور مون تموم شد به راس اولیه بازگشتیم و مسیری که باید ادامه میدادیم را ادامه میدهیم تا تمام گراف را طی کنیم.
در اصل همانند تابع بازگشتی عمل میکنه و در انتها به راس ابتدایی میرسیم.
تموم شد
در قسمت ب فکر کنم که باید دقیقا دو راس با درجه فرد داشته باشیم.
البته اگر تعریف نیمه اویلری درست یادم باشه.انگار در این حالت نباید گذر بسته باشه.
برای اثباتش هم کافیه که یالی بین این دور راس اضافه کنیم
حالا درجه همهشون زوجه. طبق اثبات قسمت الف یک دور اویلری داریم
این دور را در نظر میگیریم از یکی از درجه های فرد شروع میکنیم.دور اویلری موجود را ادامه میدهیم.تا برسیم به پایان خط یعنی آن یکی درجه فردمون.
حالا یال را حذف میکنیم. اینطوری از یک دور اویلری به یک گذر اویلری رسیده ایم که شرط مسئله را درست نگه میدارد
با تشکر
ع.ش | | | | | پاسـخ : | عليرضا جان!
ضمن تشكر از شما
جواب رو خيلي خوب توضيح داده و اثبات كردي.
آفرين بر شما و بارك الله!
از اين‌كه به اين زيبايي توضيح مي‌دهي تشكر مي‌كنيم.
منتظر حضور فعالت در ساير مسابقه‌ها هم هستيم.
با تشكر مجدد!
انشاءالله موفق باشي! | | | |
|
|
|
|
|
| |  | كاربران غيرعضو آنلاين: 2 | | | كاربران عضو آنلاين: 0 | | | کل كاربران آنلاين: 2 |
|
|
|
|