Graphs, Dioids and Semirings: New Models and Algorithms

منشا نظریه گراف به اویلر (1736) با حل مسئله مشهور "مسئله پل های کونیگزبرگ" برمی گردد. و به همیلتون با بازی معروف «سفر به دور دنیا» (1859)، برای اولین بار مشکلی را بیان کرد که در جدیدترین نسخه آن - «مشکل فروشنده مسافر» - هنوز موضوع تحقیقات فعال است. با این حال، در حدود پنجاه سال گذشته - با ظهور رایانه های الکترونیکی - است که نظریه گراف از نظر تعداد و اهمیت کاربردهای آن در سراسر علوم کاربردی به یک رشته ضروری تبدیل شده است. نظریه گراف به ویژه در علوم کامپیوتر نظری و الگوریتمی، و کنترل خودکار، بهینه‌سازی سیستم‌ها، اقتصاد و تحقیقات عملیاتی، تجزیه و تحلیل داده‌ها در علوم مهندسی نقش محوری داشته است. ارتباط نزدیک بین نمودارها و ساختارهای جبری به طور گسترده در تحلیل و اجرای الگوریتم های کارآمد برای بسیاری از مسائل استفاده شده است، به عنوان مثال: بهینه سازی شبکه حمل و نقل، بهینه سازی و برنامه ریزی شبکه مخابراتی، بهینه سازی در سیستم های برنامه ریزی و تولید و غیره.

هدف اصلی گراف‌ها، دیویدها و نیمه‌ها: مدل‌ها و الگوریتم‌های جدید تأکید بر روابط عمیق موجود بین ساختارهای نیمه‌شکل و دیوید با نمودارها و ویژگی‌های ترکیبی آن‌ها است. ضمن نشان دادن قابلیت مدل سازی و حل مسئله و انعطاف پذیری این ساختارها. علاوه بر این، این کتاب یک نمای کلی از ویژگی‌های ریاضی به کار رفته توسط ساختارهای جبری «غیر کلاسیک» ارائه می‌کند، که یا جبر معمولی را گسترش می‌دهند (یعنی نیمه‌ریزی‌ها)، یا با شاخه جدیدی از جبر (یعنی دیویدها)، جدای از ساختارهای کلاسیک گروه ها، حلقه ها و میدان ها.

The origins of Graph Theory date back to Euler (1736) with the solution of the celebrated 'Koenigsberg Bridges Problem'; and to Hamilton with the famous 'Trip around the World' game (1859), stating for the first time a problem which, in its most recent version – the 'Traveling Salesman Problem' -, is still the subject of active research. Yet, it has been during the last fifty years or so—with the rise of the electronic computers—that Graph theory has become an indispensable discipline in terms of the number and importance of its applications across the Applied Sciences. Graph theory has been especially central to Theoretical and Algorithmic Computer Science, and Automatic Control, Systems Optimization, Economy and Operations Research, Data Analysis in the Engineering Sciences. Close connections between graphs and algebraic structures have been widely used in the analysis and implementation of efficient algorithms for many problems, for example: transportation network optimization, telecommunication network optimization and planning, optimization in scheduling and production systems, etc.

The primary objectives of GRAPHS, DIOÏDS AND SEMIRINGS: New Models and Algorithms are to emphasize the deep relations existing between the semiring and dioïd structures with graphs and their combinatorial properties, while demonstrating the modeling and problem-solving capability and flexibility of these structures. In addition the book provides an extensive overview of the mathematical properties employed by "nonclassical" algebraic structures, which either extend usual algebra (i.e., semirings), or correspond to a new branch of algebra (i.e., dioïds), apart from the classical structures of groups, rings, and fields.