רשימת סמיכות

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

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

יתרונות שיטת ייצוג על ידי רשימת סמיכות בהשוואה לשיטות אחרות:

1. יעילות מקום: בשיטה זו צריך לאחסן רק מידע על צמתים מקושרים
2. השיטה מאפשרת זיהוי מהיר של צמתים סמוכים.
3. דרישת הזיכרון של שיטה זו יחסית נמוכה.

חסרונות שיטת ייצוג על ידי רשימת סמיכות בהשוואה לשיטות אחרות:

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

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

ייצוג רשימת סמיכות

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

דוגמה לגרף שמתאר רשימת סמיכות עם צמתים שונים (A,B,C,D,E).

בגרף לדוגמה, צומת A מקושר לצומת B וגם D כך שניתן לראות שכיוון הקשר לא נקבע, ולכן זהו גרף לא מכווננן (undirected graph) כלומר A קשור ל-B וגם B קשור ל-A. הרשימה המייצגת לקשרים של A תהיה:

D

B

→A

בצורה דומה עבור B רשימת הסמיכות תהיה:

E

C

A

→B

עבור C:

D

B

→C

עבור D:

E

C

A

→D

עבור E:

D

B

→E

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

גרף מכוונן לדוגמה, שמתאר רשימת סמיכות עם צמתים שונים (A,B,C).

עבור A רשימת הסמיכות תהיה:

C

B

→A

עבור B:

C

→B

עבור C:

Null

→C

כך מתקיים יישום קוד גנרי של רשימת סמיכות, למשל עבור התרשים הבא:

גרף שמתאר רשימת סמיכות גנרית עם צמתים שונים (A,B,C,D,E) לדוגמה עבור יישום קוד גנרי.

adjacency_list = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"]
}

רשימת סמיכות בכימיה

רשימת סמיכות בהקשרי כימיה היא שיטה כללית לאפיין מולקולה כימית. השיטה משולבת במחוללי מנגנונים לתגובות כימיות, למשל Reaction Mechanism Generator (RMG). ‏RMG הוא מחולל מנגנונים אוטומטי שמרכיב מודלים קינטיים הכוללים תגובות ליסודות כימיות, באמצעות נתונים וידע על אופן הפעולה של המולקולות המשתתפות בתגובות. באמצעות השיטה ניתן להצמיד רשימת סמיכות לכל הרכב כימי, שהוא מעט שונה מגרפים גנריים, מכיוון שנדרש להוסיף מידע על מבנה האלקטרונים חופשיים ועל סדר הקשרים הכימיים.

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

<number> [<label>] <element> u<unpaired> [p<pairs]> [c<charge>] [<site>] [m<morphology] <bondlist>

כאשר:

• <number>, מספר: מספר זיהוי עבור כל אטום בודד.
• <label>, תיוג: שם תג אפשרי שניתן לייחס לאטום.
• <element>, "יסוד": הוא הסמל הכימי של האטום על פי טבלת היסודות.

הפרמטרים הנוספים מהווים הגדרות עבור המצב האלקטרוני של אותו האטום. לא נדרש להוסיף את כולם לרשימת סמכויות כדי שתהיה תקנית.

• "u": מספר האלקטרונים הבלתי קשורים (למשל רדיקלים).
• "p": מספר זוגות אלקטרונים בלתי קשורים.
• "c": המטען הפורמלי הרלוונטי של האטום, כאשר למשל c-1 הוא מטען פורמלי שלילי ו-c+1 מטען חיובי.
• "s": סוג האתר בו האטום נמצא (למשל במבנים גבישיים שונים).
• "m": המורפולוגיה של האתר בו מצוי האטום.
• "bondlist": רשימה של הקשרים הקיימים עבור אותו האטום עם אטומים אחרים במולקולה. קשר מסומן על ידי מספר שמייצג אטום אחר ברשימת הסמכויות, ואות שמסמלת את סוג הקשר (קשר יחיד, כפול או משולש). למשל, לאטום שישנו קשר כפול עם אטום מספר 2, יירשם {2,D}.

עבור כלל הפרמטרים ניתן לרשום אפשרויות שונות שעשויות להתקיים במולקולה, למשל עבור קשר שעשוי להיות כפול או יחיד עם אטום מספר 2, יירשם:

{2,[S,D]}

כאמור, כללים אלו תקפים עבור רשימת סמיכות שמשולבת ב-RMG. דוגמה עבור רשימת סמכויות כזו עבור המולקולה אצטילן (C₂H₂) היא:

מולקולת אצטילן. האטומים במולקולה מסומנים בהתאם לרשימת הסמיכות.

1 C u0 p0 c0 {2,T} {3,S}
2 C u0 p0 c0 {1,T} {4,S}
3 H u0 p0 c0 {1,S}
4 H u0 p0 c0 {2,S}

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

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

מדיה וקבצים בנושא רשימת סמיכות בוויקישיתוף

• רשימת סמיכות, באתר MathWorld (באנגלית)

הערות שוליים

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