ماراتن گراف

[Olympiad]

سلام !!!! ....

اين تاپيكو زدم براي اين كه واقعا نياز بود ... اون ماراتن تركيبيات هم كه رفته اون ته تها ......

خوب ما ميخوايم تو اين تاپيك مسئله حل كنيم و الگوريتم هاي گراف رو كار كنيم .....

قوانين :

1- شماره زدن بالاي سوال .
2- حداكثر 2 سوال ميتوانند هم زمان مطرح شوند.
3- اگه الگوريتمي رو استفاده مي كنيد تو يه پست جداگانه يه توضيحي راجع بهش بدين.
4- از سوال آسون شروع ميشه و ....

من نميدونم چه سوالي بذارم ..... يك نفر سوال بذاره !!!!

......

 

[Ali1993]

سلام ...
ببخشید میام تو تاپیک مربوط به شما مطلب می نویسم . اگه سوال می خواید من می نویسم . فقط ببخشید که خیلی آسونه . خب ما کنکوری ایم دیگه
چند ریخت گراف نیمه اویلری مرتبه ی 5 با ماکزیمم درجه ی 4 وجود دارد ؟
اگه از این جور سوالا می خواید بازم بنویسم ، اگر هم که اینا براتون جزء بدیهیاته شرمنده که مزاحم شدم .

 

[Goharshady]

سلام ...
ببخشید میام تو تاپیک مربوط به شما مطلب می نویسم . اگه سوال می خواید من می نویسم . فقط ببخشید که خیلی آسونه . خب ما کنکوری ایم دیگه
چند ریخت گراف نیمه اویلری مرتبه ی 5 با ماکزیمم درجه ی 4 وجود دارد ؟
اگه از این جور سوالا می خواید بازم بنویسم ، اگر هم که اینا براتون جزء بدیهیاته شرمنده که مزاحم شدم .

بدیهی وجود ندارد.
برتراند راسل

حتی بدیهی ترین چیزها بدیهی نیستند
گئورگ کانتور

 

[SABB]

سلام ...
ببخشید میام تو تاپیک مربوط به شما مطلب می نویسم . اگه سوال می خواید من می نویسم . فقط ببخشید که خیلی آسونه . خب ما کنکوری ایم دیگه
چند ریخت گراف نیمه اویلری مرتبه ی 5 با ماکزیمم درجه ی 4 وجود دارد ؟
اگه از این جور سوالا می خواید بازم بنویسم ، اگر هم که اینا براتون جزء بدیهیاته شرمنده که مزاحم شدم .

بدیهی وجود ندارد.
برتراند راسل

حتی بدیهی ترین چیزها بدیهی نیستند
گئورگ کانتور

ببخشید سوال نامرتبط می پرسم. ولی میخواستم بدونم گئورگ کانتور همون جرج کانتور است؟!

 

[Goharshady]

سلام ...
ببخشید میام تو تاپیک مربوط به شما مطلب می نویسم . اگه سوال می خواید من می نویسم . فقط ببخشید که خیلی آسونه . خب ما کنکوری ایم دیگه
چند ریخت گراف نیمه اویلری مرتبه ی 5 با ماکزیمم درجه ی 4 وجود دارد ؟
اگه از این جور سوالا می خواید بازم بنویسم ، اگر هم که اینا براتون جزء بدیهیاته شرمنده که مزاحم شدم .

بدیهی وجود ندارد.
برتراند راسل

حتی بدیهی ترین چیزها بدیهی نیستند
گئورگ کانتور

ببخشید سوال نامرتبط می پرسم. ولی میخواستم بدونم گئورگ کانتور همون جرج کانتور است؟!

به روسی: گئورگ
به انگلیسی : جرج
به فرانسوی : ژرژ
به آلمانی : ژرچ

 

[Goharshady]

سلام ...
ببخشید میام تو تاپیک مربوط به شما مطلب می نویسم . اگه سوال می خواید من می نویسم . فقط ببخشید که خیلی آسونه . خب ما کنکوری ایم دیگه
چند ریخت گراف نیمه اویلری مرتبه ی 5 با ماکزیمم درجه ی 4 وجود دارد ؟
اگه از این جور سوالا می خواید بازم بنویسم ، اگر هم که اینا براتون جزء بدیهیاته شرمنده که مزاحم شدم .

نمی شه برنامه شو بنویسم که حساب کنه؟

 

[Ali1993]

سلام ...
ببخشید میام تو تاپیک مربوط به شما مطلب می نویسم . اگه سوال می خواید من می نویسم . فقط ببخشید که خیلی آسونه . خب ما کنکوری ایم دیگه
چند ریخت گراف نیمه اویلری مرتبه ی 5 با ماکزیمم درجه ی 4 وجود دارد ؟
اگه از این جور سوالا می خواید بازم بنویسم ، اگر هم که اینا براتون جزء بدیهیاته شرمنده که مزاحم شدم .

نمی شه برنامه شو بنویسم که حساب کنه؟

من که نمی دونم اینی که الان گفتید یعنی چه !
به هر حال امیدوارم همتون موفق باشید . امیدوارم شتر کنکور دم در خونه ی هیچ کدومتون نخوابه .

 

[SABB]

[center:43b3c09aa2]

5 تا.
[/center:43b3c09aa2]

 

[SABB]

[center:797e77a660]

مکعب n بعدی: اگر n==0 باشد یک نقطه و در غیر این صورت از دو مکعب n-1 بعدی که نقاط متناظر آن ها به هم متصل شده اند به وجود می آید.
گراف k-مکعب: گرافی با راس های متناظر با دنباله های k بیتی که دو راس آن به هم وصل اند اگر و فقط اگر دنباله های متناظرشان دقیقا در یک مولفه متفاوت باشند.

ثابت کنید گراف k مکعب با مکعب k بعدی یکریخت است!

[/center:797e77a660]

 

[SABB]

[center:91fb2660ef]

کافی است نشان دهیم یک دوسویگی

از رئوس های مکعب k بعدی به رئوس k-مکعب وجود دارد طوری که مجاورت ها را حفظ کند. برای این کار کافی است ثابت کنیم می توان راس های مکعب k بعدی را طوری با دنباله های k بیتی شماره گذاری کرد که دو راس آن وقتی و فقط وقتی به هم متصل باشند که دنباله های متناظرشان دقیقا در یک مولفه با هم تفاوت داشته باشند.
پایه استقرا به ازای n=0 برقرار است. فرض کنیم چنین شماره گذاری ای برای مکعب n بعدی درست باشد. اکنون مکعب n+1 بعدی که از دو مکعب n بعدی به دست آمده را درنظر می گیریم؛ راس های هر دو مکعب n بعدی را طبق فرض استقرا شماره گذاری کرده و به آخر دنباله های مکعب اول یک بیت 0 و به آخر دنباله های مکعب دوم یک بیت 1 اضافه می کنیم. این اضافه کردن بیت در هیچ یک از دو مکعب خاصیت شماره گذاری را تغییر نمی دهد و نیز ارتباطات بین رئوس متناظر این دو مکعب دقیقا در یک بیت (همان بیت آخر که اضافه شده) با یکدیگر اختلاف دارند. بنابراین شماره گذاری خواسته شده به دست آمد.

لطفا یکی سوال بعدی رو بذاره

[/center:91fb2660ef]

 

[sts3662]

ابر مکعب k تایی را با استفاده از ضرب دکارتی در گراف شرح دهید .

ضرب دکارتی : گراف های a , b را داریم . b تا از گراف a کنار هم بگذارید و سپس ریوس متناظر را مثل گراف b به هم وصل کنید . ( a تا از گراف b و b تا از گراف a داریم ...)

 

[Olympiad]

پاسخ : ماراتن گراف

لطفا یکی سوال بعدی رو بذاره !!!

 

[Olympiad]

پاسخ : ماراتن گراف

خوب سوال بعد رو خودم میذارم :37::37::58:

3​

ثابت کنید در گراف دو بخشی k-منتظم یال برشی نداریم​

 

[Olympiad]

پاسخ : ماراتن گراف

کسی نیست ؟؟؟ :38::38::38:​

 

[mahanmath]

پاسخ : ماراتن گراف

کسی نیست ؟؟؟ :38::38::38:​

آخه اکثر بچه ها سوالای مرحله ۲ رو دیدن ، فک کنم بهتر باشه از یه منبع دیگه سوال مطرح بشه .

 

[Olympiad]

پاسخ : ماراتن گراف

آخه اکثر بچه ها سوالای مرحله ۲ رو دیدن ، فک کنم بهتر باشه از یه منبع دیگه سوال مطرح بشه .

خوب شما سوال بذارید !

 

[rezashiri]

پاسخ : ماراتن گراف

4)

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

ب) فرض کنید که g یک گراف ساده که هیچ راس درجه 0 ندارد و هیچ زیر گراف القایی با 3 یال ندارد.ثابت کنید g دارای حداکثر 4 راس است.

 

[Olympiad]

پاسخ : ماراتن گراف

4)



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

ب) فرض کنید که g یک گراف ساده که هیچ راس درجه 0 ندارد و هیچ زیر گراف القایی با 3 یال ندارد.ثابت کنید g دارای حداکثر 4 راس است.

الف ) فرض کنید گراف مورد نظر n راس داشته باشد .... اگر یک راس را کنار بگذاریم ، به

طریق میتوان یال هایی بین این n-1 راس رسم کرد سپس راس n ام را اضافه میکنیم و این راس را به تمام راس هایی که درجه ی فرد دارند وصل میکنیم (بدیهی است درجه این راس نیز زوج خواهد بود) .... بنابراین تعداد گراف ها با رئوس درجه ی زوج برابر

ب ) راهنمایی : باید روی مولفه های گراف G کار کنید !!!!!!!!!!!!! :25::213:


خوب یکی سوال بعد رو بذاره ....البته هنوز سوال 3 حل نشده !!!

 

[1995parham]

پاسخ : ماراتن گراف

5
حداکثر تعداد دور های به طول 3 را در یک تورمنت n راسی بیابید و ثابت کنید که این تعداد بیشینه است.

 

[rezoos]

پاسخ : ماراتن گراف

خوب سوال بعد رو خودم میذارم :37::37::58:

3​

ثابت کنید در گراف دو بخشی k-منتظم یال برشی نداریم​

سوال فنی , بببخشید اگه ضایغه . یال برشی چیه?