مقدمات و مدل سازی با گراف¶

چرا گراف؟¶

گراف یک تعریف انتزاعی است. مثل ۲. در واقعیت چیزی به اسم ۲ وجود ندارد اما مثلا ۲ توپ یا ۲ سیب وجود دارند. توپ و سیب، چیز های پیچیده ای هستند و در مسائل (مثلا مساله ۲ توپ با ۳ توپ می شود چند توپ) این پیچیدگی تاثیر ندارد. پس ما این جزییات بی مصرف را حذف و تمرکزمان را روی قسمت های مهم مساله می گذاریم.

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

انتزاع علاوه بر ساده سازی مسائل، به ما کمک می کند که از راه خود در یک مساله، در مسائل دیگر نیز استفاده کنیم. مثلا وقتی می فهمیم که ۲+۳=۵ دیگر فهم ۲ سیب با سه سیب می شود ۵ سیب یا ۲ گلابی با ۳ گلابی می شود ۵ گلابی برایمان ساده است. یا در مثال شهر ها، اگر بتوانیم مساله را برای مدل انتزاعی "گرافی که روی هر یالش یک عدد زمان نوشته است" حل کنیم، می توانیم از همان راه حل برای مسیریابی بسته ها در یک شبکه کامپیوتری مثل اینترنت استفاده کنیم. در صورتی که اگر بدون رویکرد انتزاعی به مساله نگاه می کردیم ممکن بود به یک راه حل خاص منظوره برسیم (مثلا اگر جاده آسفالت بود از جاده آسفالت برو وگرنه از خاکی برو) این موضوع فایده انتزاع و گراف به عنوان یک تعریف انتزاعی را به ما نشان می دهد.

گراف در کجا ظاهر می شود؟¶

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

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

تعاریف ساده¶

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

راس و یال: در بالا اشاره شد. منظور نقاط و خطوط در گراف هستند.

طوقه: اگر یک راس به خودش یال داشته باشد به آن یال طوقه می گوییم.

یال چندگانه: اگر بین دو راس چند یال وجود داشته باشد به آن یال ها یال چندگانه می گوییم.

گراف ساده: گرافی که طوقه و یال چندگانه نداشته باشد گراف ساده است. ما معمولا با گراف های ساده سر و کله می زنیم پس نگران طوقه و یال چندگانه نباشید.

درجه یک راس: تعداد یال های متصل به یک راس را درجه آن راس می نامیم. به دلایلی، طوقه را دو بار در درجه حساب می کنیم. اگر خود راس را با \(v\) نمایش دهیم درجه آن را با \(d_v\) نمایش می دهیم.

کمترین درجه گراف: کمترین درجه گراف را با حرف یونانی دلتای کوچک نمایش می دهند. اگر تنها یک گراف مورد بحث باشد، به سادگی از \(\delta\) و اگر چند گراف مانند G و H مورد بحث باشند از \(\delta (G)\) و \(\delta (H)\) استفاده می کنیم.

بیشترین درجه گراف: بیشترین درجه گراف را با حرف یونانی دلتای بزرگ نمایش می دهند. اگر تنها یک گراف مورد بحث باشد، به سادگی از \(\Delta\) و اگر چند گراف مانند G و H مورد بحث باشند از \(\Delta (G)\) و \(\Delta (H)\) استفاده می کنیم.

مکمل یک گراف ساده: منظور از مکمل یک گراف، گرافی است که راس های آن همان راس های گراف اصلی هستند اما بین هر دو راسش یال هست اگر و تنها اگر بینشان در گراف اصلی یالی نباشد. طبق تعریف، مکمل مکمل یک گراف، خود آن گراف است. مکمل گراف G را با \(\overline{G}\) نمایش می دهند. در شکل زیر، دو گراف چهار راسی قرمز و آبی مکمل یک دیگر هستند:

جمع تمامی درجات¶

در این قسمت یک قضیه ساده از گراف را با هم اثبات می کنیم. خوب است قبل از خواندن جواب کمی به راه حل آن فکر کنید. قضیه بیان می کند که جمع درجه تمامی رئوس گراف دو برابر تعداد یال هاست یا به عبارتی دیگر \(\sum d_v = 2e\)

برای اثبات این قضیه، تاثیر هر یال را روی جمع درجات تمامی رئوس بررسی می کنیم. یک یال عادی درجه سر و تهش را یک واحد افزایش می دهد و یک طوقه درجه راسش را دو واحد پس هر یال جمع درجات را دقیقا دو واحد اضافه می کند پس جمع درجات دو برابر تعداد یال هاست.