صفحه‌ها: ۱ ۲
سلام.
دوستان این سوال مربوط به IT 91 است.
ممنون میشم درباره‌ی پاسخش راهنمایی کنید.
تشکر.
(۰۳ بهمن ۱۳۹۱ ۱۲:۵۷ ق.ظ)mohammad-a نوشته شده توسط: سلام.
دوستان این سوال مربوط به IT 91 است.
ممنون میشم درباره‌ی پاسخش راهنمایی کنید.
تشکر.
اگر پاسخ تشریحیش رو دارید بذارید تا روش بحث کنیم
سلام. چون نمیدونم ایزومورفیزم و اتومورفیزم چیه بنظرم باید به گزینه ۴ اعتماد کنم. طبق این تعریف گزینه ۲ و ۳ درست و ۱ غلطه.
گزینه ۳ گرافمون فقط ۴ راس و یه مسیر بطول ۳ داریم. نامگذاری یا از آخر به اول یا اول به آخر با ترتیب ۱و۲و۳و۴ میشه.
گزینه ۲ قسمت ۳ راسی با !۳ حالت و قسمت ۵ راسی با !۵ حالت جابجا میشن. تعداد کل حالات میشه !۳×!۵=۷۲۰
گزینه ۱ هم مشابه گزینه ۲ همون !۳×!۳ میشه ولی میشه جای دوتا ۳ تایی رو باهم عوض کرد. مثلاً اگه رئوس ۱و۲و۳ در یک سمت باشن برای مکان راس ۱ ما ۶ حالت و برای ۲ و ۳ به ترتیب ۲ و ۱ حالت انتخاب داریم. برای ۳ راس باقی مونده هم به ترتیب ۳ و ۲ و ۱ حالت. ضرب حالات میشه ۷۲ حالت.
(۰۶ بهمن ۱۳۹۱ ۱۲:۰۸ ق.ظ)Jooybari نوشته شده توسط: سلام. چون نمیدونم ایزومورفیزم و اتومورفیزم چیه بنظرم باید به گزینه ۴ اعتماد کنم. طبق این تعریف گزینه ۲ و ۳ درست و ۱ غلطه.
گزینه ۳ گرافمون فقط ۴ راس و یه مسیر بطول ۳ داریم. نامگذاری یا از آخر به اول یا اول به آخر با ترتیب ۱و۲و۳و۴ میشه.
گزینه ۲ قسمت ۳ راسی با !۳ حالت و قسمت ۵ راسی با !۵ حالت جابجا میشن. تعداد کل حالات میشه !۳×!۵=۷۲۰
گزینه ۱ هم مشابه گزینه ۲ همون !۳×!۳ میشه ولی میشه جای دوتا ۳ تایی رو باهم عوض کرد. مثلاً اگه رئوس ۱و۲و۳ در یک سمت باشن برای مکان راس ۱ ما ۶ حالت و برای ۲ و ۳ به ترتیب ۲ و ۱ حالت انتخاب داریم. برای ۳ راس باقی مونده هم به ترتیب ۳ و ۲ و ۱ حالت. ضرب حالات میشه ۷۲ حالت.
من اصلا متوجه نمیشم میتونید واضحتر توضیح بدید، اگه میشه گزینه ۴ هم توضیح بدید ممنون
(۰۴ بهمن ۱۳۹۱ ۰۴:۱۶ ب.ظ)mohandeszahra نوشته شده توسط: اگر پاسخ تشریحیش رو دارید بذارید تا روش بحث کنیممتأسفانه پاسخش رو نداشتم.
(۰۶ بهمن ۱۳۹۱ ۱۲:۰۸ ق.ظ)Jooybari نوشته شده توسط: سلام. چون نمیدونم ایزومورفیزم و اتومورفیزم چیه بنظرم باید به گزینه ۴ اعتماد کنم. طبق این تعریف گزینه ۲ و ۳ درست و ۱ غلطه.
گزینه ۳ گرافمون فقط ۴ راس و یه مسیر بطول ۳ داریم. نامگذاری یا از آخر به اول یا اول به آخر با ترتیب ۱و۲و۳و۴ میشه.
گزینه ۲ قسمت ۳ راسی با !۳ حالت و قسمت ۵ راسی با !۵ حالت جابجا میشن. تعداد کل حالات میشه !۳×!۵=۷۲۰
گزینه ۱ هم مشابه گزینه ۲ همون !۳×!۳ میشه ولی میشه جای دوتا ۳ تایی رو باهم عوض کرد. مثلاً اگه رئوس ۱و۲و۳ در یک سمت باشن برای مکان راس ۱ ما ۶ حالت و برای ۲ و ۳ به ترتیب ۲ و ۱ حالت انتخاب داریم. برای ۳ راس باقی مونده هم به ترتیب ۳ و ۲ و ۱ حالت. ضرب حالات میشه ۷۲ حالت.
تشکر آقای جویباری؛ لطف کردید.
نکته‌ای که نوشتید خیلی جالب بود٬ دقت نکرده بودم که طراح سؤال به‌گونه‌ای قصد راهنمایی داشته در گزینه‌ی چهارم.
یک سؤال٬ با توجه به این تعریف٬ برای گزینه‌ی ۳ باید گرافِ بدون جهت فرض بشه؟ (چون به‌نظر اگر جهتدار بگیریم نمیشه فرض سؤال رو برآورده کرد)
گزینه سوم نباید جهتدار باشه. فقط وجود مسیز رو میگه.
گزینه ۴ هم یه تعریف از صورت سواله. میگه گراف رو رسم میکنیم. بعد تعداد حالاتی که میشه به هر راس از گراف یه اسم نسبت داد که گرافمون عوض نشه رو مینویسیم. مثلاً برای گراف k4 این حالات میشن !۴ و یا اگه یه راس رو به دوتا راس از گراف k4 اضافه کنیم و گراف جدید بسازیم، مسلماً راس جدیدی که اضافه شده فقط ۱ حالت داره، دوراس با درجه ۳ و دو راس با درجه ۴ هم هرجفتشون ۲ حالت دارن. درکل میشه ۴ حالت.
Formally, an automorphism of a graph G = (V,E) is a permutation σ of the vertex set V, such that the pair of vertices (u,v) form an edge if and only if the pair (σ(u),σ(v)) also form an edge. That is, it is a graph isomorphism from G to itself. Automorphisms may be defined in this way both for directed graphs and for undirected graphs. The composition of two automorphisms is another automorphism, and the set of automorphisms of a given graph, under the composition operation, forms a group, the automorphism group of the graph
منبع :ویکیخب متن بالا برا دوستانی که زبانشون قوی هست
اما نکات بحث
«خودریختی» (Automorphism)
بازهم رو مطلب بحث میکنیم
تشکر فراوان.
فکر میکنم متوجه سوال شدم.
تا جایی که متوجه شدم، در سوال ایزومورف‌ها با در نظر گرفتن خودِ ترتیب رئوس را یکی در نظر می‌گیریم. چون برای گزینه‌ی سوم ترتیب ۱۲۳۴ و ۴۳۲۱ که قابل قبول هستند و ترتیب ۴۲۳۱ یا ۱۳۲۴ میتونه با هر کدام از دو حالت گفته شده یکریخت باشه.
یا برای نمونه‌ای که خود شما آوردید، تعداد حالت‌ها را به خاطر یکسان بودن ماتریس‌ها !۵ در نظر نمیگیرید.
احیاناً اشتباه میکنم؟
راستی میشه برای گراف‌های کامل اینطور که گفتید نمونه‌ی کلی آورد؟ مثلاً برای گراف [tex]\small k_{n,n}[/tex] تعداد حالت‌ها [tex]\small 2(n!)^2[/tex] باشه؟
آیا این تعریفی که از همریختی آوردید با همان تعریفی که در کتاب آقای یوسفی آورده شده یکی است؟
"دو گراف را همریخت گوییم اگر با هم ایزومورفم (یکریخت) باشند یا با تقسیم مبنا از یکی به دیگری رسید"
--------------------------------------------------------------------------
این تعاریف رو تو سیستم های جبری داریم
ایزومورفیسم =یکریختی شرط یک به یک و پوشا
اتومورفیسم = خودریختی شرط تساوی
مونومورفیسم =تک ریختی شرط یک به یک
اپی مورفیسم =بروریختی شرط پوشا
اندومورفیسم=درون ریختی شرط زیرمجموعه بودن
----------------------------------------------------------------
حالا تو گراف کدوم هاش رو داریم؟ و با چه تعاریفی؟
گراف همریخت (همومورفیک)
دو گراف همریخت هستند اگر باتقسیم مبنا بتوان از یکی به دیگری رسید
دوگراف همریخت هستند اگر یکریخت باشند
ممکن است گرافی یکریخت نباشد ولی همریخت باشد!
-----------------------------------------------------------
(۰۷ بهمن ۱۳۹۱ ۰۲:۱۲ ب.ظ)Jooybari نوشته شده توسط: فرضسلام.
ببخشید می شه یه مثال بزنید مثلا برای گزینه ۴ حلش کنید چه طور دو حالتش به دست می آد.من نفمیدم
دوستان عزیز من روی گزینه ۳ هم گیج میزنم!الان چرا اینا باهم اتو نیستند؟(اصلا اینا با هم ایزو هستند یا نه)
[tex]1\rightarrow2\rightarrow3\rightarrow4[/tex]
[tex]2\rightarrow3\rightarrow4\rightarrow1[/tex]
[tex]3\rightarrow2\rightarrow1\rightarrow4[/tex]
.
.
.
چرا فقط اون دوتایی که گفتید اتو هستند؟!مگه نباید تعداد ایزومورفیزم های G رو با خودش بدست بیاریم؟
سلام. خوب توی این مثالهایی که زدید یالهامون ۱۲ و ۲۳ و ۳۴ نیستن. یالها فقط توی اولی هستن.
(۱۳ بهمن ۱۳۹۱ ۰۲:۳۷ ق.ظ)Jooybari نوشته شده توسط: سلام. خوب توی این مثالهایی که زدید یالهامون ۱۲ و ۲۳ و ۳۴ نیستن. یالها فقط توی اولی هستن.تا اینجا که من از ایزو مورفیزم فهمیدم اسم یال ها و رئوس مهم نیست!مهم اینه که یشه اون معادل سازی رو روی رئوس و یال ها انجام داد حالا هر نامی می تونن داشته باشن!ما این ۴ عدد رو هر جوری با این ترتیب خطی بچینیم گراف حاصل ایزومورف با خودشه!
من اشتباه می کنم!؟
(۱۳ بهمن ۱۳۹۱ ۰۷:۱۷ ق.ظ)۸Operation نوشته شده توسط: تا اینجا که من از ایزو مورفیزم فهمیدم اسم یال ها و رئوس مهم نیست!مهم اینه که یشه اون معادل سازی رو روی رئوس و یال ها انجام داد حالا هر نامی می تونن داشته باشن!ما این ۴ عدد رو هر جوری با این ترتیب خطی بچینیم گراف حاصل ایزومورف با خودشه!
من اشتباه می کنم!؟
ماتریس این گراف هایی که می کشین رو رسم کنین ببینین جز اون ۲ حالت که اقای جویباری می گن بقیه متفاوتن .
(۰۶ بهمن ۱۳۹۱ ۱۲:۰۸ ق.ظ)Jooybari نوشته شده توسط: گزینه ۲ قسمت ۳ راسی با !۳ حالت و قسمت ۵ راسی با !۵ حالت جابجا میشن. تعداد کل حالات میشه !۳×!۵=۷۲۰
گزینه ۱ هم مشابه گزینه ۲ همون !۳×!۳ میشه ولی میشه جای دوتا ۳ تایی رو باهم عوض کرد. مثلاً اگه رئوس ۱و۲و۳ در یک سمت باشن برای مکان راس ۱ ما ۶ حالت و برای ۲ و ۳ به ترتیب ۲ و ۱ حالت انتخاب داریم. برای ۳ راس باقی مونده هم به ترتیب ۳ و ۲ و ۱ حالت. ضرب حالات میشه ۷۲ حالت.
توی مورد گزینه ۲ که K3,5 داریم هم می شه رئوس یه بخش با بخش دیگه جایگشت داشته باشه. مثلا اگه رئوس ۱و۲و۳ توی بخش اول و ۴و۵و۶و۷و۸ توی بخش دوم باشه خوب می تونیم مثلا راس شماره ۲ رو با زاس ۶ عوض کنیم ؟ اما ما فقط جایگشت بین رئوس بخش اول رو جدا و بین بخش دوم رو هم جدا می گیرین بعد در هم ضرب می کنیم. چرا رئوس رو بین ۲ بخش رو جابجا نمی کنیم ؟