Borna66
04-08-2009, 02:31 PM
سیری در نظریه گراف
مقدمه:
اندک زمانی است که واژه گراف در ادبیات ریاضی وارد شده است، گرچه شروع آن را می توان از زمان لئناردو اویلر ریاضیدان سوئیسی (1707-1783) دانست. اما علاقه ی شدید و مداوم به نظریه ی گراف ، بعنوان شاخه ای از ریاضیات ، از سال 1930 به بعد، آشکار گردید و امروزه این نظریه یکی از پربارترین و محبوب ترین شاخه های ریاضیات و علوم کامپیوتر است و علت آن نیز به خاطر قابلیت کاربرد آن در بسیاری از مسائل گسترده ی جامعه مدرن امروزی است.هنگامی که مساله ای به زبان گراف فرمول بندی شد، درک آن بسیار آسان تر خواهد شد. امروزه نظریه ی گراف یکی از موضوعات مهم دئر ریاضیات گسسته است. گرافها، مدل های راضی برای یک مجموعه گسسته هستند، که اعضای آن به طریقی با هم مرتبط می باشند. اعضای این مجموعه می توانند انسان ها یا رابطه ی خویشاوندی ، یا دوستی و… باشد. اعضای این مجوعه می توانند، محل اتصالهای سیم های یک شبکه ی برق و رابطه ی آنها، سیم های واصل بین دو مقطه باشد و یا عناصر مجوعه می توانند اتم های یک مولکول و ارتباط آن ها، اتصالهای شیمیایی باشد. نظریه گراف ریشه در بازیها و معما ها نیز دارد، اما امروزه این نظریه نه تنها در ریاضیات بلکه در سایر علوم مانندا اقتصاد، روانشناسی،ژنتیک و باستان شناسی کاربرد فراوانی دارد.
مفهوم گراف:
واژه گراف، نه تنها در ریاضیات، بلکه در سایر علوم و حتی در زندگی روزانه به نام های گوناگون مانند طرح دیاگرام، نگاره، نقشه، ماز و… بکار می رود. مثلا ممکن است به بهانه های مختلف شکلی رسم کنیم که از نقطه هایی تشکیل شده باشد و اگر چند نقطه، رابطه هایی با هم داشته باشند این روابط را با کشیدن خط بین آن ها نشان دهیم. نیز می توانیم تیم های ورزشی را در نظر بگیریم و آن ها را با نقاط A,B,C,… روی صفحه رسم کنیم و خطوط را با این شرط وصل کنیم که آن تیم ها با هم بازی داشته باشند، در ابتدا که بازی صورت نگرفته فقط چند نقطه داریم، ولی وقتی تیم ها باهم بازی کردند، بین تمام نقاط خط هایی وصل کنیم، بدین ترتیب یک گراف ساخته ایم، که با یک نگاه، راحت متوجه رابطه بین نقاط می شویم. بدیهی است که در انتخاب مکان نقاط در صفحه و طرز رسم کردن خطوط آزاد بوده ایم. اگر هیچ تیمی بازی نکرده باشد، هیچ خطی وصل نمی شود و در این صورت گراف، گراف صفحه نخواهد بود و اگر با هم بازی کنند، گراف کامل بوجود می آید.
قابل ذکر است که اگر نقاط را رئوس گراف و خطوط را یال بنامیم داریم: G(V.E) که آن را گراف G با رئوس V. و یال های E می نامیم.
اکنون به معرفی چند نوع گراف می پردازیم:
1) گراف های یکریخت: اگر در دو گراف، تعداد راس ها برابر بوده، بطوریکه هر دو راس متناظر، با یک حرف نام گذاری شده باشد، آن گاه وقتی دو راس بوسیله ی یالی بهم مربوط باشند، راس های هم نام آن ها در گراف دوم نیز بوسیله ی یالی بهم مربوط شوند.
2) گراف همبند و ناهمبند: اگر از هر دو راس دلخواه گراف، بتوان با حرکت روی یال ها، به راس دلخواه دیگر رسید، چنین گرافی همبند و در غیر این صورت ناهمبند است، یعنی گراف همبند از یک قطعه و ناهمبند از چند قطعه تشکیل می شود.
مرتبه، اندازه و درجه گراف:
به تعداد رئوس هر گراف مرتبه و به تعداد یالهای آن، اندازه و تعداد یال های منتهی به یک راس را درجه ی آن گراف گوییم.
بدیهی است که در گراف صفر درجه، هر راس برابر صفر است و در گراف کامل با n راس درجه، هر راس برابر با n-1 خواهد بود. راس هایی که درجه زوج دارند راس های زوج و راس هایی که درجه فرد دارند راس های فرد، نامیده می شوند. مساله حایز اهمیت این است که در هر گراف، تعداد رئوس فرد، زوج هستند، یعنی نمی توان گرافی رسم کرد که مثلا: 3 تا راس فرد داشته باشد. بعنوان مثال نمی توان گرافی رسم کرد که درجه راس های آن 5،0،2،2،5،8،7،6 باشد زیرا تعداد رئوس فرد 3 تا هستند یعنی(5،7،5)!
مقدمه:
اندک زمانی است که واژه گراف در ادبیات ریاضی وارد شده است، گرچه شروع آن را می توان از زمان لئناردو اویلر ریاضیدان سوئیسی (1707-1783) دانست. اما علاقه ی شدید و مداوم به نظریه ی گراف ، بعنوان شاخه ای از ریاضیات ، از سال 1930 به بعد، آشکار گردید و امروزه این نظریه یکی از پربارترین و محبوب ترین شاخه های ریاضیات و علوم کامپیوتر است و علت آن نیز به خاطر قابلیت کاربرد آن در بسیاری از مسائل گسترده ی جامعه مدرن امروزی است.هنگامی که مساله ای به زبان گراف فرمول بندی شد، درک آن بسیار آسان تر خواهد شد. امروزه نظریه ی گراف یکی از موضوعات مهم دئر ریاضیات گسسته است. گرافها، مدل های راضی برای یک مجموعه گسسته هستند، که اعضای آن به طریقی با هم مرتبط می باشند. اعضای این مجموعه می توانند انسان ها یا رابطه ی خویشاوندی ، یا دوستی و… باشد. اعضای این مجوعه می توانند، محل اتصالهای سیم های یک شبکه ی برق و رابطه ی آنها، سیم های واصل بین دو مقطه باشد و یا عناصر مجوعه می توانند اتم های یک مولکول و ارتباط آن ها، اتصالهای شیمیایی باشد. نظریه گراف ریشه در بازیها و معما ها نیز دارد، اما امروزه این نظریه نه تنها در ریاضیات بلکه در سایر علوم مانندا اقتصاد، روانشناسی،ژنتیک و باستان شناسی کاربرد فراوانی دارد.
مفهوم گراف:
واژه گراف، نه تنها در ریاضیات، بلکه در سایر علوم و حتی در زندگی روزانه به نام های گوناگون مانند طرح دیاگرام، نگاره، نقشه، ماز و… بکار می رود. مثلا ممکن است به بهانه های مختلف شکلی رسم کنیم که از نقطه هایی تشکیل شده باشد و اگر چند نقطه، رابطه هایی با هم داشته باشند این روابط را با کشیدن خط بین آن ها نشان دهیم. نیز می توانیم تیم های ورزشی را در نظر بگیریم و آن ها را با نقاط A,B,C,… روی صفحه رسم کنیم و خطوط را با این شرط وصل کنیم که آن تیم ها با هم بازی داشته باشند، در ابتدا که بازی صورت نگرفته فقط چند نقطه داریم، ولی وقتی تیم ها باهم بازی کردند، بین تمام نقاط خط هایی وصل کنیم، بدین ترتیب یک گراف ساخته ایم، که با یک نگاه، راحت متوجه رابطه بین نقاط می شویم. بدیهی است که در انتخاب مکان نقاط در صفحه و طرز رسم کردن خطوط آزاد بوده ایم. اگر هیچ تیمی بازی نکرده باشد، هیچ خطی وصل نمی شود و در این صورت گراف، گراف صفحه نخواهد بود و اگر با هم بازی کنند، گراف کامل بوجود می آید.
قابل ذکر است که اگر نقاط را رئوس گراف و خطوط را یال بنامیم داریم: G(V.E) که آن را گراف G با رئوس V. و یال های E می نامیم.
اکنون به معرفی چند نوع گراف می پردازیم:
1) گراف های یکریخت: اگر در دو گراف، تعداد راس ها برابر بوده، بطوریکه هر دو راس متناظر، با یک حرف نام گذاری شده باشد، آن گاه وقتی دو راس بوسیله ی یالی بهم مربوط باشند، راس های هم نام آن ها در گراف دوم نیز بوسیله ی یالی بهم مربوط شوند.
2) گراف همبند و ناهمبند: اگر از هر دو راس دلخواه گراف، بتوان با حرکت روی یال ها، به راس دلخواه دیگر رسید، چنین گرافی همبند و در غیر این صورت ناهمبند است، یعنی گراف همبند از یک قطعه و ناهمبند از چند قطعه تشکیل می شود.
مرتبه، اندازه و درجه گراف:
به تعداد رئوس هر گراف مرتبه و به تعداد یالهای آن، اندازه و تعداد یال های منتهی به یک راس را درجه ی آن گراف گوییم.
بدیهی است که در گراف صفر درجه، هر راس برابر صفر است و در گراف کامل با n راس درجه، هر راس برابر با n-1 خواهد بود. راس هایی که درجه زوج دارند راس های زوج و راس هایی که درجه فرد دارند راس های فرد، نامیده می شوند. مساله حایز اهمیت این است که در هر گراف، تعداد رئوس فرد، زوج هستند، یعنی نمی توان گرافی رسم کرد که مثلا: 3 تا راس فرد داشته باشد. بعنوان مثال نمی توان گرافی رسم کرد که درجه راس های آن 5،0،2،2،5،8،7،6 باشد زیرا تعداد رئوس فرد 3 تا هستند یعنی(5،7،5)!