گراف

[آبجی]

ریشه لغوی

« گراف » از کلمه «Graph» از زبان انگلیسی برداشته شده است که به معنای نمودار و طرح هندسی می‌باشد.
دید کلی

گراف یکی از رشته‌های به روز ریاضیات است. امروزه حجم مقالات ارائه شده در گراف آنقدر زیاد است که گردآوری آنها واقعا سخت می‌باشد. مسائل زیادی وجود دارد که تا بحال حل نشده‌اند و در دانشگاههای معتبر هم در ایران و هم در خارج به عنوان رشته‌ای تخصصی نیز به گراف توجه می‌شود. به راحتی می‌توانیم بگوییم که گراف از مسائل کاربردی واقعا زیادی تشکیل شده، بطوری که مسائل روزمره مانند مسائل مربوط به دوستی (به عنوان رابطه دو طرفه) ، دست دادن ، ازدواج ، شجره‌نامه و هزاران هزار رابطه قابل تفسیر و نشان دادن به شکل گراف هستند که رابطها در این موارد متناظر با یالهای گراف می‌باشند. مسائل همبندی ، مسئله پلهای کونینگسبرگ (Koningsbrega) ، مسئله چهار رنگ ، مسئله پستچی دوره گرد ، مسئله جورسازی و ... تنها قسمتی از مسائل جالب و مشهور در تئوری گراف می‌باشند.
تاریخچه

در زمان « اویلر » ، هفت پل در رودخانه‌ای که منشعب به دو قسمت می‌گشت، مسئله جالبی را برای گردشگران و اهالی ایجاد کرده بود و آن گذر از تمامی پلها به صورتی که از هر پل فقط یک بار عبور کنند، بود. این رودخانه در شهر کونینگسبرگ قرار داشت؛ به همین دلیل این مسئله به مسئله پلهای کونینگسبرگ مشهور است.

خیلی جالب است بدانید که مردم در این شهر دیگر بر این باور رسیده بودند که چنین مسیری وجود ندارد و این مسئله را به اویلر مطرح کرده بودند و جالب‌تر اینکه اویلر ثابت کرد چنین مسیری واقعا وجود ندارد و یافت نمی‌شود. دست نوشته‌های مربوط به این مسئله که در سال 1736 م. توسط اویلر نوشته شده بودند، به عنوان قدیمی‌ترین دست نوشته‌های مربوط به گراف تلقی می‌گردند. در این نوشته‌ها لم دست دادن نیز دیده می‌شود.
نقش و تاثیر زندگی

مسائل زیادی در زندگی مطرح می‌شود که قابل تبدیل به مسائل گراف هستند. امروزه بهینه بودن انتخابها خیلی اهمیت دارد. این بهینه بودن شامل انتخاب کوتاهترین مسیر در مسافرت از شهری به شهر دیگر ، عبور از تمامی کوچه در کمترین زمان برای پک پستچی و ... می‌باشند که در گراف مورد بحث قرار می‌گیرند. پیشرفت علوم و فناوری اطلاعات ، افزایش استفاده از کامپیوتر و وابستگی این علوم به نظریه‌های گراف اهمیت بحث گراف را در زندگی و آینده نزدیک نشان می‌دهد. به هر حال تکنولوژی و بهنیه کردن آن در عرصه صنعت لزوم استفاده را بیشتر برای ما روشن می‌کند، اما از نظر ریاضی بهترین دیدی که شاید بتوان ارائه داد، نگاه به تئوری گراف به عنوان ابزار کمک کننده حل مسائل است، نه حل آنها. جالب است بدانید که نظریه گراف در حل مسائل ریاضی سایر شاخه‌ها نیز کمک کننده می‌باشد.
آشنایی با بعضی مفاهیم مهم گراف



حلقه : اگر یالی از راسی به خودش وصل شده باشد، آن یال را حلقه می‌نامیم.


چند گراف : اگر در گرافی بین دو راس بیش از یک یال موجود باشد، آن گراف را چند گراف می‌نامیم.


گراف ساده : گراف بدون حلقه که چند گراف نباشد را گراف ساده می‌نامیم.


دو راس مجاور : دو راس را مجاور گوئیم، هر گاه یالی آن دو را به هم وصل کند.


دو یال مجاور : دو یال را مجاور گوئیم، هر گاه در راسی مشترک باشند.


درجه یک راس : در یک گراف تعداد یالهای متصل به یک راس را درجه آن راس

می‌گوئیم و با deg نشان می‌دهیم.
گشت : یک گشت در گراف متشکل از دنباله‌ای از k یال است که به صورت UV , VW , … , YZ می‌باشد. این گشت به وسیله UVW … Z نشان داده می‌شود.


مسیر : گشتی را که در آن هیچ یک از راسها و یالها تکرار نشود، مسیر می‌گوئیم.


گشت بسته : دنباله‌ای از یالها که از یک راس شروع و به آن ختم می‌شود. مانند UV , VW , … , YZ , ZU را گشت بسته می‌نامیم.


دور : مسیر بسته را دور می‌نامیم.

طبقه بندی‌های مشهور در تئوری گراف



گراف همبند و ناهمبند :

یک گراف همبند است اگر بین هر دو راس دلخواه آن مسیری وجود داشته باشد. در غیر این صورت گراف را ناهمبند گوئیم.


گراف اویلری و نااویلری :

یک گراف همبند اویلری است اگر دارای گشتی بسته باشد که از همه یالهایش گذر می‌کند. در غیر این صورت نااویلری است.


گراف همیلتنی و ناهمیلتنی :

یک گراف همبند همیلتنی است اگر دوری وجود داشته باشد که شامل همه رئوس آن باشد. در غیر این صورت ناهمیلتنی است.


گراف مسطح و غیرمسطح :

یک گراف مسطح است اگر بتوان آن را طوری کشید که هیچ دو یالی یکدیگر را مگر در راسها قطع نکنند. بطوری که در آن راس دو یال فوق مجاور می‌باشند. گرافی را که مسطح نباشد، غیرمسطح گوئیم.


درخت :

گراف فاقد دور و بدون حلقه را درخت می‌نامیم.


گرافهای دو بخشی ، کامل ، n _ منتظم :

گراف دو بخشی گرافی است که راسهای آن را بتوان به دو بخش A و B چنان تقسیم کرد که هر یال در گراف یک راسش در A باشد و راس دیگرش در B. گرافی که بین هر دو راس آن یالی باشد، گراف کامل می‌گوئیم. یک گراف ، n _ منتظم است اگر درجه همه راسهایش n باشد.

ارتباط با سایر علوم

ارتباط با علم ریاضی (در قسمت نظریه مجموعه‌هاو ...)

نظریه گراف با بخشهای دیگر ریاضیات ارتباط بسیار تنانگی دارد و بسیاری از مسائل سایر بخشها در ریاضیات با گراف قابل حل شده‌اند. قضایای بسیاری در آنالیز وجود دارند که ریشه حل آنها به لمی از قضیه دست دادن برمی‌گردد.
ارتباط با علوم کامپیوتر

ساختار فایلی کامپیوترها ، دو دویی بودن آنها ، رمزنگاری و ... بسیاری از مسائل مطرح شده در علوم کامپیوتر با گراف رابطه بسیار تنگاتنگی دارد.
ارتباط با علوم الکترونیک

گراف با علم الکترونیک نیز ارتباط دارد که ما فقط نمونه‌ای از آن در اینجا ذکر می‌کنیم: شکل (1) پشت یک فیبر را نشان می‌دهد که دارای سوراخهایی است و خطوط ما بین این سوراخها نشان دهنده ارتباط الکترونیکی می‌باشد. مسئله‌ای که در اینجا مطرح می‌شود، این است که آیا ارتباط مطلوب و دلخواهمان را می‌توانیم طوری پشت فیبر طراحی کنیم که هیچ دو مسیری یکدیگر را قطع نکنند؟ یا در حقیقت گراف متناظر مسطح باشد؟
ارتباط با شیمی

گراف با علم شیمی نیز ارتباط دارد. نشان دادن آلکانها و پیدا کردن تعداد ایزومرهای آنها نمونه‌ای از کاربرد گراف می‌باشد.
ارتباط با سایر رشته‌ها

گراف با دیگر رشته‌ها مانند باستان شناسی ، ژنتیک ، تحلیل ادبی و ... هم ارتباط دارد.
چشم انداز

هر یک از نظریات ریاضی تاریخی را با خود دارند که در بازه‌ای از زمانها مانند روشن کردن آتش بسیار شعله‌ور و افروخته می‌شوند و در هنگام افروخته شدن اوج کار کردن و کشفیات ، شهرت را به خود اختصاص می‌دهند.

جبر ، آنالیز ، هندسه ، توپولوژی _ مختلط و ... همه اینها برای خود و در زمان خود کارهای بزرگی محسوب می‌شدند، ولی دانشمندان آنقدر روی آنها کار کرده‌اند که گویا دیگر برای زمان ما و نیاز ما کار زیادی روی آنها نهانده است، اما گراف همچنان در زمان ما می‌درخشد و گویا عصر ما عصر شعله‌وری گراف است. گراف کارهای زیادی را در خود پنهان داشته که نیاز به کاشف دارد. امیدواریم شما خواننده گرامی قبل از هر کس دیگر رازهای این نظریه را به نام خود پیدا و ثبت کنید.

[آبجی]

گراف دو بخشی:
مفهوم شهودی:
فرض کنید در یک شرکت صنعتی تعدادی شغل بدون متصدی می باشند و تعدادی متقاضی برای این مشاغل اعلام آمادگی نموده اند. حال این سوال مطرح می شود که آیا می توان به هر متقاضی شغلی متناسب او اختصاص داد؟
برای حل چنین مسئله ای که به مسئله ی تخصیص موسوم است، با استفاده از گراف می توان وضعیت های خاص را پیاده سازی نمود. بدین ترتیب که گروهی که متقاضی مشاغل هستند در مجموعه ای به نام X و مجموعه مشاغل بدون متصدی را در مجموعه ای به نام Y قرار می دهیم. گراف رسم شده چنین است که به بعضی از اعضای مجموعه X یک یا چند عضو از مجموعه Y توسط یال ها وصل می نماید.
به عبارت دیگر گراف بوجود امدی دارای یالهای xy است که مر متقاضی x را از مجموعه Xy از مجموعه Y متصل می نماید. به عبارت دقیقتر هیچ دو راس متعلق به مجموعه X(متفاضیان) یا هیچ دو راس متعلق به مجموعه Y(مشاغل) توسط هیچ یالی به هم متصل نمی باشند. چنین گرافی را گراف دوبخشی یا دوپارچه می گویند.
به شغلهای مناسب تعریف گراف دوبخشی:
گراف دوبخشی گرافی است که بتوان مجموعه رئوس آن را به دو مجموعه X و Y چنان افراز نمود که هر یال آن دارای یک انتها در X و یک انتها در Y باشد، به گونه ای که هیچ دوراسی در X یا در Y با هم مجاور نباشند. چنین افرازی را دوبخشی کردن گراف می نامند.



یادآوری: منظور از افراز یک مجموعه چون A به چند مجموعه، تقسیم مجموعه A به چند مجموعه ناتهی دیگر است که باهم اشتراکی نداشته باشند و اجتماع همه آنها برابر مجموعه A باشد. و در اینجا اگر V به عنوان مجموعه رئوس باشد افراز V به دو مجموعه X و Y (ناتهی) به این صورت است که: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/80cb25b42027233308eb2cfac65c6f52.png

به عنوان مثال گراف زیر یک گراف دو بخشی است:

http://daneshnameh.roshd.ir/mavara/img/daneshnameh_up/a/a2/two-part-Graph.jpg

چرا که در این گراف مجموعه رئوس را می توان به دو مجموعه http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/865a934a1e69dd1fdd8a0dd849da3250.png
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/2134b0f792743d667a3b902cb6ff278c.png چنان افراز نمود که هیچ دو راسی در این دو مجموعه با هم مجاور نباشند و هر یال تنها یک انتها در مجموعه اول و یک انتها در مجموعه دوم داشته باشد.
و

قضیه: اگر گراف k-منتظم، دارای دوبخش X و Y باشد، آنگاه تعداد عناصر X و Y باهم برابر است.

برهان:
فرض می کنیم X دارای m راس و Y دارای n راس از راسهای گراف دو بخشی k-منتظم می باشد. یشان می دهیم که: m=n.
از هر راس در مجموعه X به تعداد k، یال خارج می شود(چرا؟) پس تعداد کل یالها(q) برابر است با: q=km
چون جمعا" m+n راس داریم، لذا مطابق قضیه مجموع درجه های راس ها و تعریف گراف k-منتظم داریم:

http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/8f0cfef9146205af23956b866e61cba2.png

پس:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/321c585820e9283885f6594088de6cd7.png

و لذا حکم برقرار است.

گراف دو بخشی کامل:
گراف دو بخشی کامل یک گراف دو بخشی است که مجموع رئوس آن به دو مجموعه X و Y چنان افراز شده است و هر راس http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/563dca68bbcd72367a30f414a3a07f87.png در ان به هر راس http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/0f0a31ca77925e1863d984bc0600c864.png وصل شده است. گراف دو بخشی کامل را با نماد http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/933641f5e01b7991e47ed137cbf386ba.png نشان می دهند که در آن m تعداد عناصر مجموعه X و n تعداد عناصر مجموعه Y است.



به عنوان مثال گراف زیر یک گراف دو بخشی کامل http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/8532ce7069344716d423ca6efb3503d7.png است.


http://daneshnameh.roshd.ir/mavara/img/daneshnameh_up/b/be/perfect-two-part-Graph.jpg



قضیه: در گراف دو بخشی کامل http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/2ed00a665cbe82fa718378d7aa242df3.png همواره داریم:http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/aba0e1c0ce55033d0b14e0f11b75f34b.png که در آن q اندازه گراف مذکور است.

برهان:
می دانیم گراف http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/2ed00a665cbe82fa718378d7aa242df3.png دارای m راس در یک مجموعه و n راس در مجموعه ای دیگر است.
تعداد کل راس ها P=m+n می باشد(مرتبه گراف). اما برای یافتن تعداد یالهای گراف دو بخشی کامل http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/2ed00a665cbe82fa718378d7aa242df3.png ابتدا تعداد کل یالهای یک گراف کامل از مرتبه P=m+n را محاسبه کرده سپس تعداد کل یالهایی که راس های دو مجموعه را در خود دو مجموعه به هم وصل می کند از آن کم می کنیم. داریم:

http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/0d732807643ba6102e1f72ffb4b91174.png


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/6d025c02857d928aec0f03e86629d0d6.png


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/d166f14e714eb7e656c45bdab9a20c33.png




قضیه: اگر G یک گراف ساده و دو بخشی از مرتبه p و اندازه q باشد آنگاه: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/08b22d58ec44d5ff5a8b98f1645249a2.png

برهان:
چون گراف دو بخشی است مطابق قضیه قبل حداکثر یال آن برابر است با: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/8a803becd2ce223441104facaec32d03.png
که m تعداد یال بخش X و n تعداد یال بخش Y است.(بیشترین تعداد یال مربوط به زمانی است که گراف، دو بخشی کامل باشد).
از طرفی می دانیم که: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/96c1c13b6356a69a76c425d9f0184d7b.png پس: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/c08aaafc5b007d9af606a864150d7d03.png , داریم:

http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/206c474cc020cbcda502552e8347f054.png

چون u آهنگ تغییرات تعداد یال را نشان می دهد و http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/b290693215c3c9c24d37b1f3097cd84b.png پس از http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/12785ddf1bb32241680850a76a282ee5.png نتیجه می شود که: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/6db21a21081ad5112cadc48888f26619.png
ضمنا" می دانیم که:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/297d57674cf0ba766f90d37f60f1184e.png

پس بیشترین مقدار u در نقطه http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/6db21a21081ad5112cadc48888f26619.png اتفاق می افتد، یعنی:

http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/e653658a216fba8cb872000ca1e07270.png

بنابراین تعداد کل یالها نمی تواند از http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/c00ebc5344e1dac4abccde87d793dca5.png بیشتر باشد و لذا
:http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/08b22d58ec44d5ff5a8b98f1645249a2.png

[آبجی]

در نظریه گراف ،یک گراف کامل ،گرافی است که هر بین هر دو راس آن دقیقا یک یال وجود داشته باشد.یک گراف کامل از مرتبه n،دارای n راس و http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/d23f72e450ccd9e3f7083c7112077ad5.png یال است و با http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/4ec9f5b5d58f6f34d437bd3927880b06.png نشان میدهند.یک گراف کامل یک گراف منتظم از درجه n-1 است.در شکل زیر گرافهای کامل از مرتبه یک تا مرتبه هشت نمایش داده شده است. از تعریف این نوع گراف معلوم است که گراف کامل از مرتبه اول ،هیچ یالی ندارد.




http://daneshnameh.roshd.ir/mavara/img/daneshnameh_up/c/c8/200px-Complete_graph_K1.png http://daneshnameh.roshd.ir/mavara/img/daneshnameh_up/4/4f/200px-Complete_graph_K2.pnghttp://daneshnameh.roshd.ir/mavara/img/daneshnameh_up/3/3e/200px-Complete_graph_K3.png http://daneshnameh.roshd.ir/mavara/img/daneshnameh_up/b/b5/200px-Complete_graph_K4.pnghttp://daneshnameh.roshd.ir/mavara/img/daneshnameh_up/3/38/200px-Complete_graph_K5.png http://daneshnameh.roshd.ir/mavara/img/daneshnameh_up/1/1c/200px-Complete_graph_K6.pnghttp://daneshnameh.roshd.ir/mavara/img/daneshnameh_up/1/1e/200px-Complete_graph_K7.png http://daneshnameh.roshd.ir/mavara/img/daneshnameh_up/3/36/200px-Complete_graph_K8.png

[آبجی]

نظريه گراف شاخه اي از رياضيات است كه درباره اشياء خاصي در رياضي به نام گراف بحث مي‌كند. به صورت شهودي گراف نمودار يا دياگرامي است شامل تعدادي رأس كه با يالهايي به هم وصل شده‌اند. تعريف دقيق‌تر گراف به اين صورت است كه گراف مجموعه‌اي از رأس‌ها است كه توسط خانواده‌اي از زوج‌هاي مرتب كه همان يال‌ها هستند به هم مربوط شده‌اند.
يالها بر دو نوع ساده و جهت دار هستند كه هر كدام در جاي خود كاربردهاي بسياري دارد. مثلاً اگر صرفاً اتصال دو نقطه -مانند اتصال تهران و زنجان با كمك آزادراه- مد نظر شما باشد كافيست آن دو شهر را با دو نقطه نمايش داده و اتوبان مزبور را با يالي ساده نمايش دهيد. اما اگر بين دو شهر جاده اي يكطرفه وجود داشته باشد آنگاه لازمست تا شما با قرار دادن يالي جهت دار مسير حركت را در آن جاده مشخص كنيد.
آغاز نظريهٔ گراف به سدهٔ هجدهم بر مي‌گردد. اويلر رياضيدان بزرگ مفهوم گراف را براي حل مسئله پل‌هاي كونيگسبرگ ابداع كرد اما رشد و پويايي اين نظريه عمدتاً مربوط به نيم سدهٔ اخير و با رشد علم داده‌ورزي (انفورماتيك) بوده است.
مهم‌ترين كاربرد گراف مدل‌سازي پديده‌هاي گوناگون و بررسي بر روي آنهاست. با گراف مي‌توان به راحتي يك نقشه بسيار بزرگ يا شبكه‌اي عظيم را در درون يك ماتريس به نام ماتريس وقوع گراف ذخيره كرد و يا الگوريتمهاي‌ مناسب مانند الگوريتم دايسترا يا الگوريتم كروسكال و ... را بر روي آن اعمال نمود.
يكي از قسمت‌هاي پركاربرد نظريهٔ گراف، گراف‌هاي مسطح است كه به بررسي گراف‌هايي مي‌پردازد كه مي‌توان آن‌ها را به نحوي روي صفحه كشيد كه يال‌ها جز در محل راس ها يكديگر را قطع نكنند. اين نوع گراف در ساخت جاده ها و حل مساله كلاسيك و قديمي سه خانه و سه چاه آب به كار مي رود.
نظريه گراف يكي از پركاربردترين نظريه ها در شاخه هاي مختلف علوم مهندسي (مانند عمران)، باستانشناسي(كشف محدوده يك تمدن) و ... است.
انواع گراف

گراف ساده: هر گراف G زوج مرتبي مانند (V,E) است كه در آن V مجموعه اي متناهي و ناتهي است و E زيرمجموعه اي از تمام زيرمجموعه هاي دو عضوي V ميباشد. اعضاي V را رأسهاي G و اعضاي E را يالهاي G ميناميم. به بيان ساده تر بين دو رأس يك گراف ساده حداكثر يك يال وجود دارد.
گراف چندگانه: هرگاه بين دو رأس متمايز از يك گراف بيش از يك يال وجود داشته باشد، آن را يك گراف چند گانه مي گوييم.
گراف جهت دار: هر گراف G زوج مرتبي مانند (V,E) است كه در آن V مجموعه اي متناهي و ناتهي است و E زيرمجموعه اي از مجموعه ي تمام زوج مرتب هاي متشكل از اعضاي V است.
خصوصيات گرافهاي خاص

·اگر تعداد يال ها و درجه راس ها در گراف ساده برابر باشد گراف موردنظر منتظم كامل است رابطه بين راسها و يالها اين چنين است.
q=p(p-1)/2
كه در آن pتعداد راسها qتعداد يالها است.
·اگر گراف همبند باشد(يعني از هر نقطه بتوان به يك نقطه دلخواه ديگر رسيد) ولي دور نداشته باشد(يعني هيچ نقطه اي از دو راه به نقطه ي بعدي نرسد)مي گويند گراف درختي است. وفرمول آنهم اين چنين است.
p=1+q
كه در آن pتعداد راسها qتعداد يالها است.