מטרואיד – הבדלי גרסאות

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