نگاهی به ریاضیات پیشرفته/نظریه گراف
|
|
در ریاضیات ، نظریه گراف مطالعه نمودارها است ، که ساختارهای ریاضی هستند که برای مدل‌سازی روابط زوجی بین اشیاء استفاده می‌شوند. یک نمودار در این زمینه از رئوس (که گره ها یا نقاط نیز نامیده می شوند ) ساخته شده است که توسط یال ها (که پیوندها یا خطوط نیز نامیده می شوند) به هم متصل می شوند . بین نمودارهای بدون جهت ، که در آن یال ها دو راس را به طور متقارن به هم مرتبط می کنند، و نمودارهای جهت دار ، که در آن یال ها دو راس را به طور نامتقارن به هم مرتبط می کنند، تمایز قائل می شوند. نمودارها یکی از موضوعات اصلی مطالعه در ریاضیات گسسته هستند.
تاریخ
ویرایشبرخلاف شاخه‌های دیگر ریاضیات، سیر نظریهٔ گراف آغاز معینی در زمان و مکان دارد و آن مسئلهٔ هفت پل کونیگسبرگ است که در سال ۱۷۳۶ توسط لئونارد اویلر حل شد. در سال ۱۷۵۲ قضیهٔ اویلر برای گراف‌های مسطح ارائه می‌شود. اما پس از آن به مدت تقریباً یک قرن فعالیت اندکی در این زمینه صورت گرفت.
تعریف
ویرایشتعریف دقیق‌تر گراف به این صورت است، که گراف مجموعه‌ای از رأس‌ها است، که توسط خانواده‌ای از زوج‌های مرتب که همان یال‌ها هستند به هم مربوط (وصل) شده‌اند.
یال‌ها بر دو نوع ساده و جهت دار هستند، که هر کدام در جای خود کاربردهای بسیاری دارد؛ مثلاً اگر صرفاً اتصال دو نقطه -مانند اتصال تهران و زنجان با کمک آزادراه- مد نظر شما باشد، کافیست آن دو شهر را با دو نقطه نمایش داده، و اتوبان مزبور را با یالی ساده نمایش دهید. اما اگر بین دو شهر جاده‌ای یکطرفه وجود داشته باشد آنگاه لازمست تا شما با قرار دادن یالی جهت دار مسیر حرکت را در آن جاده مشخص کنید. همچنین برای اینکه فاصله بین دو شهر را در گراف نشان دهید، می‌توانید از گراف وزن دار استفاده کنید و مسافت بین شهرها را با یک عدد بر روی هر یال نشان دهید.
آغاز نظریهٔ گراف به سدهٔ هجدهم بر می‌گردد. لئونارد اویلر ریاضیدان بزرگ مفهوم گراف را برای حل مسئله پل‌های کونیگسبرگ ابداع کرد اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سدهٔ اخیر و با رشد علم انفورماتیک بوده‌است.
مهم‌ترین کاربرد گراف مدل‌سازی پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد یا الگوریتمهای مناسب مانند الگوریتم دایکسترا یا الگوریتم کروسکال و… را بر روی آن اعمال نمود.
یکی از قسمت‌های پرکاربرد نظریهٔ گراف، گراف مسطح است که به بررسی گراف‌هایی می‌پردازد که می‌توان آنها را به نحوی روی صفحه کشید که یال‌ها جز در محل رأس‌ها یکدیگر را قطع نکنند. این نوع گراف در ساخت جاده‌ها و حل مسئله کلاسیک و قدیمی سه خانه و سه چاه آب به کار می‌رود.
نظریه گراف یکی از پرکاربردترین نظریه‌ها در شاخه‌های مختلف علوم مهندسی (مانند عمران)، باستان‌شناسی (کشف محدوده یک تمدن) و… است.
روابط میان رأس‌های یک گراف را می‌توان با کمک ماتریس بیان کرد.
برای نمایش تصویری گراف‌ها معمولاً از نقطه یا دایره برای کشیدن رأس‌ها و از کمان یا خط راست برای کشیدن یال بین رأس‌ها استفاده می‌شود.
کاربرد
ویرایشنمودارها را می‌توان برای مدل‌سازی بسیاری از انواع روابط و فرآیندها در سیستم‌های فیزیکی، بیولوژیکی،اجتماعی و اطلاعاتی استفاده کرد.بسیاری از مسائل عملی را می توان با نمودار نشان داد. با تأکید بر کاربرد آنها در سیستم های دنیای واقعی، اصطلاح شبکه گاهی اوقات به معنای نموداری تعریف می شود که در آن ویژگی ها (مثلاً نام ها) با رئوس و یال ها مرتبط هستند و موضوعی که سیستم های دنیای واقعی را به عنوان یک علم شبکه بیان و درک می کند نامیده می شود.
علوم کامپیوتر
ویرایشدر علم کامپیوتر ، سایبرنتیک از نمودارها برای نمایش شبکه های ارتباطی، سازماندهی داده ها، دستگاه های محاسباتی، جریان محاسبات و غیره استفاده می کند. به عنوان مثال، ساختار پیوند یک وب سایت را می توان با یک نمودار جهت دار نشان داد که در آن رئوس نشان دهنده صفحات وب است. و لبه های جهت دار نشان دهنده پیوندها از یک صفحه به صفحه دیگر است. رویکرد مشابهی را می توان برای مشکلات در رسانه های اجتماعی، سفر، زیست شناسی، طراحی تراشه های کامپیوتری، نقشه برداری از پیشرفت بیماری های عصبی، و بسیاری از زمینه های دیگر اتخاذ کرد. بنابراین توسعه الگوریتم‌هایی برای مدیریت نمودارها از علاقه‌مندی عمده در علوم کامپیوتر است. راتبدیل نمودارها اغلب رسمی و با سیستم های بازنویسی نمودار نشان داده می شود . مکمل سیستم‌های تبدیل گراف که بر روی دستکاری در حافظه مبتنی بر قانون گراف‌ها تمرکز می‌کنند، پایگاه‌های اطلاعاتی گراف هستند که برای ذخیره‌سازی پایدار ، ذخیره‌سازی پایدار و پرس‌وجو از داده‌های ساختار یافته گراف طراحی شده‌اند.
ریاضیات
ویرایشدر ریاضیات، نمودارها در هندسه و بخش های خاصی از توپولوژی مانند نظریه گره مفید هستند . نظریه گراف جبری پیوند نزدیکی با نظریه گروه دارد . نظریه گراف جبری در بسیاری از زمینه ها از جمله سیستم های پویا و پیچیدگی به کار گرفته شده است.
فیزیک و شیمی
ویرایشتئوری گراف همچنین برای مطالعه مولکول ها در شیمی و فیزیک استفاده می شود. در فیزیک ماده چگال ، ساختار سه بعدی ساختارهای اتمی شبیه‌سازی شده پیچیده را می‌توان با جمع‌آوری آماری در مورد ویژگی‌های نظری گراف مرتبط با توپولوژی اتم‌ها به صورت کمی مطالعه کرد. همچنین، « نمودارهای فاینمن و قواعد محاسباتی ، نظریه میدان کوانتومی را به شکلی در ارتباط نزدیک با اعداد تجربی که می‌خواهیم بفهمیم، خلاصه می‌کنند». در شیمی، یک نمودار یک مدل طبیعی برای یک مولکول می سازد، که در آن رئوس نشان دهنده اتم ها و پیوندهای لبه است.. این رویکرد به ویژه در پردازش کامپیوتری ساختارهای مولکولی، از ویرایشگرهای شیمیایی تا جستجو در پایگاه داده استفاده می شود. در فیزیک آماری ، نمودارها می توانند ارتباطات محلی بین بخش های متقابل یک سیستم و همچنین پویایی یک فرآیند فیزیکی در چنین سیستم هایی را نشان دهند. به طور مشابه، در علوم اعصاب محاسباتیاز نمودارها می توان برای نشان دادن ارتباطات عملکردی بین نواحی مغز استفاده کرد که با یکدیگر تعامل دارند و فرآیندهای شناختی مختلفی را ایجاد می کنند، جایی که رئوس نشان دهنده مناطق مختلف مغز و لبه ها نشان دهنده ارتباطات بین آن مناطق هستند. تئوری نمودار نقش مهمی در مدل‌سازی الکتریکی شبکه‌های الکتریکی ایفا می‌کند، در اینجا وزن‌ها با مقاومت قطعات سیم برای به دست آوردن خواص الکتریکی سازه‌های شبکه مرتبط می‌شوند. نمودارها همچنین برای نشان دادن کانال‌های میکرو مقیاس محیط متخلخل استفاده می‌شوند که در آن رئوس نشان‌دهنده منافذ و لبه‌ها کانال‌های کوچک‌تر را نشان می‌دهند که منافذ را به هم متصل می‌کنند. نظریه گراف شیمیایی از گراف مولکولی استفاده می کندبه عنوان وسیله ای برای مدل سازی مولکول ها. نمودارها و شبکه ها مدل های عالی برای مطالعه و درک انتقال فاز و پدیده های بحرانی هستند. حذف گره ها یا لبه ها منجر به یک انتقال بحرانی می شود که در آن شبکه به خوشه های کوچک تقسیم می شود که به عنوان یک انتقال فاز مورد مطالعه قرار می گیرد. این تفکیک از طریق تئوری نفوذ بررسی می شود .