"نظریه ی گراف "
مساله اين بود كه شخصي از هر يك از نواحي A ، B ، Cو يا D حركت كند و از هر يك از پل ها يك بار و فقط يك بار بگذزرد و به نقطه شروع بازگردد. اهالي شهر در هنگام گردش وپياده روي مي كوشيدند مساله را عملا حل كنند. ولي كوشش آن ها بي نتيجه مي ماند. تا اين كه اويلر با باداع نظريه اي كه در آن هندسه بدون اندازه ناميد توانست حل ناپذيري آن را ثابت كند. اويلر ابتدا مدلي رياضي براي مساله درست كرد : به هر يك از جزيره ها و ساحل ها يك نقطه نسبت داد و دو نقطه متناظر با دو ناحيه اي را كه با پلي مرتبط بودند با پاره خط يا كماني به هم وصل كرد."
با اين كار اويلر يك گراف به دست آورد.اويلر در مقاله بسيار كوتاهي با استدلالي ساده عبث بودن كوشش ها را ثابت كرد. لازم به ذكر است كه هر چند ريشه هاي نظريه گراف ها به اواسط قرن هجدهم ميلادي برمي گردد ولي شناخت زيبايي و كارايي در زمينه هاي نظري و علمي تا نيمه قرن بيستم ميلادي به
درازا کشید .
.
لئونارد اويلر :
لئونارد اويلر كه او را بنيانگذار نظريه ي گراف ها يا به عبارت ديگر نظريه ي هندسه ي بدون اندازه (توپولوژي) مي داننداز رياضيدانان بزرگ قرن هجدهم ميلادي و در واقع از رياضيدانان يزرگ همه ي اعصار است.اويلر در سال 1707 در شهر بازل در سوئيس متولد شد و چون استعداد رياضي فوق العاده اي از خود نشان داد موفق به تحصيل رياضيات در مكتب رياضيدانان مشهور عصر خود شد. در 20 سالگي به روسيه مهاجرت كرد و در فرهنگستان پترزبورگ مشغول كار و تحقيق شد. پس از چندين سال برلين را به عنوان محل اقامت خود برگزيد ولي هم چنان عضو فرهنگستان علوم پترزبورگ باقي ماند. اويلر در دوران عمر خود صد ها مقاله ي رياضي منتشر كرد و در زمينه هاي مختلف رياضيات تاثير بنيادي گذاشت. اويلر در سال 1783 در گذشت
نظریه گراف:
تعریف:
فرض کنید V یک مجموعه ناتهی و E زیرمجموعهای از باشد در این صورت زوج را یک گراف می نامند.V را مجموعه راس ها و E را مجموعه یال ها می گویند. اگر ترتیب قرار گرفتن راس ها در مجموعه E مهم باشد،گراف را گراف جهتدار می گویند و یال از راس به سمت راس را به صورت نشان میدهند.در غیر این صورت گراف را بدون جهت مینامند و یال بین راس های و با نماد نشان میدهند.
تعداد راس های یک گراف را مرتبه و تعداد یال های آن را اندازه گراف می نامیم.
در شکل روبرو گرافی را با شش راس و هفت یال مشاهده می کنیم
شاخه ای از ریاضیات است که درباره اشیاء خاصی در ریاضی به نام گراف بحث میکند. به صورت شهودی گراف نمودار یا دیاگرامی است شامل تعدادی رأس که با یالهایی به هم وصل شدهاند. تعریف دقیقتر گراف به این صورت است که گراف مجموعهای از رأسها است که توسط خانوادهای از زوجهای مرتب که همان یالها هستند به هم مربوط شدهاند.
یالها بر دو نوع ساده و جهت دار هستند که هر کدام در جای خود کاربردهای بسیاری دارد. مثلا اگر صرفا اتصال دو نقطه -مانند اتصال تهران و زنجان با کمک آزادراه- مد نظر شما باشد کافیست آن دو شهر را با دو نقطه نمایش داده و اتوبان مزبور را با یالی ساده نمایش دهید. اما اگر بین دو شهر جاده ای یکطرفه وجود داشته باشد آنگاه لازمست تا شما با قرار دادن یالی جهت دار مسیر حرکت را در آن جاده مشخص کنید.
آغاز نظریهٔ گراف به سدهٔ هجدهم بر میگردد. اویلر ریاضیدان بزرگ مفهوم گراف را برای حل مسئله پلهای کونیگسبرگ ابداع کرد اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سدهٔ اخیر و با رشد علم دادهورزی (انفورماتیک) بوده است.
مهمترین کاربرد گراف مدلسازی پدیدههای گوناگون و بررسی بر روی آنهاست. با گراف میتوان به راحتی یک نقشه بسیار بزرگ یا شبکهای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد و یا الگوریتمهای مناسب مانند الگوریتم دایسترا یا الگوریتم کروسکال و ... را بر روی آن اعمال نمود.
یکی از قسمتهای پركاربرد نظریهٔ گراف، گرافهای مسطح یا هامنی است که به بررسی گرافهایی میپردازد كه میتوان آنها را به نحوی روی صفحه كشید كه یالها جز در محل راس ها یكدیگر را قطع نكنند. این نوع گراف در ساخت جاده ها و حل مساله کلاسیک و قدیمی سه خانه و سه چاه آب به کار می رود.
نظریه گراف یکی از پرکاربردترین نظریه ها در شاخه های مختلف علوم مهندسی (مانند عمران),باستانشناسی(کشف محدوده یک تمدن) و.. است!
انواع گراف:
گراف ساده: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه ای متناهی و ناتهی است و E زیرمجموعه ای از تمام زیرمجموعه های دو عضوی V میباشد. اعضای V را رأسهای G و اعضای E را یالهای G مینامیم. به بیان ساده تر بین دو رأس یک گراف ساده حداکثر یک یال وجود دارد.
گراف چندگانه: هرگاه بین دو رأس متمایز از یک گراف بیش از یک یال وجود داشته باشد، آن را یک گراف چند گانه می گوییم.
گراف جهت دار: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه ای متناهی و ناتهی است و E زیرمجموعه ای از مجموعه ی تمام زوج مرتب های متشکل از اعضای V است.
گراف کامل:در نظریه گراف ،یک گراف کامل ،گرافی است که هر بین هر دو راس آن دقیقا یک یال وجود داشته باشد
· یک گراف کامل از مرتبه n،دارای n راس و یال است و آن را با نشان میدهند.
· یک گراف کامل یک گراف منتظم از درجه n-1 است.
مساله اين بود كه شخصي از هر يك از نواحي A ، B ، Cو يا D حركت كند و از هر يك از پل ها يك بار و فقط يك بار بگذزرد و به نقطه شروع بازگردد. اهالي شهر در هنگام گردش وپياده روي مي كوشيدند مساله را عملا حل كنند. ولي كوشش آن ها بي نتيجه مي ماند. تا اين كه اويلر با باداع نظريه اي كه در آن هندسه بدون اندازه ناميد توانست حل ناپذيري آن را ثابت كند. اويلر ابتدا مدلي رياضي براي مساله درست كرد : به هر يك از جزيره ها و ساحل ها يك نقطه نسبت داد و دو نقطه متناظر با دو ناحيه اي را كه با پلي مرتبط بودند با پاره خط يا كماني به هم وصل كرد."
با اين كار اويلر يك گراف به دست آورد.اويلر در مقاله بسيار كوتاهي با استدلالي ساده عبث بودن كوشش ها را ثابت كرد. لازم به ذكر است كه هر چند ريشه هاي نظريه گراف ها به اواسط قرن هجدهم ميلادي برمي گردد ولي شناخت زيبايي و كارايي در زمينه هاي نظري و علمي تا نيمه قرن بيستم ميلادي به
درازا کشید .
.
لئونارد اويلر :
لئونارد اويلر كه او را بنيانگذار نظريه ي گراف ها يا به عبارت ديگر نظريه ي هندسه ي بدون اندازه (توپولوژي) مي داننداز رياضيدانان بزرگ قرن هجدهم ميلادي و در واقع از رياضيدانان يزرگ همه ي اعصار است.اويلر در سال 1707 در شهر بازل در سوئيس متولد شد و چون استعداد رياضي فوق العاده اي از خود نشان داد موفق به تحصيل رياضيات در مكتب رياضيدانان مشهور عصر خود شد. در 20 سالگي به روسيه مهاجرت كرد و در فرهنگستان پترزبورگ مشغول كار و تحقيق شد. پس از چندين سال برلين را به عنوان محل اقامت خود برگزيد ولي هم چنان عضو فرهنگستان علوم پترزبورگ باقي ماند. اويلر در دوران عمر خود صد ها مقاله ي رياضي منتشر كرد و در زمينه هاي مختلف رياضيات تاثير بنيادي گذاشت. اويلر در سال 1783 در گذشت
نظریه گراف:
تعریف:
فرض کنید V یک مجموعه ناتهی و E زیرمجموعهای از باشد در این صورت زوج را یک گراف می نامند.V را مجموعه راس ها و E را مجموعه یال ها می گویند. اگر ترتیب قرار گرفتن راس ها در مجموعه E مهم باشد،گراف را گراف جهتدار می گویند و یال از راس به سمت راس را به صورت نشان میدهند.در غیر این صورت گراف را بدون جهت مینامند و یال بین راس های و با نماد نشان میدهند.
تعداد راس های یک گراف را مرتبه و تعداد یال های آن را اندازه گراف می نامیم.
در شکل روبرو گرافی را با شش راس و هفت یال مشاهده می کنیم
شاخه ای از ریاضیات است که درباره اشیاء خاصی در ریاضی به نام گراف بحث میکند. به صورت شهودی گراف نمودار یا دیاگرامی است شامل تعدادی رأس که با یالهایی به هم وصل شدهاند. تعریف دقیقتر گراف به این صورت است که گراف مجموعهای از رأسها است که توسط خانوادهای از زوجهای مرتب که همان یالها هستند به هم مربوط شدهاند.
یالها بر دو نوع ساده و جهت دار هستند که هر کدام در جای خود کاربردهای بسیاری دارد. مثلا اگر صرفا اتصال دو نقطه -مانند اتصال تهران و زنجان با کمک آزادراه- مد نظر شما باشد کافیست آن دو شهر را با دو نقطه نمایش داده و اتوبان مزبور را با یالی ساده نمایش دهید. اما اگر بین دو شهر جاده ای یکطرفه وجود داشته باشد آنگاه لازمست تا شما با قرار دادن یالی جهت دار مسیر حرکت را در آن جاده مشخص کنید.
آغاز نظریهٔ گراف به سدهٔ هجدهم بر میگردد. اویلر ریاضیدان بزرگ مفهوم گراف را برای حل مسئله پلهای کونیگسبرگ ابداع کرد اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سدهٔ اخیر و با رشد علم دادهورزی (انفورماتیک) بوده است.
مهمترین کاربرد گراف مدلسازی پدیدههای گوناگون و بررسی بر روی آنهاست. با گراف میتوان به راحتی یک نقشه بسیار بزرگ یا شبکهای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد و یا الگوریتمهای مناسب مانند الگوریتم دایسترا یا الگوریتم کروسکال و ... را بر روی آن اعمال نمود.
یکی از قسمتهای پركاربرد نظریهٔ گراف، گرافهای مسطح یا هامنی است که به بررسی گرافهایی میپردازد كه میتوان آنها را به نحوی روی صفحه كشید كه یالها جز در محل راس ها یكدیگر را قطع نكنند. این نوع گراف در ساخت جاده ها و حل مساله کلاسیک و قدیمی سه خانه و سه چاه آب به کار می رود.
نظریه گراف یکی از پرکاربردترین نظریه ها در شاخه های مختلف علوم مهندسی (مانند عمران),باستانشناسی(کشف محدوده یک تمدن) و.. است!
انواع گراف:
گراف ساده: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه ای متناهی و ناتهی است و E زیرمجموعه ای از تمام زیرمجموعه های دو عضوی V میباشد. اعضای V را رأسهای G و اعضای E را یالهای G مینامیم. به بیان ساده تر بین دو رأس یک گراف ساده حداکثر یک یال وجود دارد.
گراف چندگانه: هرگاه بین دو رأس متمایز از یک گراف بیش از یک یال وجود داشته باشد، آن را یک گراف چند گانه می گوییم.
گراف جهت دار: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه ای متناهی و ناتهی است و E زیرمجموعه ای از مجموعه ی تمام زوج مرتب های متشکل از اعضای V است.
گراف کامل:در نظریه گراف ،یک گراف کامل ،گرافی است که هر بین هر دو راس آن دقیقا یک یال وجود داشته باشد
· یک گراف کامل از مرتبه n،دارای n راس و یال است و آن را با نشان میدهند.
· یک گراف کامل یک گراف منتظم از درجه n-1 است.
آخرین ویرایش:
