کتاب آشنایی با نظریه ی گراف | بی. وست

معرفی کتاب آشنایی با نظریه ی گراف | بی. وست

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

بسیاری از نتایج در نظریه گراف چند اثبات دارند؛ طرح آن‌ها به افزایش انعطاف‌پذیری دانشجویان در امتحان به رهیافتهای چندگانه برای حل یک مساله می‌انجامد.

قضیه توران تنها از پنداره‌های ابتدایی بهره می‌گیرد و بنابراین در فصل 1 مطرح می‌گردد. کاربردی که " لم اسپرنر" را موجب می‌شود، متضمن معلومات پیشرفته است و از این‌رو پیش از فصل 8 مطرح نمی‌شود. درخت‌ها و فاصله‌ها با هم ظاهر می‌شوند ( فصل2)، زیرا نتایج گوناگونی درباره فاصله به درخت‌ها برمی‌گردند و برای اینکه درختها به الگوریتم دیجکسترا و به مدارهای اویلری مربوط می‌شوند. قضیه پترسن برای عامل‌ها ( فصل 3) از مدارهای اویلری و جورسازی دو بخشی بهره می‌گیرد. قضیه منگر پیش از شارش شبکه مطرح می‌شود ( فصل4)، و کاربردهای مجزایی برای شارش شبکه ذکر شده‌اند.

( فصل5) از جورسازی دوبخشی بهره می‌گیرد. بحث اصلی گراف‌های تام در فصل 8 دیده می‌شود. سودهی‌های گراف در بسیاری از تمرینات و مثال‌های  ظاهر می‌شود،  از جمله قضیه گاله- روی و التصاق استانلی میان چند جمله‌ای رنگی و سودهی‌های بیدور( فصل5). اثبات ارائه شده در قضیه وایزینگ برای گراف‌های ساده ( فصل6) الگوریتمی و کوتاه است. اثبات قضیه کوراتوفسکی ( فصل7) از روش تامسن استفاده می‌کند و به صورت یک درس جدی و مناسب خواهد بود.

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

نویسنده: داگلاس بی.وست

• مترجم: دکتر بیژن شمس
• انتشارات: گسترش علوم پایه