איזומורפיזם של גרפים

בתורת הגרפים, איזומורפיזם של גרפים הוא התאמה בין הקודקודים של שני גרפים המשרה התאמה בין הקשתות. גרפים איזומורפיים (כאלו שיש ביניהן איזומורפיזם) הם זהים זה לזה מכל בחינה תאורטית. מציאת איזומורפיזם בין גרפים היא בעיה חישובית קשה ומפורסמת.

משפט וויטני קובע ששני גרפים קשירים הם איזומורפיים אם ורק אם ה-Line graphs שלהם איזומורפיים, למעט חריג אחד: המשולש איננו איזומורפי לגרף הקלשון (קודקוד אחד מחובר לשלושה) אף על פי שה-Line graphs שלהם כן.

הגדרה

גרפים $G$ ו-$H$ הם איזומורפיים אם קיימת פונקציה $f:V\left(G\right)\rightarrow V\left(H\right)$ חד-חד-ערכית ועל, כך שעבור כל $v,w\in V\left(G\right)$, מספר הקשתות המקשרות בין $v$ ו-$w$ זהה למספר הקשתות המקשרות בין $f\left(v\right)$ ו-$f\left(w\right)$.

שני גרפים, $G$ ו-$H$, אשר איזומורפיים זה לזה, יסומנו כך: $G\simeq H$.

כל התכונות שאפשר לנסח במונחי השפה של תורת הגרפים נשמרות תחת איזומורפיזם. למשל, אם G ו-H איזומורפיים ואחד מהם פשוט, מכוון, בעל מסלול המילטוני, דו-צדדי, או מושלם, אז כך גם השני. איזומורפיזם שומר גם על תכונות מספריות של הגרף: המספר הכרומטי, הדרגה הממוצעת, המותן וכדומה.

כבעיה חישובית

הבעיה של לקבוע האם שני גרפים נתונים הם איזומורפיים היא ב-NP כי בהינתן התאמה בין הגרפים, קל לוודא שהיא אכן איזומורפיזם. ב-2017 הראה Laszlo Babai שהסיבוכיות היא תת-אקספוננציאלית: 2^{O((log n)3)}. עם זאת, לבעיה התכונה הנדירה יחסית שלא ידוע האם היא ב-P, אך גם לא ידוע האם היא NPC (כלומר NP שלמה). בעיה מפורסמת נוספת עם תכונה זו היא בעיית הפירוק לגורמים. משערים שהבעיה איננה NPC, שכן זה יגרור קריסה של ההיררכיה הפולינומית.

הכללה של בעיה זו, השואלת האם גרף מסוים איזומורפי לתת-גרף של גרף אחר, היא ב-NPC (שכן ניתן להראות רדוקציה פולינומית מבעיית הקליקה אליה).

קישורים חיצוניים

מדיה וקבצים בנושא איזומורפיזם של גרפים בוויקישיתוף

• איזומורפיזם של גרפים, באתר MathWorld (באנגלית)

הערות שוליים

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.