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