ماتروید

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از نظریه ماتروید)
پرش به: ناوبری، جستجو

تعریف ماتروید[ویرایش]

را یک مجموعه در نظر بگیرید. را زیرمجموعه‌ای از مجموعهٔ توانی بردارید، . اگر سه شرط زیر برای برقرار باشد آنگاه جفت مرتب را یک ماتروید روی می‌نامیم. را مجموعهٔ پس‌زمینهٔ این ماتروید و را گردایهٔ مجموعه‌های مستقل این ماتروید می‌نامیم. این سه شرط عبارت‌اند‌ از:

مکمل در را گردایهٔ مجموعه‌های وابستهٔ این ماتروید می‌گویند. عناصر وابسته مینیمال نسبت به رابطهٔ شمول را چرخه‌های این ماتروید می‌گویند. عناصر مستقل ماکسیمال نسبت به رابطهٔ شمول، پایه‌های این ماتروید گفته می‌شوند. ماتروید را می‌توان بوسیلهٔ مجموعه‌های وابسته یا چرخه‌ها یا پایه‌هایش نیز معرفی نمود.

نمونه‌ها[ویرایش]

در نظریهٔ گراف می‌توانید یک گراف را بردارید و مجموعهٔ پس‌زمینه را مجموعهٔ گره‌های آن برداشته و یک مجموعه از این گره‌ها را وابسته درنظر بگیرید هر گاه یک دور در زیرگراف القا شده از این گره‌ها وجود داشته باشد. به این ماتروید، ماتروید گرافی می‌گویند. در جبرخطی می‌توانید یک فضای برداری اتنخاب کرده و یک مجموعه بردار دلخواه از این فضا را به عنوان مجموعهٔ پس‌زمینه بردارید. یک مجموعه از این بردارها را وابسته گوئیم هر گاه وابستهٔ خطی باشند یعنی یک ترکیب خطی نابدیهی از آنها صفر شود. به این ماتروید، ماتروید ماتریسی می‌گوئیم. علت این نامگذاری این است که می‌توان نمایش برداری این بردارها را در نظر گرفته و با کنار هم قرار دادن آنها یک ماتریس داشت که آنگاه مجموعهٔ پس‌زمینهٔ ما گردایهٔ ستون‌های این ماتریس است. در جبرجابجایی می‌توان رابطهٔ وابستگی ماتروید را وابستگی جبری در نظر گرفت.

کاربرد[ویرایش]

به طور کلی داشتن ساختار ماترویدی در یک بحث ریاضی باعث می‌شود که ابزارها و قضایای زیادی را از جبرخطی و نظریهٔ گراف که مرتبط با ساختار ماترویدی‌شان است را به مبحث موردنظر انتقال داد. مسئلهٔ مهم دیگر مطالعهٔ چرخه‌ها و پایه‌ها است. در بسیاری از موارد ریاضیدانان به دنبال یافتن بزرگترین‌ها و کوچکترین‌های صادق در یک سری شرایط هستند که به شناخت برخی اشیاء ریاضی و کار کردن با آنها کمک می‌کند.

منابع[ویرایش]

  • James Oxley, Matroid Theory, Oxford