گراف ساده: گرافی بدون طوقه و یال تکراری

گراف ساده: بنیاد ساختارهای گسسته در ریاضیات و علوم کامپیوتر

۱. تعریف دقیق گراف ساده و اجزای آن

یک گراف ساده¹ از دو بخش اصلی تشکیل شده است: مجموعه‌ای از رأس‌ها² (نقاط یا گره‌ها) و مجموعه‌ای از یال‌ها³ (اتصال‌دهنده‌های بین رأس‌ها). شرط اصلی برای ساده بودن گراف این است که هیچ طوقه⁴ (یالی که یک رأس را به خودش وصل کند) وجود نداشته باشد و همچنین بین هر دو رأس حداکثر یک یال مستقیم وجود داشته باشد. به بیان ریاضی، اگر مجموعه رأس‌ها را با $V$ و مجموعه یال‌ها را با $E$ نشان دهیم، آنگاه هر یال $e \in E$ یک زوج نامرتب از دو رأس متمایز است، یعنی $e = \{u,v\}$ که در آن $u \neq v$ و $u,v \in V$.

برای مثال، فرض کنید $V = \{1,2,3\}$ و $E = \{\{1,2\}, \{2,3\}\}$. این یک گراف ساده است زیرا رأس 1 به خودش وصل نیست و بین 1 و 2 فقط یک یال وجود دارد. حال اگر E شامل \{1,1\} باشد، آن طوقه محسوب می‌شود و گراف دیگر ساده نیست. همچنین اگر دو یال \{1,2\} و \{1,2\} تکراری داشته باشیم، آن را چندالی⁵ می‌نامیم که در گراف ساده مجاز نیست.

۲. انواع گراف‌های ساده بر اساس ساختار

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

۳. درجه رأس و قضیه دست دادن

یکی از مفاهیم کلیدی در گراف‌های ساده، درجه¹⁰ یک رأس است که برابر است با تعداد یال‌های متصل به آن رأس. در گراف ساده، درجه هر رأس حداکثر می‌تواند $n-1$ باشد که $n$ تعداد رأس‌هاست. یک قضیه مهم به نام قضیه دست دادن¹¹ می‌گوید: مجموع درجات همه رأس‌های یک گراف همواره برابر با دو برابر تعداد یال‌ها است.

به عنوان مثال، در یک مهمانی با 10 نفر که هر فرد با چند نفر دیگر دست می‌دهد، تعداد کل دست دادن‌ها (هر دست دادن دو نفر را درگیر می‌کند) همیشه زوج است. همچنین در هر گراف ساده، تعداد رأس‌هایی که درجه فرد دارند، حتماً زوج است. این نتیجه‌گیری ساده اما قدرتمند است.

۴. کاربرد عملی: مدل‌سازی شبکه دوستی در یک کلاس

فرض کنید در یک کلاس 6 نفره (رأس‌ها: الف، ب، پ، ت، ث، ج) می‌خواهیم روابط دوستی (یال) را مدل کنیم. اگر دوستی بین الف و ب، ب و پ، پ و ت، ت و ث، و ث و ج وجود داشته باشد و هیچ دوستی تکراری یا طوقه‌ای نباشد، این یک گراف ساده از نوع مسیر با $6$ رأس و $5$ یال است. درجه رأس‌های میانی برابر 2 و رأس‌های انتهایی برابر 1 است. با استفاده از قضیه دست دادن، مجموع درجات = 1+2+2+2+2+1 = 10 و دو برابر یال‌ها ($2 \times 5 = 10$) است. این مثال نشان می‌دهد چگونه یک موقعیت روزمره را می‌توان به گراف ساده تبدیل کرد.

۵. چالش‌های مفهومی

۶. جمع‌بندی

۷. پاورقی

¹ گراف ساده (Simple Graph): گرافی بدون طوقه و بدون یال تکراری که در آن هر یال دو رأس متمایز را وصل می‌کند.

² رأس (Vertex): یکی از نقاط یا گره‌های اصلی در گراف که می‌تواند با یال به سایر رأس‌ها متصل شود.

³ یال (Edge): اتصال بین دو رأس در گراف که نشان‌دهنده رابطه یا پیوند است.

⁴ طوقه (Loop): یالی که یک رأس را به خودش متصل می‌کند و در گراف ساده مجاز نیست.

⁵ چندالی (Multiple Edge یا Parallel Edge): وجود بیش از یک یال میان یک زوج رأس مشخص.

⁶ گراف کامل (Complete Graph): گرافی ساده که در آن هر دو رأس متمایز مستقیماً با یک یال به هم وصل شده‌اند و با $K_n$ نمایش داده می‌شود.

⁷ گراف تهی (Empty Graph یا Null Graph): گرافی ساده با حداقل یک رأس و بدون هیچ یالی.

⁸ گراف دوبخشی (Bipartite Graph): گرافی ساده که مجموعه رأس‌های آن به دو بخش مجزا افراز می‌شود و هر یال یک رأس از بخش اول را به بخش دوم متصل می‌کند.

⁹ گراف مسیر (Path Graph): گرافی ساده که رأس‌های آن را می‌توان به صورت یک دنباله خطی مرتب کرد به طوری که یال‌ها فقط بین رأس‌های مجاور در این دنباله باشند.

¹⁰ درجه (Degree): تعداد یال‌های وارد شده به یک رأس. در گراف ساده بدون طوقه، درجه هر رأس برابر تعداد همسایه‌های آن است.

¹¹ قضیه دست دادن (Handshaking Lemma): قضیه‌ای که می‌گوید مجموع درجات تمام رأس‌های هر گراف برابر دو برابر تعداد یال‌هاست.

¹² چندگراف (Multigraph): نوعی گراف که مجاز به داشتن یال‌های تکراری (چندالی) است، اما ممکن است طوقه نداشته باشد یا داشته باشد.