Shortest Connectivity: An Introduction with Applications in Phylogeny

مشکل \"کوتاهترین اتصال\" تاریخچه طولانی و پیچیده ای دارد: با توجه به مجموعه محدودی از نقاط در یک فضای متریک، شبکه ای را جستجو کنید که این نقاط را با کمترین طول ممکن به هم متصل کند. این کوتاه ترین شبکه باید یک درخت باشد و ممکن است دارای رئوس متفاوت از نقاطی باشد که قرار است متصل شوند. در طول سال ها مشکلات زندگی واقعی بیشتری ارائه می شود که از این مشکل یا یکی از نزدیکان آن به عنوان یک برنامه کاربردی، به عنوان یک مشکل فرعی یا یک مدل استفاده می کنند.

این جلد مقدمه‌ای است بر تئوری «کوتاه‌ترین اتصال»، به‌عنوان هسته اصلی «مسائل طراحی شبکه هندسی»، که مشکل کلی را می‌توان به صورت زیر بیان کرد: با توجه به پیکربندی رئوس و/یا لبه‌ها، شبکه‌ای را بیابید که حاوی این اشیاء است، برخی الزامات از پیش تعیین‌شده را برآورده می‌کند، و یک تابع هدف معین را که به چندین معیار فاصله بستگی دارد، به حداقل می‌رساند. کاربرد جدیدی از کوتاه‌ترین اتصال نیز مورد بحث قرار گرفته است، یعنی ایجاد درخت‌هایی که تاریخچه تکاملی \"موجودات زنده\" را منعکس می‌کنند.

هدف در این متن سطح فارغ‌التحصیل، تشریح مفاهیم کلیدی ریاضی است که زیربنای آن هستند. این سوالات مهم در ریاضیات کاربردی این مفاهیم شامل ریاضیات گسسته (به ویژه نظریه گراف)، بهینه سازی، علوم کامپیوتر و چندین ایده در زیست شناسی است.

The problem of "Shortest Connectivity" has a long and convoluted history: given a finite set of points in a metric space, search for a network that connects these points with the shortest possible length. This shortest network must be a tree and may contain vertices different from the points which are to be connected. Over the years more and more real-life problems are given, which use this problem or one of its relatives as an application, as a subproblem or a model.

This volume is an introduction to the theory of "Shortest Connectivity", as the core of the so-called "Geometric Network Design Problems", where the general problem can be stated as follows: given a configuration of vertices and/or edges, find a network which contains these objects, satisfies some predetermined requirements, and which minimizes a given objective function that depends on several distance measures. A new application of shortest connectivity is also discussed, namely to create trees which reflect the evolutionary history of "living entities".

The aim in this graduate level text is to outline the key mathematical concepts that underpin these important questions in applied mathematics. These concepts involve discrete mathematics (particularly graph theory), optimization, computer science, and several ideas in biology.