האלגברה של הכל

טבלת קישורים

תקציר ומבוא 1

2 הגדרות וסימונים בסיסיים

2.1 סטים

2.2 רצפים

2.3 חתימות ואלגברות ו-2.4 קטגוריות

3 מונוגרפיות והמורפיזמים שלהן

4 גבולות ו-Colimits

5 מונוגרפיות ציור

6 מבני גרפים ומונוגרפיות מוקלדות

7 תת-מונוגרפיות ומורפיזמים חלקיים

8 טרנספורמציות אלגבריות של מונוגרפיות

9 מונוגרפיות מוקלדות מיוחסות

10 מסקנה והפניות

תַקצִיר

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

מילות מפתח : טרנספורמציה של גרפים אלגבריים, מבני גרפים, גרפים מוקלדים

1 הקדמה

מושגים רבים ושונים של גרפים משמשים במתמטיקה ומדעי המחשב: גרפים פשוטים, גרפים מכוונים, רב-גרפים, היפרגרפים וכו'. מושג אחד אהוב בהקשר של לוגיקה ושכתוב הוא זה המוכר גם כ-quivers, כלומר, מבנים בצורה pN, E, s, tq כאשר N, E הם קבוצות ו- s מזדהות מ-N ו- s, (t) קצות מטרה של כל קצה (או חץ). אחת הסיבות לכך היא שקטגוריית הקולטים היא איזומורפית לקטגוריית האלגברות של החתימה הממוינת עם שני מיני צמתים וקצוות ושני שמות אופרטורים src ו-tgt של קצוות מסוג Ñ צמתים. בהתאם למסורת זו, בגרף אנו מתכוונים לרטט לאורך המאמר הזה.

על מנת לייצג בצורה נוחה מבני נתונים משוכללים, לעתים קרובות יש צורך להעשיר את המבנה של גרפים בתכונות: צמתים או קצוות עשויים להיות מסומנים עם אלמנטים מקבוצה קבועה, או עם ערכים שנלקחו באלגברה כלשהי, או עם קבוצות של ערכים כמו ב-[1] וכו'. דוגמה מעניינת ניתן למצוא ב-[2] עם הרעיון של גרפים E, שכן הם נחשבים גם כ-no-attributes.

ליתר דיוק, גרף E הוא אלגברה שהחתימה שלה יכולה להיות מיוצגת על ידי הגרף הבא:

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

מכאן שהדרך להכללה של מושג הגרפים כרוכה כנראה בהכללה של החתימה של גרפים הנחשבים כאלגברות. אחר הנתיב הזה הלך על ידי Michael L¨owe ב-[3], שם מבנה גרף מוגדר כחתימה מונאדית מגוונת רבות. ואכן בדוגמאות לעיל, ובדוגמאות רבות שסופקו ב-[3], לכל האופרטורים יש arity 1 ולכן הם יכולים להיחשב כקצוות מהתחום שלהם למיון הטווח שלהם. האם זו הסיבה לכך שהם נקראים מבני גרפים? אבל הדוגמה שלמעלה מראה שגרפים אלקטרוניים שונים מאוד מהגרף המייצג את החתימה שלהם. חוץ מזה, זה לא נוח שההבנה שלנו של מבנים כאלה תתבסס על תחביר, כלומר על השמות המסוימים שניתנו למיונים ואופרטורים בחתימה.

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

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

הגישה שננקטה כאן היא דווקא לדחות כל הבחנה מבנית בין צמתים וקצוות, ומכאן לאמץ תצוגה מאוחדת של צמתים כקצוות באורך 0, וקצוות סטנדרטיים כקצוות באורך 2 מכיוון שהם סמוכים לשני צמתים. תצוגה מאוחדת זו מאפשרת באופן הגיוני לקצוות להיות צמודים לכל קצוות ולא רק לצמתים, ובכך להכליל את קצוות ה-ev של גרפים E, ואפילו לקצוות הסמוכים לעצמם. לבסוף, אין סיבה להגביל את אורך הקצוות ל-0 או 2, ונמצא סיבות טובות (בסעיף 6) לאפשר קצוות באורך אינסופי, סידורי. המושגים והסימונים הדרושים מוצגים בסעיף 2. מבנה המונוגרפיה (יחד עם מורפיזמים) מוגדר בסעיף 3, ומניב אוסף של קטגוריות של מונוגרפיות לפי חלק ממאפייניהן. המאפיינים של קטגוריות אלה ביחס לקיומם של מגבלות ומגבלות משותפים מנותחים בסעיף 4.

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

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

הרעיון של מבנה גרף הוצג ב- [3] על מנת להשיג קטגוריות של הומורפיזמים חלקיים שבהם ניתן לבצע טכניקות של שכתוב גרפים אלגברי. ההתכתבות עם מונוגרפיות שנקבעו בסעיף 6 מחייבת התפתחות דומה של מורפיזמים חלקיים של מונוגרפיות בסעיף 7. לאחר מכן ניתן להגדיר, לנתח ולהשוות את שיטות הדחיפה הבודדת והכפולה של שכתוב מונוגרפיות.

המושג E-graph הוצג ב-[2] על מנת להשיג קטגוריות מתנהגות היטב (שכתוב גרף כתוב) של גרפים מיוחסים, ומכאן להציע ייצוגים מתאימים של מבני נתונים מהחיים האמיתיים. זה מושג על ידי העשרת גרפים E באלגברה מסוג נתונים, ועל ידי זיהוי צמתים בעלי ערך מיון עם האלמנטים של אלגברה זו. אנו נוקטים בגישה דומה בסעיף 9 עם הרעיון של מונוגרפיה מודפסת מיוחסת על ידי זיהוי אלמנטים של אלגברה עם קצוות, ומשיגים קטגוריות המתנהגות בצורה דומה. בשל האוניברסליות של מונוגרפיות אנו רואים שכל Σ-אלגברה יכולה להיות מיוצגת כמונוגרפיה מוקלדת מיוחסת.

אנו מסכמים בסעיף 10. שימו לב שחלקים מסעיפים 4 עד 6 פורסמו ב [4].