سوالات جالب گراف !

[RezaSi]

سلام ...

اگه کسی سوال قشنگی از این قسمت داره بزاره حل کنیم ( مخصوصا با Shayan بودم :p )

و لطفا شماره هم بزنید اگه کسی خواست جواب بده مشکلی نداشته باشه ...

سوال 1 : G گرافی 2-منتظم از مرتبه ی 7 و H گرافی 3-منتظم است . هر راس G را به تمام راسهای H وصل کردیم . گراف حاصل منتظم است.اندازه گراف جدید کدام است ؟

50 75 80 100

[Shayan]

پاسخ سوال 1: جهت حل بدین صورت می نویسیم:
در مورد گراف G مرتبه و اندازه را به ترتیب p1 و q1 می گیریم.
در مورد این گراف واضح است که 7=p1=q1 پس تا اینجا این را فهمیدیم.
در مورد گراف H اطلاع مشخصی نداریم، پس مرتبه ی آن را x می گیریم.
خوب پس اندازه آن طبق فرمول pr=2q می شود 3x/2 .
حال می گوییم گراف جدید منتظم است.
پس بدین صورت عمل می کنیم:
ابتدا در مورد این که گراف چند منتظم است. می دانیم گراف G دو منتظم بود، از هر راس به x راس گراف دوم وصل شد و گراف حاصل منتظم است.
پس گراف ما 2+x منتظم است.
تعداد راس ها هم که مشخص است x+7 تا می باشد.
می ماند اندازه گراف:
ببینید به تعداد هر راس گراف G چون هر کدام به x راس گراف H وصل می شود x یال اضافه می گردد به تعداد کل یال ها.
پس ما 7x یال اضافه خواهیم داشت.
خوب پس اندازه گراف نهایی خواهد شد:
7+7x+3x/2
خوب حالا فرمول رو می نویسیم:

خوب واضح است که x نمی تواند صفر باشد.
پس x برابر 8 می باشد.
حال x را در فرمولی که برای اندازه کلی در آوردیم می گذاریم و حاصل برابر 75 می گردد.
یکم سر سری شد البته پاسخم.

موفق باشید

[Shayan]

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

موفق باشید دوست عزیز

[RezaSi]

جالب بود ولی یکم طولانی شد ...

راه حل من فکر کنم کوتاه تره : اول می بینیم که همه ی راس های g به h وصل شده و چون g 7 راس داره پس به هر راس گراف h هفت یال اضافه شده یعنی گرافمون باید 10-منتظم باشه و چون همه ی راس های h هم به g وصل شدن و گراف باید 10منتظم باشه پس تعداد راس های h هم 10 - 2 = 8 هستش پس کلا گرافمون 15 راس داره و 10-منتظمه پس کلا 150/2 = 75 یال داره ...

البته راه حل شما هم همین بود فقط یکم به زبون غیر ریاضوی گفتمش ...

لطفا اگه سوالی دارید بزارید ... مرسی !

در مورد ورود به انجمنم فکر نکنم خیلی بمونم ... فوقش تا اول مهر ... سطحمم خیلی بالا نی ... خیلی بیشتر باید تلاش کنم ... بازم مرسی که جواب می دید !

[Shayan]

یکی از دوستان سوالی پرسیده بود گفتم اینجا هم بگذارم:

پرسش 2: دترمینان ماتریس مجاورت گراف کامل از مرتبه 80 چند است؟

[RezaSi]

یکی از دوستان سوالی پرسیده بود گفتم اینجا هم بگذارم:

پرسش 2: دترمینان ماتریس مجاورت گراف کامل از مرتبه 80 چند است؟

راستش من دترمینان گراف n*n رو بلد نیستم ( یه چیزایی می دونم ولی نه خیلی کامل) ... فکر کنم این سوال باشه برا بعد این که تو هندسه تحلیلی دترمینانو خوندم حل کنم بهتره ... :p

بعدش این سوال گراف نبود که ... همش شد ماتریس ... یه سوال گراف خوشگل بده فکر کنم .... :D

بازم مرسی از لطفت .

[Shayan]

الآن راستش سوال درست حسابی از مبحث گراف دم دست ندارم که شما که المپیادی هستید رو راضی کنه.
ولی اگه چیزی دیدم می گذارم.

موفق باشید

[RezaSi]

شما که سوال نمی زاری من می زارم : ( البته اینا خیلی قشنگ نیست ( در واقع برای کنکور قشنگه فقط ! )) :

سوال 3 : در گرافی با دنباله درجات s:4,3,3,3,1 چند دور وجود دارد ؟

4 5 6 7

حالا شما هم اگه سوال داری بزار ... در همین حدود باشه هم خوبه !

[Shayan]

رسم گراف:



دورها:

1-abca
2-abda
3-acda
4-bcdb
5-abcda
6-acbda
7-abdca

[RezaSi]

سوال 4 :



http://s1.picofile.com/file/7501282896/Test.jpeg

[Shayan]

اول استنباطاتی از صورت سوال می کنیم:
با توجه به سوال:

1- هیچ کس به خود نامه نمی نویسد - گراف طوقه ندارد
2- هیچ کس بیشتر از یک نامه نمی نویسد - یال موازی نداریم
3- هرکس به شخصی نامه می نویسد که از او نامه دریافت کرده باشد - گراف جهت ندارد یا به عبارتی عر رفتی بازگشتی دارد.

از این موارد نتیجه می گیریم که گراف ساده هست.
خوب، هر شخص به دو نفر نامه می نویسد، پس گراف ما گراف 2 منتظم از مرتبه 5 است.
خوب پس فقط شکل پنج ضلعی می تونه باشه.
حالا باید ببینیم اگر افراد a و b و c و d و e باشند، چند حالت داریم، خوب این عین این میمونه که بگیم با این مهره ها چجوری میشه دستبند درست کرد!
طبق فرمولش میشه 1-5 فاکتوریل تقسیم بر 2 و میشه 12.
حالا راه دیگه،
یک مهره رو ثابت فرض می کنیم و جایگشت بقیه رو حساب می کنیم، با توجه به تقارن نصف حالات تکراری میشه پس باید حاصل تقسیم بر 2 بشه و باز هم جواب 12.

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

[ani htmi]

سوالات اساسی در درس گسسته قسمت گراف؟

سلام و درود خدمت استادان گرامی.باعرض پوزش از اینکه وقتتون رو میگیرم.لطفا اگه میشه پاسخ تشریحی سوالاتم رو بهم بدین ممنون و سپاسگزار


1-بامجموعه رئوس{V={a . b .c .d .e. f چند گراف ساده بادویال می توان رسم کرد بطوری که هر دویال یک راس مشترک داشته باشند؟



2-با مجموعه رئوس {V={a . b .c .d .e. f چند گراف ساده با دویال می توان رسم کرد بطوری که هر دویال از هم جدا باشند؟



3-دوری به طول P که (p≥3) رابه عنوان گراف G در نظر بگیرید. گراف S را با افزودن یک راس به گراف G و وصل کردن آن به همه راسهای G میسازیم . تعداد دورهای به طول Pگراف S چیست ؟ P . P+1 .P -1 .P+2




4-دوری به طول P که (p≥3) رابه عنوان گراف G در نظر بگیرید. گراف S را با افزودن یک راس به گراف G و وصل کردن آن به همه راسهای G میسازیم . تعداد دورهای به طول 4گراف S چیست ؟ P . P+1 . P یا P+1 . و ترتیب 4 از P



5- شش تیم دو به دو باهم مسابقه می دهند . تعداد کل بازیها در پایان مسابقات کدام است؟ 10 . 30 . 12 .15