מטרואיד

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

הגדרות

מטרואיד (סופי) $M$ הוא זוג סדור הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle (E,I)} , כאשר $E$ היא קבוצה של אובייקטים כלשהם ו-$I$ היא משפחה של תתי קבוצות של $E$. $E$ נקראת קבוצת הבסיס של המטרואיד. כל קבוצה ב-$I$ נקראת קבוצה בלתי תלויה של המטרואיד. קבוצה בלתי תלויה מקסימלית (ביחס להכלה, כלומר, כזו שכל קבוצה שמכילה אותה כבר לא בלתי תלויה) נקראת בסיס. קבוצה תלויה מינימלית ביחס להכלה (כלומר, כל איבר שנוריד ממנה יהפוך אותה לבלתי תלויה) נקראת מעגל. ניתן להגדיר מטרואיד באמצעות הקבוצות הבלתי תלויות שלו, הבסיסים שלו, המעגלים שלו ועוד.

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

זוג סדור $(E,I)$ כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} קבוצת איברים סופית ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} היא משפחה של תתי קבוצות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} הוא מטרואיד אם ורק אם:

1. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \emptyset \in I} .
2. לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\in I} , אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B\subseteq A} אז גם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B\in I} .
3. לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A,B\in I} , אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| B\right| > \left| A\right|} אז יש $x\in B\setminus A$ כך ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\cup \{x\}\in I} .

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

בסיסים

תהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} קבוצת בסיס כלשהי של איברים. תהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{B}} משפחה של תתי קבוצות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} . הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{B}} היא קבוצת בסיסים (קבוצות בלתי תלויות מקסימליות ביחס להכלה) של מטרואיד כלשהו אם ורק אם:

1. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{B}} אינה ריקה.
2. לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B_1,B_2\in \mathcal{B} } ולכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\in B_1\setminus B_2} קיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y\in B_2\setminus B_1} כך ש $B_{1}\setminus \{x\}\cup \{y\}$ הוא בסיס.

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

מעגלים

תהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} קבוצת בסיס כלשהי של איברים. תהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{C}} משפחה לא ריקה של תת-קבוצות לא ריקות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} . הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{C}} היא קבוצת המעגלים (קבוצות תלויות מינימליות ביחס להכלה; באנגלית - circuits) של מטרואיד כלשהו אם ורק אם:

1. לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_1\in \mathcal{C}} , אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_2\subset C_1} אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_2\notin \mathcal{C}} .
2. יהיו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_1,C_2\in \mathcal{C}} מעגלים שונים, ותהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\in C_1\cap C_2} נקודה. אז יש $C_{3}\subseteq C_{1}\cup C_{2}\setminus \{x\}$ כך ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_3\in\mathcal{C}} .

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

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

דוגמאות

תורת הגרפים

יהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G=(V,E)} גרף קשיר. מטרואיד המעגלים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} שמסומן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M(G)} הוא הזוג הסדור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (E,I)} כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} היא קבוצת הקשתות של הגרף ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} היא משפחה של קבוצות של קשתות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} המהוות (ביחד עם הקודקודים המחוברים להן) יער (כלומר, לא כוללות מעגלים). הקבוצות הבלתי תלויות הן כל קבוצות הקשתות שלא כוללות מעגלים בגרף. הבסיסים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M(G)} הם העצים הפורשים של $G$. המעגלים הם כל המעגלים הפשוטים בגרף. אכן, בכל גרף מתקיים שהקבוצה שלא מכילה קשתות היא קבוצה ללא מעגלים (=יער) ולכן בלתי תלויה. בנוסף, תת-קבוצה של יער מהווה בעצמה יער, ולבסוף, בהינתן שני יערות, האחד גדול מהשני, ישנה קשת מהיער הגדול שניתן להעביר ליער הקטן, ובכך להגדיל את היער הקטן מבלי להפכו לתלוי (כלומר מבלי לסגור בו מעגל). אם מדובר בגרף לא קשיר, יש להחליף את המילים "העצים הפורשים" ב"היערות הפורשים".

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

תהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} מטריצה מעל שדה כלשהו. עמודותיה הן וקטורים. המטרואיד הווקטורי על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} הוא הזוג הסדור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (E,I) } כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} היא קבוצת הווקטורים המהווים את עמודות המטריצה ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} היא משפחת קבוצות הווקטורים הבלתי תלויות (במובן הרגיל של אלגברה ליניארית) מתוך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} .

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

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

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

תהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} קבוצת ובה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} איברים. לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0\leq k\leq n} קיים מטרואיד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{k,n}} שקבוצת הבסיס שלו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} והוא מכונה מטרואיד יוניפורמי. במטרואיד זה, קבוצה נקראת בלתי תלויה אם עוצמתה קטנה או שווה מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} . למשל, אם קבוצת הבסיס שלנו היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{a,b,c,d\}} אז במטרואיד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{2,4}} הקבוצות הבלתי תלויות הן: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \emptyset , \{a\}, \{b\}, \{c\}, \{d\}, \{a,b\}, \{a,c\}, \{a,d\}, \{b,c\}, \{b,d\}, \{c,d\}} . במטרואיד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{0,n}} הקבוצה הבלתי תלויה היחידה היא הקבוצה הריקה. במטרואיד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{n,n}} כל הקבוצות הן בלתי תלויות. באופן כללי, במטרואיד יוניפורמי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{k,n}} , הקבוצות הבלתי תלויות הן כל הקבוצות בעוצמה קטנה או שווה ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} , הבסיסים הם כל הקבוצות בעוצמה בדיוק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} והמעגלים הם כל הקבוצות מעוצמה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k+1} .

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

יהי גרף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G=(V,E)} . תהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} משפחת כל קבוצות הקשתות שמהוות זיווג (לאו דווקא שלם). כלומר, קבוצת קשתות נמצאת ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} אם ורק אם אין בה זוג קשתות עם קודקוד משותף. אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M=(E,I)} אינו מטרואיד. אמנם, אף על פי שהקבוצה הריקה היא זיווג, וכל תת-קבוצה של זיווג היא בעצמה זיווג, הדרישה השלישית עבור מטרואידים אינה מתקיימת: בהינתן שני זיווגים בגרף בגדלים שונים, אין זה בטוח שניתן להעביר קשת מהגדול אל הקטן, ולהשאירו זיווג חוקי. למשל, בגרף הדו צדדי השלם על 4 קודקודים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{2,2}} , אם ניקח את הזיווג הקטן להיות קשת אחת (לא משנה איזו) ואת הזיווג הגדול להיות זוג קשתות אחרות, הוספת כל אחת מבין שתי הקשתות של הקבוצה הגדולה תהפוך את הקבוצה הקטנה לכזו שאינה זיווג.

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

דרגה

לכל מטרואיד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M=(E,I)} מוגדרת פונקציית דרגה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r: P(E)\rightarrow \mathbb{N}} , המחזירה לכל תת-קבוצה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} , את גודל תת-הקבוצה הבלתי תלויה הגדולה ביותר שלה. הדרגה של קבוצת הבסיס עצמה שווה לגודלי כל הבסיסים במטרואיד. במטרואידים וקטוריים, דרגה של קבוצה שקולה למימד של המרחב הווקטורי הנפרש על ידי הקבוצה. במטרואידים גרפיים, הדרגה של קבוצה היא גודל העץ (או היער) המקסימלי המוכל בה. במטרואיד יוניפורמי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{k,n}} , דרגתה של כל קבוצה בלתי תלויה היא עוצמתה, ודרגתה של כל קבוצה תלויה היא k.

קבוצה סגורה

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

סגור (closure)

לכל מטרואיד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M=(E,I)} מוגדרת פונקציית הסגור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle cl:P(E)\rightarrow P(E)} , המתאימה לכל תת-קבוצה של קבוצת הבסיס את הקבוצה הסגורה המינימלית המכילה אותה. במטרואידים וקטורים, הדבר שקול לכל איברי E הנפרשים על ידי הקבוצה.

דואליות

יהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M=(E,I)} ותהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{B}} קבוצת הבסיסים שלו. תהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{B^*}=\{E\setminus B | B\in \mathcal{B}\} } , קבוצת משלימי הבסיסים שלו. אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{B^*}} היא קבוצת בסיסים של מטרואיד אחר, שמכונה המטרואיד הדואלי ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} ומסומן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

מטרואיד40904209Q898572