روش اجرای آزمونک
ابتدا ناورداهای سریع را مقایسه کن. اگر مانعی نبود، رأسهای نقشدار را متناظر و سپس همهٔ یالها را کنترل کن. راهنما در همریختی گراف قرار دارد.
۱۰ تمرین ناوردا و نگاشت
سؤال 1
دو گراف بهترتیب 5 و 6 رأس دارند. آیا ممکن است همریخت باشند؟
پاسخ تشریحی
خیر؛ همریختی یک تناظر یکبهیک میان رأسهاست و تعداد رأس باید برابر باشد.
سؤال 2
دو گراف تعداد رأس برابر ولی تعداد یال متفاوت دارند. نتیجه چیست؟
پاسخ تشریحی
ناهمریختاند؛ نگاشت همریخت یالها را حفظ میکند، پس تعداد یال یک ناورداست.
سؤال 3
دنبالهٔ درجهٔ دو گراف [3,2,2,1] و [3,3,1,1] است. همریختاند؟
پاسخ تشریحی
خیر؛ چندمجموعهٔ درجهها متفاوت است و همین برای اثبات ناهمریختی کافی است.
سؤال 4
گراف G مثلثی با رأسهای a,b,c و H مثلثی با رأسهای 1,2,3 است. یک همریختی بده.
پاسخ تشریحی
برای نمونه f(a)=1، f(b)=2 و f(c)=3. هر سه یال مثلث به سه یال مثلث دوم میروند؛ پس نگاشت معتبر است.
سؤال 5
G مسیر a−b−c−d و H مسیر 3−1−4−2 است. یک تناظر همریخت بنویس.
پاسخ تشریحی
f(a)=3، f(b)=1، f(c)=4، f(d)=2 مسیر را یالبهیال حفظ میکند.
سؤال 6
آیا یک دور 4 رأسی و یک مسیر 4 رأسی همریختاند؟
پاسخ تشریحی
خیر؛ درجههای دور همگی 2 است، اما مسیر دو رأس درجه 1 دارد؛ دنبالههای درجه متفاوتاند.
سؤال 7
دو گراف دنبالهٔ درجهٔ یکسان دارند. آیا حتماً همریختاند؟
پاسخ تشریحی
خیر؛ برابری دنبالهٔ درجه شرط لازم است، نه کافی. باید الگوی همسایگی، دورها یا نگاشت کامل نیز بررسی شود.
سؤال 8
در G تنها یک رأس درجه 3 و در H نیز تنها یک رأس درجه 3 وجود دارد. در هر همریختی این دو رأس چه میشوند؟
پاسخ تشریحی
چون درجه حفظ میشود و این نقش یکتا است، رأس درجه 3 در G باید به رأس درجه 3 در H نگاشت شود.
سؤال 9
یکی از دو گراف مثلث دارد و دیگری هیچ دور 3تایی ندارد. نتیجه چیست؟
پاسخ تشریحی
ناهمریختاند؛ نگاشت حافظ یال، دور سهتایی را نیز به دور سهتایی میبرد.
سؤال 10
دانشآموز فقط میگوید دو شکل شبیه هم دیده میشوند. برای اثبات همریختی چه کم است؟
پاسخ تشریحی
باید نگاشت یکبهیک و پوشا میان رأسها بدهد و نشان دهد مجاورت و نامجاورت تحت آن حفظ میشود.
چکلیست خودتصحیح
- تعداد رأس و یال را مقایسه کردم.
- دنبالهٔ درجه را مرتب نوشتم.
- رأسهای با درجه یا نقش یکتا را متناظر کردم.
- دورها و مؤلفهها را بهعنوان ناوردا سنجیدم.
- برای اثبات همریختی، نگاشت کامل و حفظ یالها را نشان دادم.