מהי מטריצת סמיכות?
במאמר זה, אנו הולכים לדון במטריצת הסמיכות יחד עם הייצוג שלה.
הגדרת מטריצת סמיכות
בתורת הגרפים, מטריצת סמיכות היא דרך צפופה לתיאור מבנה הגרף הסופי. המטריצה הדו-ממדית היא המשמשת למיפוי הקשר בין צמתי הגרף.
אם יש לגרף נ מספר הקודקודים, אז מטריצת הסמיכות של הגרף הזה היא n x n , וכל כניסה של המטריצה מייצגת את מספר הקצוות מקודקוד אחד למשנהו.
מטריצת סמיכות נקראת גם בשם מטריצת חיבור . לפעמים זה נקרא גם א מטריצת קודקוד .
ייצוג מטריצת סמיכות
אם גרף לא מכוון G מורכב מ-n קודקודים אז מטריצת הסמיכות של גרף היא n x n מטריצה A = [aij] ומוגדרת על ידי -
א ij = 1 {אם קיים נתיב מ-V אני ל-V י }
א ij = 0 {אחרת}
בואו נראה כמה מהנקודות החשובות ביחס למטריצת הסמיכות.
- אם קיים קצה בין קודקוד V אני ו-V י , כאשר i הוא שורה, ו-j הוא עמודה, ואז הערך של a ij = 1.
- אם אין קצה בין קודקוד V אני ו-V י , ואז הערך של a ij = 0.
- אם אין לולאות עצמיות בגרף הפשוט, אז למטריצת הקודקוד (או מטריצת הסמיכות) צריכה להיות 0s באלכסון.
- מטריצת סמיכות היא סימטרית עבור גרף לא מכוון. הוא מציין שהערך ב-i ה' שורה ו-j ה' העמודה שווה לערך ב-j ה' שורה i ה'
- אם מטריצת הסמיכות מוכפלת בעצמה, ואם יש ערך שאינו אפס קיים ב-i ה' שורה ו-j ה' עמודה, ואז יש את המסלול מ-V אני ל-V י עם אורך שווה ערך ל-2. הערך שאינו אפס במטריצת הסמיכות מייצג שמספר הנתיבים הנבדלים קיים.
הערה: במטריצת סמיכות, 0 מייצג שאין קשר בין שני צמתים, בעוד ש-1 מייצג שיש קשר בין שני צמתים.
כיצד ליצור מטריצת סמיכות?
נניח שיש גרף ז עם נ מספר הקודקודים, אז מטריצת הקודקוד (או מטריצת הסמיכות) ניתנת על ידי -
א = א אחד עשר א 12 . . . . . א 1n א עשרים ואחת א 22 . . . . . א 2n . . . . . . . . . א n1 א n2 . . . . . א nn
איפה הא ij שווה למספר הקצוות מהקודקוד i עד j. כפי שהוזכר לעיל, מטריצת הסמיכות היא סימטרית עבור גרף לא מכוון, אז עבור גרף לא מכוון, ij = א הי .
כאשר הגרפים פשוטים ואין משקלים על הקצוות או קצוות מרובים, אז הכניסות של מטריצת הסמיכות יהיו 0 ו-1. אם אין לולאות עצמיות, אז הערכים האלכסוניים של מטריצת הסמיכות יהיו 0.
כעת, בואו נראה את מטריצת הסמיכות עבור גרף לא מכוון ועבור גרפים מכוונים.
מטריצת סמיכות לגרף לא מכוון
בגרף לא מכוון, קצוות אינם משויכים לכיוונים איתם. בגרף לא מכוון, אם קיים קצה בין קודקוד A לקודקוד B, אז ניתן להעביר את הקודקודים מ-A ל-B וכן מ-B ל-A.
הבה נבחן את הגרף הבלתי מכוון למטה וננסה לבנות את מטריצת הסמיכות שלו.
בגרף, אנו יכולים לראות שאין לולאה עצמית, ולכן הערכים האלכסוניים של המטריצה הסמוכה יהיו 0. מטריצת הסמיכות של הגרף לעיל תהיה -
מטריצת סמיכות לגרף מכוון
בגרף מכוון, הקצוות יוצרים זוג מסודר. קצוות מייצגים נתיב ספציפי מקודקוד A כלשהו לקודקוד אחר B. צומת A נקרא הצומת הראשוני, בעוד שצומת B נקרא הצומת המסוף.
הבה נבחן את הגרף המכוון למטה וננסה לבנות את מטריצת הסמיכות שלו.
בגרף הנ'ל, אנו יכולים לראות שאין לולאה עצמית, ולכן הערכים האלכסוניים של המטריצה הסמוכה יהיו 0. מטריצת הסמיכות של הגרף הנ'ל תהיה -
מאפייני מטריצת הסמיכות
חלק מהמאפיינים של מטריצת הסמיכות רשומים כדלקמן:
- מטריצת סמיכות היא מטריצה המכילה שורות ועמודות המשמשות לייצוג גרף פשוט עם תווית עם המספרים 0 ו-1 במיקום של (V אני , IN י ), לפי התנאי אם שני ה-V או לא אני ו-V י צמודים.
- עבור גרף מכוון, אם קיים קצה בין קודקוד i או V אני לקודקוד j או V י , ואז הערך של A[V אני ][IN י ] = 1, אחרת הערך יהיה 0.
- עבור גרף לא מכוון, אם יש קצה שקיים בין קודקוד i או V אני לקודקוד j או V י , ואז הערך של A[V אני ][IN י ] = 1 ו-A[V י ][IN אני ] = 1, אחרת הערך יהיה 0.
בואו נראה כמה שאלות של מטריצת הסמיכות. השאלות שלהלן הן על הגרפים הלא מכוונים והמכוונים המשוקללים.
הערה: אומרים שגרף הוא הגרף המשוקלל אם לכל קצה מוקצה מספר חיובי, הנקרא משקל הקצה.
שאלה 1 - מה תהיה מטריצת הסמיכות עבור הגרף המשוקלל הלא מכוון למטה?
פתרון - בשאלה הנתונה, אין לולאה עצמית, כך שברור שהכניסות האלכסוניות של המטריצה הסמוכה לגרף הנ'ל יהיו 0. הגרף הנ'ל הוא גרף לא מכוון. המשקולות בקצוות הגרף יוצגו ככניסות של מטריצת הסמיכות.
מטריצת הסמיכות של הגרף לעיל תהיה -
שאלה 2 - מה תהיה מטריצת הסמיכות עבור הגרף המשוקלל המכוון למטה?
פתרון - בשאלה הנתונה, אין לולאה עצמית, כך שברור שהכניסות האלכסוניות של המטריצה הסמוכה לגרף הנ'ל יהיו 0. הגרף הנ'ל הוא גרף מכוון משוקלל. המשקולות בקצוות הגרף יוצגו ככניסות של מטריצת הסמיכות.
מטריצת הסמיכות של הגרף לעיל תהיה -
מקווה שמאמר זה מועיל לך על מנת להבין על מטריצת סמיכות. כאן, דנו במטריצת הסמיכות יחד עם היצירה והמאפיינים שלה. דנו גם ביצירת מטריצת סמיכות על גרפים מכוונים או לא מכוונים, בין אם הם משוקללים או לא.
