## ۱. مقدمه و تعاریف بنیادی
نظریه گراف (Graph Theory) یکی از کلیدیترین مباحث ریاضیات گسسته است که به مطالعه روابط ساختارمند بین اشیاء میپردازد. هر سیستم پیچیدهای که در آن اجزا به یکدیگر متصل هستند را میتوان با گراف مدلسازی کرد.
تعریف ریاضی:
یک گراف با نماد G نمایش داده میشود و شامل یک زوج مرتب به صورت G = (V, E) است:
– V (Vertices): مجموعه رأسها یا گرهها.
– E (Edges): مجموعه یالها یا خطوطی که رأسها را به هم وصل میکنند.
## ۲. انواع اصلی گرافها
گرافها بر اساس ویژگیهای یالهایشان دستهبندی میشوند:
– گراف ساده (Simple Graph): فاقد طوقه (اتصال راس به خودش) و یالهای موازی است.
– گراف جهتدار (Directed Graph): یالها دارای جهت مشخص (فلش) هستند (مانند جریان ترافیک در خیابانها).
– گراف کامل (Complete Graph): گرافی که در آن هر رأس به تمام رأسهای دیگر متصل است.
– گراف وزندار (Weighted Graph): به هر یال عددی اختصاص داده میشود (مانند فاصله بین دو شهر یا هزینه بیمه).
## ۳. مفاهیم کلیدی و قضایا
یکی از مهمترین مفاهیم، درجه (Degree) یک رأس است که تعداد یالهای متصل به آن را نشان میدهد.
قضیه دست دادن (Handshaking Lemma):
در هر گراف، مجموع درجات تمام رأسها دقیقاً دو برابر تعداد یالهاست. به زبان ریاضی:
Sum of deg(v) = 2 * |E|
این قضیه ثابت میکند که تعداد رأسهایی با درجه فرد در هر گراف، همیشه عددی زوج است.
## ۴. نمایش گراف در حافظه کامپیوتر
برای پردازش گرافها توسط سیستمهای کامپیوتری، از دو ساختار داده اصلی استفاده میشود:
۱. ماتریس مجاورت (Adjacency Matrix): یک جدول دو بعدی که ارتباط بین رأسها را با ۰ و ۱ نشان میدهد.
۲. لیست مجاورت (Adjacency List): برای هر رأس، لیستی از همسایگان آن ذخیره میشود که برای گرافهای بزرگ بسیار بهینهتر است.
## ۵. الگوریتمهای پیمایش (Traversals)
برای جستوجو در دادههای گرافی، دو الگوریتم بنیادین وجود دارد:
– BFS (جستوجوی اول سطح): برای پیدا کردن کوتاهترین مسیر در شبکهها.
– DFS (جستوجوی اول عمق): برای تحلیل ساختارهای تو در تو و تشخیص دور در گراف.
## ۶. نتیجهگیری
نظریه گراف زبان مشترک ریاضیات و تکنولوژی است. درک این مبحث به شما کمک میکند تا مسائل پیچیده را به مدلهای بصری و قابل حل تبدیل کنید.
