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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש
Incomplete-document-purple.svg
יש להשלים ערך זה: בערך זה חסר תוכן מהותי.
הנכם מוזמנים להשלים את החלקים החסרים ולהסיר הודעה זו. שקלו ליצור כותרות לפרקים הדורשים השלמה, ולהעביר את התבנית אליהם.

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

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

הגדרה[עריכת קוד מקור | עריכה]

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

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

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

כבעיה חישובית[עריכת קוד מקור | עריכה]

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

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]

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