מטרואיד

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

הגדרות

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

תורת הגרפים

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

אלגברה ליניארית

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

מטרואידים יוניפורמיים

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

דוגמה למבנה שאינו מטרואיד

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

דרגה

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

קבוצה סגורה

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

סגור (closure)

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

דואליות

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

ההיררכיה המטרואידית

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