نظریه گراف
نظریه گراف
نظریه گراف شاخهای از ریاضیات است که دربارهٔ گراف ها بحث میکند. به صورت شهودی، گراف نموداری است، شامل تعدادی رأس، که با یالهایی به هم وصل شدهاند.
تعریف
تعریف دقیقتر گراف به این صورت است، که گراف مجموعهای از رأسها است، که توسط خانوادهای از زوجهای مرتب که همان یالها هستند به هم مربوط شدهاند.
یالها بر دو نوع ساده و جهت دار هستند، که هر کدام در جای خود کاربردهای بسیاری دارد. مثلاً اگر صرفاً اتصال دو نقطه -مانند اتصال تهران و زنجان با کمک آزادراه- مد نظر شما باشد، کافیست آن دو شهر را با دو نقطه نمایش داده، و اتوبان مزبور را با یالی ساده نمایش دهید. اما اگر بین دو شهر جادهای یکطرفه وجود داشته باشد آنگاه لازمست تا شما با قرار دادن یالی جهت دار مسیر حرکت را در آن جاده مشخص کنید.
آغاز نظریهٔ گراف به سدهٔ هجدهم بر میگردد. اولر ریاضیدان بزرگ مفهوم گراف را برای حل مسئله پلهای کونیگسبرگ ابداع کرد اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سدهٔ اخیر و با رشد علم انفورماتیک بودهاست.
مهمترین کاربرد گراف، مدلسازی پدیدههای گوناگون و بررسی بر روی آنهاست. با گراف میتوان به راحتی یک نقشه بسیار بزرگ یا شبکهای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد و یا الگوریتمهای مناسب مانند الگوریتم دایسترا یا الگوریتم کروسکال و ... را بر روی آن اعمال نمود.
یکی از قسمتهای پرکاربرد نظریهٔ گراف، گراف مسطح است که به بررسی گرافهایی میپردازد که میتوان آنها را به نحوی روی صفحه کشید که یالها جز در محل راسها یکدیگر را قطع نکنند. این نوع گراف در ساخت جادهها و حل مساله کلاسیک و قدیمی سه خانه و سه چاه آب به کار میرود.
نظریه گراف یکی از پرکاربردترین نظریهها در شاخههای مختلف علوم مهندسی (مانند عمران)، باستانشناسی (کشف محدوده یک تمدن) و ... است.
روابط میان راس های یک گراف را میتوان با کمک ماتریس بیان کرد .
انواع گراف
گراف ساده: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعهای متناهی و ناتهی است و E زیرمجموعهای از تمام زیرمجموعههای دو عضوی V میباشد. اعضای V را رأسهای G و اعضای E را یالهای G مینامیم. به بیان ساده تر بین دو رأس یک گراف ساده حداکثر یک یال وجود دارد.
گراف چندگانه: هرگاه بین دو رأس متمایز از یک گراف بیش از یک یال وجود داشته باشد، آن را یک گراف چند گانه میگوییم.
گراف جهت دار: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعهای متناهی و ناتهی است و E زیرمجموعهای از مجموعهٔ تمام زوج مرتبهای متشکل از اعضای V است.
گراف مسطح: گراف مسطح گرافی است که میتوان آن را در یک صفحه محاط کرد به گونه ای که یال هایش یکدیگر را تنها در راس ها قطع کنند.
نظریه گراف شاخهای از ریاضیات است که دربارهٔ گراف ها بحث میکند. به صورت شهودی، گراف نموداری است، شامل تعدادی رأس، که با یالهایی به هم وصل شدهاند.
نمایش تصویری یک گراف
تعریف
تعریف دقیقتر گراف به این صورت است، که گراف مجموعهای از رأسها است، که توسط خانوادهای از زوجهای مرتب که همان یالها هستند به هم مربوط شدهاند.
یالها بر دو نوع ساده و جهت دار هستند، که هر کدام در جای خود کاربردهای بسیاری دارد. مثلاً اگر صرفاً اتصال دو نقطه -مانند اتصال تهران و زنجان با کمک آزادراه- مد نظر شما باشد، کافیست آن دو شهر را با دو نقطه نمایش داده، و اتوبان مزبور را با یالی ساده نمایش دهید. اما اگر بین دو شهر جادهای یکطرفه وجود داشته باشد آنگاه لازمست تا شما با قرار دادن یالی جهت دار مسیر حرکت را در آن جاده مشخص کنید.
آغاز نظریهٔ گراف به سدهٔ هجدهم بر میگردد. اولر ریاضیدان بزرگ مفهوم گراف را برای حل مسئله پلهای کونیگسبرگ ابداع کرد اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سدهٔ اخیر و با رشد علم انفورماتیک بودهاست.
مهمترین کاربرد گراف، مدلسازی پدیدههای گوناگون و بررسی بر روی آنهاست. با گراف میتوان به راحتی یک نقشه بسیار بزرگ یا شبکهای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد و یا الگوریتمهای مناسب مانند الگوریتم دایسترا یا الگوریتم کروسکال و ... را بر روی آن اعمال نمود.
یکی از قسمتهای پرکاربرد نظریهٔ گراف، گراف مسطح است که به بررسی گرافهایی میپردازد که میتوان آنها را به نحوی روی صفحه کشید که یالها جز در محل راسها یکدیگر را قطع نکنند. این نوع گراف در ساخت جادهها و حل مساله کلاسیک و قدیمی سه خانه و سه چاه آب به کار میرود.
نظریه گراف یکی از پرکاربردترین نظریهها در شاخههای مختلف علوم مهندسی (مانند عمران)، باستانشناسی (کشف محدوده یک تمدن) و ... است.
روابط میان راس های یک گراف را میتوان با کمک ماتریس بیان کرد .
انواع گراف
گراف ساده: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعهای متناهی و ناتهی است و E زیرمجموعهای از تمام زیرمجموعههای دو عضوی V میباشد. اعضای V را رأسهای G و اعضای E را یالهای G مینامیم. به بیان ساده تر بین دو رأس یک گراف ساده حداکثر یک یال وجود دارد.
گراف چندگانه: هرگاه بین دو رأس متمایز از یک گراف بیش از یک یال وجود داشته باشد، آن را یک گراف چند گانه میگوییم.
گراف جهت دار: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعهای متناهی و ناتهی است و E زیرمجموعهای از مجموعهٔ تمام زوج مرتبهای متشکل از اعضای V است.
گراف مسطح: گراف مسطح گرافی است که میتوان آن را در یک صفحه محاط کرد به گونه ای که یال هایش یکدیگر را تنها در راس ها قطع کنند.
+ نوشته شده در دوشنبه بیست و چهارم آبان ۱۳۸۹ ساعت توسط بهزادی
|
این وبلاگ برای برقراری ارتباط با همه ی علاقمندان ریاضی ساخته شده است، لیسانس ریاضی خودمو از دانشگاه فرهنگیان اهواز گرفتم و در حال حاضر دانشجوی ارشد ریاضی روزانه گرایش انالیز از دانشگاه شهرکرد هستم، ایمیل من