מיון מערך
- פותח הנושא עריסטו
- פורסם בתאריך
באופן כללי - אי אפשר
ברור שאפשר לסדר את המערך על ידי n-1 החלפות. יהי כל איבר במערך, קודקוד בגרף לא מכוון. צריך לפחות n-1 צלעות על מנת להגיע לכל קודקוד, ז"א - יש קודקוד בודד שלא הגענו אליו, ולא ביצענו איתו החלפה. *** אבל אם אחד האיברים נמצא במקומו הנכון ביחס למערך המסודר, אז ניתן לסדר בn-2, ואם יש k איברים שנמצאים במקומם הנכון אז אפשר לסדר על ידי n-k-1 החלפות ***
ברור שאפשר לסדר את המערך על ידי n-1 החלפות. יהי כל איבר במערך, קודקוד בגרף לא מכוון. צריך לפחות n-1 צלעות על מנת להגיע לכל קודקוד, ז"א - יש קודקוד בודד שלא הגענו אליו, ולא ביצענו איתו החלפה. *** אבל אם אחד האיברים נמצא במקומו הנכון ביחס למערך המסודר, אז ניתן לסדר בn-2, ואם יש k איברים שנמצאים במקומם הנכון אז אפשר לסדר על ידי n-k-1 החלפות ***
תוצאות בסיסיות מתורת החבורות
נפעיל פרמוטציה p על המערך המסודר לדוגמא:
נפעיל פרמוטציה p על המערך המסודר לדוגמא:
p=(1,2,...,n)
פרמוטציה זו היא n מעגל, והיא ניתן לפירוק לn-1 טרנספוזיציות (ולא פחות!). כאמור טרנספוזיציה היא החלפה של שני איברים. סדר הפרמוטציה הוא n בדיוק, משום שאם נפעיל את p^k עבור k<n לא נחזור למצב המקורי. pq=I =>p=q^-1 =>p^n=q^-n=>q^n=I על כן k הסדר של q מחלק את n, נניח בשלילה שk<n pq=I=>q=p^-1=>q^k=p^-k=>p^k=I שזו סתירה לכך שn הוא הסדר של p. לכן כל פרמוטציה הפוכה חייבת להיות מסדר n, ועל כן מאחר ואנו משתמשים בכל n האיברים, היא חייבת להיות מעגל מסדר n. וכל מעגל מסדר n מתפרק לn-1 טרנספוזיציות -> n-1 החלפות ואף לא אחת פחות. טיעון זה נכון לכל n מעגל, ולא בהכרח לפרמוטציה p שהוגדרה. כפי שאמרתי קודם ונימקתי על ידי עצים פורשים, אם יש k איברים שנמצאים במקומם הנכון, ניתן להסתפק רק ב n-k-1 החלפות (טרנספוזיציות). אבל אם k=0 חייבים להעזר n-1 כפי שהוכחתיאי דיוק קטן שחובה לתקנו
יכול להיות מצב שבו כל האיברים לא נמצאים במקומם, אך ניתן להעזר בפחות מn-1 החלפות כאשר p היא מכפלת שני מעגלים זרים שהgcd של הסדר שלהם קטן מn. דוגמא: n=6, p=(1,2)(3,4,5,6)zzz ניתן להסתפק בהחלפות הבאות: p=(1,2)(3,6)(3,5)(3,4)zzz שזה n-2 החלפות אבל שוב, עבור כל הפרמוטציות של הn מעגלים חייבים להעזר בn-1 החלפות.
יכול להיות מצב שבו כל האיברים לא נמצאים במקומם, אך ניתן להעזר בפחות מn-1 החלפות כאשר p היא מכפלת שני מעגלים זרים שהgcd של הסדר שלהם קטן מn. דוגמא: n=6, p=(1,2)(3,4,5,6)zzz ניתן להסתפק בהחלפות הבאות: p=(1,2)(3,6)(3,5)(3,4)zzz שזה n-2 החלפות אבל שוב, עבור כל הפרמוטציות של הn מעגלים חייבים להעזר בn-1 החלפות.
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.