تالار گفتمان مانشت

با توجه به بحث
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
که قفل شده!

نقل قول: راستی میشه برای گراف‌های کامل اینطور که گفتید نمونه‌ی کلی آورد؟ مثلاً برای گراف [tex]K_{n,n}[/tex] تعداد حالت‌ها [tex]2(n!)^{2}[/tex]باشه؟

و همچنین میشه برای گراف [tex]K_{n}[/tex] تعداد اتومورفیزم ها رو از این فرمول رو بدست آورد [tex]n![/tex]

آیا این دو فرمول برقرارند؟

لطفا راهنمایی کنید

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

سلام....
سوالو به صورت کامل واستون توضیح می دم با اینکه سوال مال خیلی وقته پیشه حالا اگر دیدینش بخوانیدش:
سوال 32 :

سوال گفته یک اتومورفیزم یک ایزومورفیزم از گراف به خودش است.و همانجوری که می دانید ایزوموفیزم تابع یک به یک و پوشا مثلا بین گرف G1 و گراف G2 یک ایزومورفیزم درست کنیم یعنی رئوس گراف G1 رو می نگاشتیم به رئوس گراف G2 به این می گفتن ایزومورفیزم و اتومورفیزم یعنی گراف به خودش یعنی رئوس گراف رو به خودش بنگاریم جوری که گرافه عوض نشه به همچین چیزی اتومورفیزم یا خودریختی گفته می شه:

حالا گزینه ها:

1)k3,3 ,36 تا اتومورفیزم داره که از این طریق به دست میاد: (البته باید با توجه به شکلش حساب کنیم):
3!*3!*2 یعنی
kn,n می شه :2*N!^2 اتومورفیزم داره!
N^2! به خاطر اینکه هر دسته با خودش!(اولیشو می شه به 3 طریق بعدی رو به 2 طریق و راس آخر یه دسته رو به یه طریق به هم نگاشت کنیم و اون سمتم همین طور)
2 برابرم به خاطر اینکه هر دسته با خودش نگاشت داره!(یعنی می توان جای دسته بالا و پایین رو با هم عوض کرد واین روند بالا واسه اونام بوجود می یاد)

2)ولی در km,n می شه m!*n! یعنی n ها با خودشون و m ها با خودشون می تونند نگاشت بشن!

3)اتومورفیزم یعنی رئوس این گرافو با یک تابع یک به یک و پوشا بدیم به رئوس همین گراف به طوری که گراف همین گراف بماند یعنی هر کیو به خودش بدیم و یعنی هر گراف حداقل یه اتومورفیزم رو داره و اگر شکلو بکشید می بینید که گراف عوض نمی شه و اگر بخواهیم یه اتومورفیزم واسه این شکل بکشیم باید 14 (1و 2 رو نباید به هم بدیم چون 1 درجش 1 و 2 درجش 2 است و به همین ترتیب:41 , 23,32 (یعنی 2 رو به 3 نگاشت کنیم یعنی تصویرشون کردیم به هم با توجه به درجه رئوس اون مجموعه اصلی که گزینه داده!)).پس این دو تا تابع اتومورفیزم یک به یک و پوشایی داره که شکل رو تغییر نمی ده و همین نگه می داره!

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

که اگه حساب کنید 1 غلط و بقیه درستند.

موفق باشید...

سپاس فراوان

آیا این درسته که دو تا اتومورفیزم هاش اینان ؟

1234 و 4321

(19 بهمن 1392 12:24 ق.ظ)tayebe68 نوشته شده توسط: [ -> ]سپاس فراوان

آیا این درسته که دو تا اتومورفیزم هاش اینان ؟

۱۲۳۴ و ۴۳۲۱

بله

این هم یک مثال دیگه از «خودریختی» (Automorphism)