میتروید

الگو:Short description در ترکیبیات، مِیتروید الگو:به انگلیسی الگو:IPAc-en (ممکن است در ترجمه ها به آن متروید، ماتروید و... هم گفته شود) ساختاری است که مفهوم استقلال خطی در فضاهای برداری را تجرید سازی کرده و تعمیم می دهد. از نظر اصول موضوعه منطقی، روش های بسیاری برای تعریف یک میتروید وجود دارد که مهم ترین آن ها ازین قرارند: براساس مجموعه ها؛ پایه ها و مدارها؛ توابع رتبه؛ عملگرهای بستار؛ مجموعه های بسته یا فلت‌ها. به زبان مجموعه های مرتب جزئی، یک میتروید متناهی معادل با مشبکه هندسی است.

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

تعاریف

طرق متنوعی برای تعریف میتروید (متناهی) وجود دارد که با هم رمزریخت (کریپتومورف) هستند:

مجموعه‌های مستقل

برحسب استقلال، یک میتروید متناهی $M$ شامل زوج مرتب $(E,ℐ)$ است که $E$ مجموعه ای متناهی (که به آن مجموعه زمینه گفته می شود) و $ℐ$ خانواده ای از زیرمجموعه های $E$ (که به آن مجموعه های مستقل گفته می شود) است که دارای خواص زیر باشد:

1. مجموعه تهی مستقل است، یعنی $\mathrm{\varnothing }\in ℐ$. یا به عباری، حداقل یکی از زیرمجموعه های $E$ مستقل است، یعنی $ℐ\ne \mathrm{\varnothing }$.
2. هر زیرمجموعه از یک مجموعه مستقل، مستقل است، یعنی برای هر $A^{\prime }\subseteq A\subseteq E$، اگر $A\in ℐ$ آنگاه $A^{\prime }\in ℐ$. این خاصیت را برخی مواقع خاصیت موروثی، یا خاصیت بسته از پایین نیز می گویند.
3. اگر $A$ و $B$ دو مجموعه مستقل باشند (یعنی، هر مجموعه مستقل باشند) و $A$ از $B$ عناصر بیشتری داشته باشد، آنگاه وجود دارد $x\in A\setminus B$ چنان که $B\cup \{x\}$ در $ℐ$ است. برخی اوقات به این خاصیت خاصیت افزودگی یا خاصیت تبادل مجموعه مستقل نیز می گویند.

دو خاصیت اول ساختاری ترکیبیاتی به نام دستگاه استقلال (یا مجتمع سادکی مجرد) تعریف می کنند.

نمونه‌ها

مرتبط

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

کاربرد

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

پانویس

• الگو:یادکرد-ویکی

منابع

• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Springer
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation
• الگو:Citation.
• الگو:Citation. Reprinted in الگو:Harvtxt, pp. 55–79.
• الگو:Citationالگو:Dead link.

پیوندهای بیرونی

• الگو:Springer
• Kingan, Sandra : Matroid theory. A large bibliography of matroid papers, matroid software, and links.
• Locke, S. C. : Greedy Algorithms.
• Pagano, Steven R. : Matroids and Signed Graphs.
• Mark Hubenthal: A Brief Look At Matroids (PDF) (contain proofs for statements of this article)
• James Oxley : What is a matroid? (PDF)
• Neil White : Matroid Applications