Graphs, Colourings and the Four-colour Theorem

دسته بندی: نظریه نمودار
ویرایش:  
نویسندگان: Wilson R.A.  
سری:  
 
ناشر:  
سال نشر:  
تعداد صفحات: 147 
زبان: English 
فرمت فایل : DJVU (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود) 
حجم فایل: 629 کیلوبایت 

قیمت کتاب (تومان) : 50,000

Издательство انتشارات دانشگاه آکسفورد، 2002، -147 ص. این کتاب برگرفته از یک ماژول سال سوم در نظریه گراف است که در دانشگاه بیرمنگام طی سه سال ارائه شده است. 1996-9، و دوباره در سال 2001. این ماژول به گونه ای طراحی شده است که برای تعداد زیادی از دانش آموزان قابل دسترسی باشد (پیش نیازها حداقل هستند)، اما همچنان برای ارائه مطالب چالش برانگیز. این دوره حول محور "حدس چهار رنگ" معروف است، که هر نقشه را می توان با چهار رنگ رنگ آمیزی کرد، مشروط به این قرارداد معمول که هیچ دو کشور مجاور را نمی توان یکسان رنگ کرد. این مسئله به ظاهر ساده از اولین ظهور خود در فرهنگ عامه ریاضی در دهه 1850 تا حل نهایی آن در دهه 1970، نسل‌های ریاضیدانان حرفه‌ای و آماتور را ناامید کرده است.
کتاب با بحث در مورد رویکردهای اولیه کمپ آغاز می‌شود. و Tait در دهه‌های 1870 و 1880، قبل از اینکه نقص‌های استدلال‌های خود را آشکار کنند، و سپس برخی از روش‌های اصلاح روش‌ها، بدیهی‌سازی مسائل، و تعمیم حدس‌ها را شرح دادند. در این مسیر، ما چندین مورد از بهترین جواهرات موضوع را ارائه می کنیم: محدودیت هیوود برای رنگ آمیزی نقشه روی سطحی با سوراخ، قضیه کوراتوفسکی که مشخص می کند کدام نمودارها (یا نقشه ها) را می توان روی سطحی بدون سوراخ رسم کرد، و قضیه ویزینگ. بر روی حداقل تعداد رنگ های مورد نیاز برای رنگ آمیزی لبه های یک نمودار. بخش پایانی کتاب با هدف ارائه بینشی در مورد روش هایی است که در نهایت مشکل چهار رنگ را حل کردند.
بسیاری از مطالب این کتاب در یک دوره منفرد از حدود 20 سخنرانی پوشش داده شده است، اگرچه برخی از مطالب اضافی نیز شامل برای کامل بودن و تسهیل انتخاب شخصی موضوعات اضافه شده است. اگر دانش‌آموزان قبلاً نمودارها را ملاقات کرده‌اند، می‌توان فصل 2 را تا حد زیادی حذف کرد. اگر هدف این باشد که خود قضیه چهار رنگ را تا حدودی بررسی کنیم، فصل های 7 و 8 تا حدودی مماس هستند و همچنین می توان آنها را حذف کرد. از سوی دیگر، می‌توان با انتخاب ترکیبی وسیع‌تر از موضوعات از همه فصل‌ها، یک دوره عمومی‌تر تئوری گراف ایجاد کرد.
بخش اول. نمودارها، نقشه‌ها و مسئله چهار رنگ.
مقدمه.
نظریه گراف پایه.
کاربردهای فرمول اویلر.
رویکرد کمپه.
بخش دوم. موضوعات مرتبط.
رویکردهای دیگر برای مسئله چهار رنگ.
نقشه بر روی سطوح دارای سوراخ.
قضیه کوراتوفسکی.
رنگ آمیزی نمودارهای غیرمسطح.
بخش سوم. چگونه قضیه چهار رنگ را اثبات کنیم.
نمای کلی.
کاهش پذیری.
تخلیه.

Издательство Oxford University Press, 2002, -147 pp. This book arose out of a third-year module in graph theory given at the University of Birmingham over the three years 1996-9, and again in 2001. This module was designed to be accessible to a large number of students (the prerequisites are minimal), but still to present some challenging material. The course centres around the famous 'four-colour conjecture', that every map can be coloured with four colours, subject to the usual convention that no two adjacent countries may be coloured the same. From its first appearance in mathematical folklore in the 1850s, until its eventual solution in the 1970s, this apparently simple problem has frustrated generations of mathematicians, both professional and amateur.
The book begins with a discussion of the early approaches of Kempe and Tait in the 1870s and 1880s, before revealing the flaws in their arguments, and then describing some of the ways in which the methods were refined, the problems axiomatised, and the conjectures generalized. In the course of this, we present several of the finest gems of the subject: Heawood's bound for map-colouring on a surface with holes, Kuratowski's theorem characterising which graphs (or maps) can be drawn on a surface without holes, and Vizing's theorem on the minimum number of colours needed to colour the edges of a graph. The final part of the book aims to provide some insight into the methods which eventually cracked the four-colour problem.
Much of the material in this book was covered in a single course of about 20 lectures, although some extra material has been added for completeness, and to facilitate a personal selection of topics. If students have met graphs before, then Chapter 2 can be largely omitted. If the aim is to study the four-colour theorem itself in some depth, then Chapters 7 and 8 are somewhat tangential and can also be omitted. On the other hand, a more general graph theory course can be made by picking a somewhat broader mix of topics from all the chapters.
Part I. Graphs, Maps and the Four-colour Problem.
Introduction.
Basic graph theory.
Applications of Euler's formula.
Kempe's approach.
Part II. Related Topics.
Other approaches to the four-colour problem.
Maps on surfaces with holes.
Kuratowski's theorem.
Colouring non-planar graphs.
Part III. How to Prove the Four-colour Theorem.
Overview.
Reductibility.
Discharging.