ניתן לתאר את גרף האיזומורפיזם כגרף שבו גרף בודד יכול להיות יותר מצורה אחת. זה אומר שלשני גרפים שונים יכולים להיות אותו מספר של קצוות, קודקודים ואותם קישוריות קצוות. סוגים אלה של גרפים ידועים בתור גרפי איזומורפיזם. הדוגמה של גרף איזומורפיזם מתוארת באופן הבא:
הגרף לעיל מכיל את הדברים הבאים:
- אותו גרף מיוצג ביותר מצורה אחת.
- לפיכך, אנו יכולים לומר שהגרפים הללו הם גרפים של איזומורפיזם.
תנאים לאיזומורפיזם גרף
כל שני גרפים ייקרא איזומורפיזם אם הם עומדים בארבעת התנאים הבאים:
- יהיה מספר שווה של קודקודים בגרפים הנתונים.
- יהיה מספר שווה של קצוות בגרפים הנתונים.
- תהיה כמות שווה של רצף מעלות בגרפים הנתונים.
- אם הגרף הראשון יוצר מחזור באורך k בעזרת קודקודים {v1, v2, v3, …. vk}, אז גם גרף אחר חייב ליצור את אותו מחזור באורך זהה k בעזרת קודקודים {v1, v2, v3, …. K V}.
הערה: ניתן לתאר את רצף המעלות של גרף כרצף של מעלות של כל הקודקודים בסדר עולה.
נקודות חשובות
- כדי שכל שני גרפים יהיו איזומורפיזם, התנאים הדרושים הם ארבעת התנאים שהוגדרו לעיל.
- אין צורך שהתנאים שהוגדרו לעיל יספיקו כדי להראות שהגרפים הנתונים הם איזומורפיים.
- אם שני גרפים עומדים בארבעת התנאים שהוגדרו לעיל, גם אז, אין צורך שהגרפים יהיו בוודאי איזומורפיזם.
- אם הגרף לא עומד בתנאים כלשהם, אז אנחנו יכולים לומר שהגרפים הם בוודאי לא איזומורפיזם.
תנאים מספיקים לאיזומורפיזם גרף
אם אנחנו רוצים להוכיח ששני גרפים הם איזומורפיזם, יש כמה תנאים מספיקים שנספק לנו להבטיח ששני הגרפים הם בוודאי איזומורפיזם. כאשר שני הגרפים ינוקו בהצלחה את כל ארבעת התנאים הנ'ל, רק אז נבדוק את הגרפים הללו לתנאים מספיקים, המתוארים כדלקמן:
- אם הגרפים המשלימים של שני הגרפים הם איזומורפיזם, אזי הגרפים הללו יהיו בוודאי איזומורפיזם.
- אם המטריצות הסמוכות של שני הגרפים זהות, אז הגרפים הללו יהיו איזומורפיזם.
- אם הגרפים התואמים של שני גרפים מתקבלים בעזרת מחיקת כמה קודקודים של גרף אחד, והתמונות המתאימות שלהם בתמונות אחרות הן איזומורפיזם, רק אז הגרפים הללו לא יהיו איזומורפיזם.
כאשר שני גרפים עומדים באחד מהתנאים שלעיל, אז אנו יכולים לומר שהגרפים הללו הם בוודאי איזומורפיזם.
linux make command
דוגמאות לאיזומורפיזם גרף
ישנן הרבה דוגמאות לאיזומורפיזם גרף, המתוארות כך:
דוגמה 1:
בדוגמה זו, הראינו אם הגרפים הבאים הם איזומורפיזם.
פִּתָרוֹן: לשם כך, נבדוק את כל ארבעת התנאים של איזומורפיזם גרף, המתוארים כך:
תנאי 1:
- בגרף 1, יש מספר כולל של 4 קודקודים, כלומר G1 = 4.
- בגרף 2, יש מספר כולל של 4 קודקודים, כלומר G2 = 4.
כאן,
יש מספר שווה של קודקודים בשני הגרפים G1 ו-G2. אז הגרפים הללו עומדים בתנאי 1. כעת נבדוק את התנאי השני.
תנאי 2:
- בגרף 1, יש סה'כ 5 מספר קצוות, כלומר G1 = 5.
- בגרף 2, יש מספר כולל של 6 קצוות, כלומר G2 = 6.
כאן,
אין מספר שווה של קצוות בשני הגרפים G1 ו-G2. אז הגרפים האלה לא עומדים בתנאי 2. עכשיו אנחנו לא יכולים לבדוק את כל התנאים הנותרים.
מכיוון שהגרפים הללו מפרים את תנאי 2. אז הגרפים הללו אינם איזומורפיזם.
∴ גרף G1 וגרף G2 אינם גרפים של איזומורפיזם.
דוגמה 2:
בדוגמה זו, הראינו אם הגרפים הבאים הם איזומורפיזם.
פִּתָרוֹן: לשם כך, נבדוק את כל ארבעת התנאים של איזומורפיזם גרף, המתוארים כך:
תנאי 1:
- בגרף 1, יש מספר כולל של 4 קודקודים, כלומר G1 = 4.
- בגרף 2, יש מספר כולל של 4 קודקודים, כלומר G2 = 4.
- בגרף 3, יש מספר כולל של 4 קודקודים, כלומר G3 = 4.
כאן,
יש מספר שווה של קודקודים בכל הגרפים G1, G2 ו-G3. אז הגרפים הללו עומדים בתנאי 1. כעת נבדוק את התנאי השני.
תנאי 2:
- בגרף 1, יש סה'כ 5 מספר קצוות, כלומר G1 = 5.
- בגרף 2, יש סה'כ 5 מספר קצוות, כלומר G2 = 5.
- בגרף 3, יש סה'כ 4 מספר קצוות, כלומר G2 = 4.
כאן,
- יש מספר שווה של קצוות בשני הגרפים G1 ו-G2. אז הגרפים האלה עומדים בתנאי 2.
- אבל אין מספר שווה של קצוות בגרפים (G1, G2) ו-G3. אז הגרפים (G1, G2) ו-G3 אינם עומדים בתנאי 2.
מאז, הגרפים (G1, G2) ו-G3 מפרים את תנאי 2. אז אנחנו יכולים לומר שהגרפים האלה אינם איזומורפיזם.
∴ גרף G3 אינו איזומורפיזם עם גרף G1 ולא עם גרף G2.
מכיוון שהגרפים, G1 ו-G2 עומדים בתנאי 2. אז אנחנו יכולים לומר שהגרפים האלה עשויים להיות איזומורפיזם.
sonu nigam
∴ גרפים G1 ו-G2 עשויים להיות איזומורפיזם.
כעת נבדוק את התנאי השלישי עבור גרפים G1 ו-G2.
תנאי 3:
- בגרף 1, מידת הרצף s היא {2, 2, 3, 3}, כלומר, G1 = {2, 2, 3, 3}.
- בגרף 2, מידת הרצף s היא {2, 2, 3, 3}, כלומר, G2 = {2, 2, 3, 3}.
כאן
יש מספר שווה של רצפי מעלות בשני הגרפים G1 ו-G2. אז הגרפים האלה עומדים בתנאי 3. כעת נבדוק את התנאי הרביעי.
תנאי 4:
גרף G1 יוצר מחזור באורך 3 בעזרת קודקודים {2, 3, 3}.
גרף G2 גם יוצר מחזור באורך 3 בעזרת קודקודים {2, 3, 3}.
כאן,
זה מראה ששני הגרפים מכילים את אותו מחזור מכיוון ששני הגרפים G1 ו-G2 יוצרים מחזור באורך 3 בעזרת קודקודים {2, 3, 3}. אז הגרפים האלה עומדים בתנאי 4.
לכן,
- הגרפים G1 ו-G2 עומדים בכל ארבעת התנאים הנחוצים לעיל.
- אז G1 ו-G2 עשויים להיות איזומורפיזם.
כעת נבדוק מספיק תנאים כדי להראות שהגרפים G1 ו-G2 הם איזומורפיזם.
השחקנית סאי פאלאווי
בדיקת תנאים מספקים
כפי שלמדנו שאם הגרפים המשלימים של שני הגרפים הם איזומורפיזם, שני הגרפים יהיו בוודאי איזומורפיזם.
אז נצייר את הגרפים המשלימים של G1 ו-G2, המתוארים כדלקמן:
בגרפים המשלימים לעיל של G1 ו-G2, אנו יכולים לראות ששני הגרפים הם איזומורפיזם.
∴ גרפים G1 ו-G2 הם איזומורפיזם.
דוגמה 3:
בדוגמה זו, הראינו אם הגרפים הבאים הם איזומורפיזם.
הוספה של java למערך
פִּתָרוֹן: לשם כך, נבדוק את כל ארבעת התנאים של איזומורפיזם גרף, המתוארים כך:
תנאי 1:
- בגרף 1, יש בסך הכל 8 מספר קודקודים, כלומר, G1 = 8.
- בגרף 2, יש בסך הכל 8 מספר קודקודים, כלומר, G2 = 8.
כאן,
יש מספר שווה של קודקודים בשני הגרפים G1 ו-G2. אז הגרפים הללו עומדים בתנאי 1. כעת נבדוק את התנאי השני.
תנאי 2:
- בגרף 1, המספר הכולל של הקצוות הוא 10, כלומר, G1 = 10.
- בגרף 2, המספר הכולל של הקצוות הוא 10, כלומר, G2 = 10.
כאן,
יש מספר שווה של קצוות בשני הגרפים G1 ו-G2. אז הגרפים האלה עומדים בתנאי 2. כעת נבדוק את התנאי השלישי.
תנאי 3:
- בגרף 1, מידת הרצף s היא {2, 2, 2, 2, 3, 3, 3, 3}, כלומר G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- בגרף 2, מידת הרצף s היא {2, 2, 2, 2, 3, 3, 3, 3}, כלומר, G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
כאן
יש מספר שווה של רצפי מעלות בשני הגרפים G1 ו-G2. אז הגרפים האלה עומדים בתנאי 3. כעת נבדוק את התנאי הרביעי.
תנאי 4:
- גרף G1 יוצר מחזור באורך 4 בעזרת מעלות 3 קודקודים.
- גרף G2 אינו יוצר מחזור באורך 4 בעזרת קודקודים מכיוון שקודקודים אינם סמוכים.
כאן,
שני הגרפים G1 ו-G2 אינם יוצרים את אותו מחזור עם אותו אורך. אז הגרפים האלה מפרים את תנאי 4.
מכיוון שגרפים G1 ו-G2 מפרים את תנאי 4. אז בגלל ההפרה של תנאי 4, הגרפים האלה לא יהיו איזומורפיזם.
∴ גרפים G1 ו-G2 אינם איזומורפיזם.