Matroid Theory and its Applications in Electric Network Theory and in Statics

من. موضوعات این کتاب مفهوم ماتروئید بیش از پنج دهه است که شناخته شده است. ویتنی (1935) آن را به عنوان تعمیم رایج نمودارها و ماتریس ها معرفی کرد. در دو دهه اخیر، به دلایل زیر مشخص شده است که این مفهوم چقدر اهمیت دارد: (1) ترکیبیات (یا ریاضیات گسسته) توسط بسیاری به عنوان مجموعه ای از ایده های جالب، گاهی عمیق، اما عمدتاً نامرتبط در نظر گرفته می شود. با این حال، مانند سایر شاخه های ریاضیات، ترکیبات نیز شامل برخی از ابزارهای عمومی است که می توان آنها را آموخت و سپس برای مسائل مختلف به کار برد. نظریه ماتروئید یکی از این ابزارهاست. (2) در ترکیبات، اهمیت نسبی الگوریتم ها با گسترش رایانه ها افزایش یافته است. تحلیل کلاسیک حتی مسائلی را که در آن «فقط» تعداد محدودی از موارد مورد مطالعه قرار می‌گرفت، در نظر نمی‌گرفت. اکنون چنین مشکلاتی نه تنها مورد توجه قرار می گیرند، بلکه پیچیدگی آنها اغلب با جزئیات قابل توجهی تحلیل می شود. به برخی از این نوع سؤالات (به عنوان مثال، تعیین اینکه چه زمانی الگوریتم به اصطلاح \"طمع\" بهینه است) حتی بدون ابزارهای matroidal نیز نمی توان پاسخ داد.

I. The topics of this book The concept of a matroid has been known for more than five decades. Whitney (1935) introduced it as a common generalization of graphs and matrices. In the last two decades, it has become clear how important the concept is, for the following reasons: (1) Combinatorics (or discrete mathematics) was considered by many to be a collection of interesting, sometimes deep, but mostly unrelated ideas. However, like other branches of mathematics, combinatorics also encompasses some gen­ eral tools that can be learned and then applied, to various problems. Matroid theory is one of these tools. (2) Within combinatorics, the relative importance of algorithms has in­ creased with the spread of computers. Classical analysis did not even consider problems where "only" a finite number of cases were to be studied. Now such problems are not only considered, but their complexity is often analyzed in con­ siderable detail. Some questions of this type (for example, the determination of when the so called "greedy" algorithm is optimal) cannot even be answered without matroidal tools.