نظریه گراف

از ویکی‌پدیا، دانشنامهٔ آزاد.

نمایش تصویری یک گراف
بزرگ شود
نمایش تصویری یک گراف

نظریه گراف دانشی است که درباره موجوداتی به نام گراف بحث می‌کند. به صورت مرئی گراف «چیزی» است شامل تعدادی رأس که با یالهایی به هم وصل شده‌اند. تعریف دقیق‌تر نظریهٔ گراف به این صورت است که گراف مجموعه‌ای از رأس‌ها است که توسط خانواده‌ای از زوج‌های مرتب که همان یال‌ها هستند به هم ربط داده شده‌اند.

آغاز نظریهٔ گراف به سدهٔ هجدهم بر می‌گردد. اویلر ریاضیدان بزرگ مفهوم گراف را برای حل مسئله پل‌های کونیگزبرگ ابداع کرد اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سدهٔ اخیر و با رشد علم داده‌ورزی (انفورماتیک) بوده است.

مهم‌ترین کاربرد گراف مدل‌سازی پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک ماتریس ذخیره کرد و یا الگوریتمهای‌ مناسب را بر روی آن اعمال نمود.

یکی از قسمت‌های پركاربرد نظریهٔ گراف، گراف‌های مسطح است که به بررسی گراف‌هایی می‌پردازد كه می‌توان آن‌ها را به‌طوری روی صفحه كشید (با گذاشتن نقطه برای رأس‌ها و گذاشتن خم‌هایی كه اين نقاط را به هم وصل می‌كنند به جای یال‌ها) كه یال‌ها یكدیگر را قطع نكنند.

[ویرایش] مطالعهٔ بیشتر


این نوشتار در زمینهٔ ریاضیات ناقص است. با گسترش آن به ویکی‌پدیا کمک کنید.