تاریخچه ی:
گراف و طبقه بندی آن
تفاوت با نگارش: 1
| ||گراف شاخهای جدید و بسیار جالب در ریاضیات میباشد. در ریاضیات تعریفهای مختلفی برای گراف ارائه میشود که این تعریفها با توجه به سطح مخاطب از شهودی به صوری حر کت میکند. تعریفی که ما از گراف برایتان ارائه میدهیم، یک تعریف تقریبا شهودی میباشد:
''یک گراف شامل نقاطی است که راس نامیده میشود و این راسها به وسیله خطوطی (که لازم نیست خط راست باشند) به هم وصل میشوند. این خطوط را یال میگوئیم.''
در بعضی از کتابها از کلمات ''گره'' و ''نقطه'' هم به جای ''راس'' استفاده میشود.|| | | ||گراف شاخهای جدید و بسیار جالب در ریاضیات میباشد. در ریاضیات تعریفهای مختلفی برای گراف ارائه میشود که این تعریفها با توجه به سطح مخاطب از شهودی به صوری حر کت میکند. تعریفی که ما از گراف برایتان ارائه میدهیم، یک تعریف تقریبا شهودی میباشد:
''یک گراف شامل نقاطی است که راس نامیده میشود و این راسها به وسیله خطوطی (که لازم نیست خط راست باشند) به هم وصل میشوند. این خطوط را یال میگوئیم.''
در بعضی از کتابها از کلمات ''گره'' و ''نقطه'' هم به جای ''راس'' استفاده میشود.|| |
| !ریشه لغوی | | !ریشه لغوی |
| « گراف » از کلمه «''Graph''» از زبان انگلیسی برداشته شده است که به معنای ''نمودار و طرح هندسی'' میباشد. | | « گراف » از کلمه «''Graph''» از زبان انگلیسی برداشته شده است که به معنای ''نمودار و طرح هندسی'' میباشد. |
| !دید کلی | | !دید کلی |
| گراف یکی از رشتههای به روز ریاضیات است. امروزه حجم مقالات ارائه شده در گراف آنقدر زیاد است که گردآوری آنها واقعا سخت میباشد. مسائل زیادی وجود دارد که تا بحال حل نشدهاند و در دانشگاههای معتبر هم در ایران و هم در خارج به عنوان رشتهای تخصصی نیز به گراف توجه میشود. به راحتی میتوانیم بگوییم که گراف از مسائل کاربردی واقعا زیادی تشکیل شده، بطوری که مسائل روزمره مانند مسائل مربوط به دوستی (به عنوان رابطه دو طرفه) ، دست دادن ، ازدواج ، شجرهنامه و هزاران هزار رابطه قابل تفسیر و نشان دادن به شکل گراف هستند که رابطها در این موارد متناظر با یالهای گراف میباشند. مسائل همبندی ، ((مسئله پلهای کونینگسبرگ)) (Koningsbrega) ، ((مسئله چهار رنگ)) ، ((مسئله پستچی دوره گرد)) ، ((مسئله جورسازی)) و ... تنها قسمتی از مسائل جالب و مشهور در تئوری گراف میباشند. | | گراف یکی از رشتههای به روز ریاضیات است. امروزه حجم مقالات ارائه شده در گراف آنقدر زیاد است که گردآوری آنها واقعا سخت میباشد. مسائل زیادی وجود دارد که تا بحال حل نشدهاند و در دانشگاههای معتبر هم در ایران و هم در خارج به عنوان رشتهای تخصصی نیز به گراف توجه میشود. به راحتی میتوانیم بگوییم که گراف از مسائل کاربردی واقعا زیادی تشکیل شده، بطوری که مسائل روزمره مانند مسائل مربوط به دوستی (به عنوان رابطه دو طرفه) ، دست دادن ، ازدواج ، شجرهنامه و هزاران هزار رابطه قابل تفسیر و نشان دادن به شکل گراف هستند که رابطها در این موارد متناظر با یالهای گراف میباشند. مسائل همبندی ، ((مسئله پلهای کونینگسبرگ)) (Koningsbrega) ، ((مسئله چهار رنگ)) ، ((مسئله پستچی دوره گرد)) ، ((مسئله جورسازی)) و ... تنها قسمتی از مسائل جالب و مشهور در تئوری گراف میباشند. |
| !تاریخچه | | !تاریخچه |
| در زمان « ((اویلر)) » ، هفت پل در رودخانهای که منشعب به دو قسمت میگشت، مسئله جالبی را برای گردشگران و اهالی ایجاد کرده بود و آن گذر از تمامی پلها به صورتی که از هر پل فقط یک بار عبور کنند، بود. این رودخانه در شهر ''کونینگسبرگ'' قرار داشت؛ به همین دلیل این مسئله به مسئله پلهای کونینگسبرگ مشهور است.
خیلی جالب است بدانید که مردم در این شهر دیگر بر این باور رسیده بودند که چنین مسیری وجود ندارد و این مسئله را به اویلر مطرح کرده بودند و جالبتر اینکه اویلر ثابت کرد چنین مسیری واقعا وجود ندارد و یافت نمیشود. دست نوشتههای مربوط به این مسئله که در سال 1736 م. توسط اویلر نوشته شده بودند، به عنوان قدیمیترین دست نوشتههای مربوط به گراف تلقی میگردند. در این نوشتهها لم دست دادن نیز دیده میشود. | | در زمان « ((اویلر)) » ، هفت پل در رودخانهای که منشعب به دو قسمت میگشت، مسئله جالبی را برای گردشگران و اهالی ایجاد کرده بود و آن گذر از تمامی پلها به صورتی که از هر پل فقط یک بار عبور کنند، بود. این رودخانه در شهر ''کونینگسبرگ'' قرار داشت؛ به همین دلیل این مسئله به مسئله پلهای کونینگسبرگ مشهور است.
خیلی جالب است بدانید که مردم در این شهر دیگر بر این باور رسیده بودند که چنین مسیری وجود ندارد و این مسئله را به اویلر مطرح کرده بودند و جالبتر اینکه اویلر ثابت کرد چنین مسیری واقعا وجود ندارد و یافت نمیشود. دست نوشتههای مربوط به این مسئله که در سال 1736 م. توسط اویلر نوشته شده بودند، به عنوان قدیمیترین دست نوشتههای مربوط به گراف تلقی میگردند. در این نوشتهها لم دست دادن نیز دیده میشود. |
| !نقش و تاثیر زندگی | | !نقش و تاثیر زندگی |
| مسائل زیادی در زندگی مطرح میشود که قابل تبدیل به مسائل گراف هستند. امروزه بهینه بودن انتخابها خیلی اهمیت دارد. این بهینه بودن شامل انتخاب کوتاهترین مسیر در مسافرت از شهری به شهر دیگر ، عبور از تمامی کوچه در کمترین زمان برای پک پستچی و ... میباشند که در گراف مورد بحث قرار میگیرند. پیشرفت علوم و فناوری اطلاعات ، افزایش استفاده از کامپیوتر و وابستگی این علوم به نظریههای گراف اهمیت بحث گراف را در زندگی و آینده نزدیک نشان میدهد. به هر حال تکنولوژی و بهنیه کردن آن در عرصه صنعت لزوم استفاده را بیشتر برای ما روشن میکند، اما از نظر ریاضی بهترین دیدی که شاید بتوان ارائه داد، نگاه به تئوری گراف به عنوان ابزار کمک کننده حل مسائل است، نه حل آنها. جالب است بدانید که نظریه گراف در حل مسائل ریاضی سایر شاخهها نیز کمک کننده میباشد. | | مسائل زیادی در زندگی مطرح میشود که قابل تبدیل به مسائل گراف هستند. امروزه بهینه بودن انتخابها خیلی اهمیت دارد. این بهینه بودن شامل انتخاب کوتاهترین مسیر در مسافرت از شهری به شهر دیگر ، عبور از تمامی کوچه در کمترین زمان برای پک پستچی و ... میباشند که در گراف مورد بحث قرار میگیرند. پیشرفت علوم و فناوری اطلاعات ، افزایش استفاده از کامپیوتر و وابستگی این علوم به نظریههای گراف اهمیت بحث گراف را در زندگی و آینده نزدیک نشان میدهد. به هر حال تکنولوژی و بهنیه کردن آن در عرصه صنعت لزوم استفاده را بیشتر برای ما روشن میکند، اما از نظر ریاضی بهترین دیدی که شاید بتوان ارائه داد، نگاه به تئوری گراف به عنوان ابزار کمک کننده حل مسائل است، نه حل آنها. جالب است بدانید که نظریه گراف در حل مسائل ریاضی سایر شاخهها نیز کمک کننده میباشد. |
| !آشنایی با بعضی مفاهیم مهم گراف | | !آشنایی با بعضی مفاهیم مهم گراف |
| *__حلقه :__ اگر یالی از راسی به خودش وصل شده باشد، آن یال را ''حلقه'' مینامیم.
| | *__حلقه :__ اگر یالی از راسی به خودش وصل شده باشد، آن یال را ''حلقه'' مینامیم.
|
| *__چند گراف :__ اگر در گرافی بین دو راس بیش از یک یال موجود باشد، آن گراف را ''چند گراف'' مینامیم.
| | *__چند گراف :__ اگر در گرافی بین دو راس بیش از یک یال موجود باشد، آن گراف را ''چند گراف'' مینامیم.
|
| *__گراف ساده :__ گراف بدون حلقه که چند گراف نباشد را ''گراف ساده'' مینامیم.
| | *__گراف ساده :__ گراف بدون حلقه که چند گراف نباشد را ''گراف ساده'' مینامیم.
|
| *__دو راس مجاور :__ دو راس را مجاور گوئیم، هر گاه یالی آن دو را به هم وصل کند.
| | *__دو راس مجاور :__ دو راس را مجاور گوئیم، هر گاه یالی آن دو را به هم وصل کند.
|
| *__دو یال مجاور :__ دو یال را مجاور گوئیم، هر گاه در راسی مشترک باشند.
| | *__دو یال مجاور :__ دو یال را مجاور گوئیم، هر گاه در راسی مشترک باشند.
|
| *__درجه یک راس :__ در یک گراف تعداد یالهای متصل به یک راس را ''درجه آن راس'' میگوئیم و با deg نشان میدهیم.
| | *__درجه یک راس :__ در یک گراف تعداد یالهای متصل به یک راس را ''درجه آن راس'' میگوئیم و با deg نشان میدهیم.
|
| *__((گشت)) :__ یک گشت در گراف متشکل از دنبالهای از k یال است که به صورت UV , VW , … , YZ میباشد. این گشت به وسیله UVW … Z نشان داده میشود.
| | *__((گشت)) :__ یک گشت در گراف متشکل از دنبالهای از k یال است که به صورت UV , VW , … , YZ میباشد. این گشت به وسیله UVW … Z نشان داده میشود.
|
| *__مسیر :__ گشتی را که در آن هیچ یک از راسها و یالها تکرار نشود، ''مسیر'' میگوئیم.
| | *__مسیر :__ گشتی را که در آن هیچ یک از راسها و یالها تکرار نشود، ''مسیر'' میگوئیم.
|
| *__گشت بسته :__ دنبالهای از یالها که از یک راس شروع و به آن ختم میشود. مانند UV , VW , … , YZ , ZU را ''گشت بسته'' مینامیم.
| | *__گشت بسته :__ دنبالهای از یالها که از یک راس شروع و به آن ختم میشود. مانند UV , VW , … , YZ , ZU را ''گشت بسته'' مینامیم.
|
| *__دور :__ مسیر بسته را ''دور'' مینامیم. | | *__دور :__ مسیر بسته را ''دور'' مینامیم. |
| !طبقه بندیهای مشهور در تئوری گراف | | !طبقه بندیهای مشهور در تئوری گراف |
| #__((گراف همبند|گراف همبند و ناهمبند)) :__
یک گراف همبند است اگر بین هر دو راس دلخواه آن مسیری وجود داشته باشد. در غیر این صورت گراف را ناهمبند گوئیم.
| | #__((گراف همبند|گراف همبند و ناهمبند)) :__
یک گراف همبند است اگر بین هر دو راس دلخواه آن مسیری وجود داشته باشد. در غیر این صورت گراف را ناهمبند گوئیم.
|
| #__((گراف اویلری|گراف اویلری و نااویلری)) :__
یک گراف همبند اویلری است اگر دارای گشتی بسته باشد که از همه یالهایش گذر میکند. در غیر این صورت نااویلری است.
| | #__((گراف اویلری|گراف اویلری و نااویلری)) :__
یک گراف همبند اویلری است اگر دارای گشتی بسته باشد که از همه یالهایش گذر میکند. در غیر این صورت نااویلری است.
|
| #__((گراف همیلتنی|گراف همیلتنی و ناهمیلتنی)) :__
یک گراف همبند همیلتنی است اگر دوری وجود داشته باشد که شامل همه رئوس آن باشد. در غیر این صورت ناهمیلتنی است.
| | #__((گراف همیلتنی|گراف همیلتنی و ناهمیلتنی)) :__
یک گراف همبند همیلتنی است اگر دوری وجود داشته باشد که شامل همه رئوس آن باشد. در غیر این صورت ناهمیلتنی است.
|
| #__((گراف مسطح|گراف مسطح و غیرمسطح)) :__
یک گراف مسطح است اگر بتوان آن را طوری کشید که هیچ دو یالی یکدیگر را مگر در راسها قطع نکنند. بطوری که در آن راس دو یال فوق مجاور میباشند. گرافی را که مسطح نباشد، غیرمسطح گوئیم.
| | #__((گراف مسطح|گراف مسطح و غیرمسطح)) :__
یک گراف مسطح است اگر بتوان آن را طوری کشید که هیچ دو یالی یکدیگر را مگر در راسها قطع نکنند. بطوری که در آن راس دو یال فوق مجاور میباشند. گرافی را که مسطح نباشد، غیرمسطح گوئیم.
|
| #__درخت :__
گراف فاقد دور و بدون حلقه را درخت مینامیم.
| | #__درخت :__
گراف فاقد دور و بدون حلقه را درخت مینامیم.
|
- | #__گرافهای دو بخشی ، کامل ، n _ منتظم :__
((گراف دو بخشی)) گرافی است که راسهای آن را بتوان به دو بخش A و B چنان تقسیم کرد که هر یال در گراف یک راسش در A باشد و راس دیگرش در B. گرافی که بین هر دو راس آن یالی باشد، ((نظریه گراف کامل)) میگوئیم. یک گراف ، ((گراف n _ منتظم|n _ منتظم)) است اگر درجه همه راسهایش n باشد. |
+ | #__گرافهای دو بخشی ، کامل ، n _ منتظم :__
((گراف دو بخشی)) گرافی است که راسهای آن را بتوان به دو بخش A و B چنان تقسیم کرد که هر یال در گراف یک راسش در A باشد و راس دیگرش در B. گرافی که بین هر دو راس آن یالی باشد، ((نظریه گراف کامل|گراف کامل)) میگوئیم. یک گراف ، ((گراف n _ منتظم|n _ منتظم)) است اگر درجه همه راسهایش n باشد. |
| !ارتباط با سایر علوم | | !ارتباط با سایر علوم |
| !!ارتباط با علم ریاضی (در قسمت نظریه مجموعههاو ...) | | !!ارتباط با علم ریاضی (در قسمت نظریه مجموعههاو ...) |
| نظریه گراف با بخشهای دیگر ریاضیات ارتباط بسیار تنانگی دارد و بسیاری از مسائل سایر بخشها در ریاضیات با گراف قابل حل شدهاند. قضایای بسیاری در ((آنالیز)) وجود دارند که ریشه حل آنها به لمی از قضیه دست دادن برمیگردد. | | نظریه گراف با بخشهای دیگر ریاضیات ارتباط بسیار تنانگی دارد و بسیاری از مسائل سایر بخشها در ریاضیات با گراف قابل حل شدهاند. قضایای بسیاری در ((آنالیز)) وجود دارند که ریشه حل آنها به لمی از قضیه دست دادن برمیگردد. |
| !!ارتباط با علوم کامپیوتر | | !!ارتباط با علوم کامپیوتر |
| ساختار فایلی کامپیوترها ، دو دویی بودن آنها ، رمزنگاری و ... بسیاری از مسائل مطرح شده در علوم کامپیوتر با گراف رابطه بسیار تنگاتنگی دارد. | | ساختار فایلی کامپیوترها ، دو دویی بودن آنها ، رمزنگاری و ... بسیاری از مسائل مطرح شده در علوم کامپیوتر با گراف رابطه بسیار تنگاتنگی دارد. |
| !!ارتباط با علوم الکترونیک | | !!ارتباط با علوم الکترونیک |
| گراف با علم الکترونیک نیز ارتباط دارد که ما فقط نمونهای از آن در اینجا ذکر میکنیم: شکل (1) پشت یک فیبر را نشان میدهد که دارای سوراخهایی است و خطوط ما بین این سوراخها نشان دهنده ارتباط الکترونیکی میباشد. مسئلهای که در اینجا مطرح میشود، این است که آیا ارتباط مطلوب و دلخواهمان را میتوانیم طوری پشت فیبر طراحی کنیم که هیچ دو مسیری یکدیگر را قطع نکنند؟ یا در حقیقت گراف متناظر مسطح باشد؟ | | گراف با علم الکترونیک نیز ارتباط دارد که ما فقط نمونهای از آن در اینجا ذکر میکنیم: شکل (1) پشت یک فیبر را نشان میدهد که دارای سوراخهایی است و خطوط ما بین این سوراخها نشان دهنده ارتباط الکترونیکی میباشد. مسئلهای که در اینجا مطرح میشود، این است که آیا ارتباط مطلوب و دلخواهمان را میتوانیم طوری پشت فیبر طراحی کنیم که هیچ دو مسیری یکدیگر را قطع نکنند؟ یا در حقیقت گراف متناظر مسطح باشد؟ |
| !!ارتباط با شیمی | | !!ارتباط با شیمی |
| گراف با علم شیمی نیز ارتباط دارد. نشان دادن آلکانها و پیدا کردن تعداد ایزومرهای آنها نمونهای از کاربرد گراف میباشد. | | گراف با علم شیمی نیز ارتباط دارد. نشان دادن آلکانها و پیدا کردن تعداد ایزومرهای آنها نمونهای از کاربرد گراف میباشد. |
| !!ارتباط با سایر رشتهها | | !!ارتباط با سایر رشتهها |
| گراف با دیگر رشتهها مانند باستان شناسی ، ژنتیک ، تحلیل ادبی و ... هم ارتباط دارد. | | گراف با دیگر رشتهها مانند باستان شناسی ، ژنتیک ، تحلیل ادبی و ... هم ارتباط دارد. |
| !چشم انداز | | !چشم انداز |
| هر یک از نظریات ریاضی تاریخی را با خود دارند که در بازهای از زمانها مانند روشن کردن آتش بسیار شعلهور و افروخته میشوند و در هنگام افروخته شدن اوج کار کردن و کشفیات ، شهرت را به خود اختصاص میدهند.
((جبر)) ، آنالیز ، ((هندسه)) ، ((توپولوژی _ مختلط)) و ... همه اینها برای خود و در زمان خود کارهای بزرگی محسوب میشدند، ولی دانشمندان آنقدر روی آنها کار کردهاند که گویا دیگر برای زمان ما و نیاز ما کار زیادی روی آنها نهانده است، اما گراف همچنان در زمان ما میدرخشد و گویا عصر ما عصر شعلهوری گراف است. گراف کارهای زیادی را در خود پنهان داشته که نیاز به کاشف دارد. امیدواریم شما خواننده گرامی قبل از هر کس دیگر رازهای این نظریه را به نام خود پیدا و ثبت کنید. | | هر یک از نظریات ریاضی تاریخی را با خود دارند که در بازهای از زمانها مانند روشن کردن آتش بسیار شعلهور و افروخته میشوند و در هنگام افروخته شدن اوج کار کردن و کشفیات ، شهرت را به خود اختصاص میدهند.
((جبر)) ، آنالیز ، ((هندسه)) ، ((توپولوژی _ مختلط)) و ... همه اینها برای خود و در زمان خود کارهای بزرگی محسوب میشدند، ولی دانشمندان آنقدر روی آنها کار کردهاند که گویا دیگر برای زمان ما و نیاز ما کار زیادی روی آنها نهانده است، اما گراف همچنان در زمان ما میدرخشد و گویا عصر ما عصر شعلهوری گراف است. گراف کارهای زیادی را در خود پنهان داشته که نیاز به کاشف دارد. امیدواریم شما خواننده گرامی قبل از هر کس دیگر رازهای این نظریه را به نام خود پیدا و ثبت کنید. |
| !مباحث مرتبط با عنوان | | !مباحث مرتبط با عنوان |
| *((گراف اویلری)) | | *((گراف اویلری)) |
| *((گراف دو بخشی)) | | *((گراف دو بخشی)) |
- | *((نظریه گراف کامل)) |
+ | *((نظریه گراف کامل|گراف کامل)) |
| *((گراف مسطح)) | | *((گراف مسطح)) |
| *((گراف n _ منتظم)) | | *((گراف n _ منتظم)) |
| *((گراف همبند)) | | *((گراف همبند)) |
| *((گراف همیلتنی)) | | *((گراف همیلتنی)) |
| *((گشت)) | | *((گشت)) |
| *((مسئله پستچی دوره گرد)) | | *((مسئله پستچی دوره گرد)) |
| *((مسئله پلهای کونینگسبرگ)) | | *((مسئله پلهای کونینگسبرگ)) |
| *((مسئله جورسازی)) | | *((مسئله جورسازی)) |
| *((مسئله چهار رنگ)) | | *((مسئله چهار رنگ)) |