מטרואיד

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

הגדרות

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

קבוצות בלתי תלויות

זוג סדור $(E,I)$ כך ש-$E$ קבוצת איברים סופית ו-$I$ היא משפחה של תתי קבוצות של $E$ הוא מטרואיד אם ורק אם:

1. $\emptyset \in I$.
2. לכל $A\in I$, אם $B\subseteq A$ אז גם $B\in I$.
3. לכל $A,B\in I$, אם $\left|B\right|>\left|A\right|$ אז יש $x\in B\setminus A$ כך ש- $A\cup \{x\}\in I$.

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

בסיסים

תהי $E$ קבוצת בסיס כלשהי של איברים. תהי ${\mathcal {B}}$ משפחה של תתי קבוצות של $E$. ${\mathcal {B}}$ היא קבוצת בסיסים (קבוצות בלתי תלויות מקסימליות ביחס להכלה) של מטרואיד כלשהו אם ורק אם:

1. ${\mathcal {B}}$ אינה ריקה.
2. לכל $B_{1},B_{2}\in {\mathcal {B}}$ ולכל $x\in B_{1}\setminus B_{2}$ קיים $y\in B_{2}\setminus B_{1}$ כך ש $B_{1}\setminus \{x\}\cup \{y\}$ הוא בסיס.

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

מעגלים

תהי $E$ קבוצת בסיס כלשהי של איברים. תהי ${\mathcal {C}}$ משפחה של תתי קבוצות של $E$. ${\mathcal {C}}$ היא קבוצת המעגלים (קבוצות תלויות מינימליות ביחס להכלה) של מטרואיד כלשהו אם ורק אם:

1. $\emptyset \notin {\mathcal {C}}$.
2. לכל $C_{1}\in {\mathcal {C}}$, אם $C_{2}\subset C_{1}$ אז $C_{2}\notin {\mathcal {C}}$.
3. יהיו $C_{1},C_{2}\in {\mathcal {C}}$ ויהי $x\in C_{1}\cap C_{2}$. אז יש $C_{3}\subseteq C_{1}\cup C_{2}\setminus \{x\}$ כך ש- $C_{3}\in {\mathcal {C}}$.

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

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

דוגמאות

תורת הגרפים

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

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

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

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

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

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

תהי $E$ קבוצת ובה $n$ איברים. לכל $0\leq k\leq n$ קיים מטרואיד $U_{k,n}$ שקבוצת הבסיס שלו $E$ והוא מכונה מטרואיד יוניפורמי. במטרואיד זה, קבוצה נקראת בלתי תלויה אם עוצמתה קטנה או שווה מ-$k$. למשל, אם קבוצת הבסיס שלנו היא $\{a,b,c,d\}$ אז במטרואיד $U_{2,4}$ הקבוצות הבלתי תלויות הן: $\emptyset ,\{a\},\{b\},\{c\},\{d\},\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}$. במטרואיד $U_{0,n}$ הקבוצה הבלתי תלויה היחידה היא הקבוצה הריקה. במטרואיד $U_{n,n}$ כל הקבוצות הן בלתי תלויות. באופן כללי, במטרואיד יוניפורמי $U_{k,n}$, הקבוצות הבלתי תלויות הן כל הקבוצות בעוצמה קטנה או שווה ל-$k$, הבסיסים הם כל הקבוצות בעוצמה בדיוק $k$ והמעגלים הם כל הקבוצות מעוצמה $k+1$.

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

יהי גרף $G=(V,E)$. תהי $I$ משפחת כל קבוצות הקשתות שמהוות זיווג (לאו דווקא שלם). כלומר, קבוצת קשתות נמצאת ב-$I$ אם ורק אם אין בה זוג קשתות עם קודקוד משותף. אז $M=(E,I)$ אינו מטרואיד. אמנם, למרות שהקבוצה הריקה היא זיווג, וכל תת-קבוצה של זיווג היא בעצמה זיווג, הדרישה השלישית עבור מטרואידים אינה מתקיימת: בהינתן שני זיווגים בגרף בגדלים שונים, אין זה בטוח שניתן להעביר קשת מהגדול אל הקטן, ולהשאירו זיווג חוקי. למשל, בגרף הדו צדדי השלם על 4 קודקודים $K_{2,2}$, אם ניקח את הזיווג הקטן להיות קשת אחת (לא משנה איזו) ואת הזיווג הגדול להיות זוג קשתות אחרות, הוספת כל אחת מבין שתי הקשתות של הקבוצה הגדולה תהפוך את הקבוצה הקטנה לכזו שאינה זיווג.

הגדרות בסיסיות נוספות

דרגה

לכל מטרואיד $M=(E,I)$ מוגדרת פונקציית דרגה $r:P(E)\rightarrow \mathbb {N}$, המחזירה לכל תת-קבוצה של $E$, את גודל תת-הקבוצה הבלתי תלויה הגדולה ביותר שלה. הדרגה של קבוצת הבסיס עצמה שווה לגדלי כל הבסיסים במטרואיד. במטרואידים וקטוריים, דרגה של קבוצה שקולה למימד של המרחב הווקטורי הנפרש על ידי הקבוצה. במטרואידים גרפיים, הדרגה של קבוצה היא גודל העץ (או היער) המקסימלי המוכל בה. במטרואיד יוניפורמי $U_{k,n}$, דרגתה של כל קבוצה בלתי תלויה היא עוצמתה, ודרגתה של כל קבוצה תלויה היא k.

קבוצה סגורה

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

סגור (closure)

לכל מטרואיד $M=(E,I)$ מוגדרת פונקציית הסגור $cl:P(E)\rightarrow P(E)$, המתאימה לכל תת-קבוצה של קבוצת הבסיס את הקבוצה הסגורה המינימלית המכילה אותה. במטרואידים וקטורים, הדבר שקול לכל איברי E הנפרשים על ידי הקבוצה.

דואליות

יהי $M=(E,I)$ ותהי ${\mathcal {B}}$ קבוצת הבסיסים שלו. תהי ${\mathcal {B^{*}}}=\{E\setminus B|B\in {\mathcal {B}}\}$, קבוצת משלימי הבסיסים שלו. אז ${\mathcal {B^{*}}}$ היא קבוצת בסיסים של מטרואיד אחר, שמכונה המטרואיד הדואלי ל-$M$ ומסומן $M^{*}$. במטרואידים גרפיים של גרפים מישוריים, ההגדרה מתלכדת עם הגדרת הגרף הדואלי (הגרף בו הפאות הופכות לקודקודים).

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

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

לקריאה נוספת

• Welsh, D. J. A. (1976), Matroid Theory, Academic Press, מסת"ב 012744050X.
• Oxley, James (1992), Matroid Theory, New York: Oxford University Press, מסת"ב 0-19-853563-5, MR1207587.

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

• "מהו מטרואיד?" (באנגלית). מאמר מבואי אך מקיף בנושא.