• مشکی
  • سفید
  • سبز
  • آبی
  • قرمز
  • نارنجی
  • بنفش
  • طلایی
انجمن ها > انجمن دانش آموزی > صفحه اول بحث
لطفا در سایت شناسائی شوید!
دانش آموزی (بازدید: 2170)
چهارشنبه 8/3/1392 - 14:52 -0 تشکر 606977
نظریه گراف

بسم الله الرحمن الرحیم

سلام علیکم

در این بحث قصد داریم شما را با
نظریه گراف آشنا کنیم.

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

از این مبحث هر سال در کنکور سراسری و آزاد رشته ریاضی به صورت مستقیم تست می آید.

موفق و موید باشید.

یا حق.

چهارشنبه 8/3/1392 - 14:54 - 0 تشکر 606978

مقدمه ای از نظریه گراف


تعریف دقیق‌تر گراف به این صورت است، که گراف مجموعه‌ای از رأس‌ها است، که توسط خانواده‌ای از زوج‌های مرتب که همان یال‌ها هستند به هم مربوط (وصل) شده‌اند.

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

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

چهارشنبه 8/3/1392 - 14:55 - 0 تشکر 606979

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

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

نظریه گراف یکی از پرکاربردترین نظریه‌ها در شاخه‌های مختلف علوم مهندسی (مانند عمران)، باستان‌شناسی (کشف محدوده یک تمدن) و ... است.

روابط میان راس های یک گراف را می‌توان با کمک ماتریس بیان کرد .

براى نمایش تصویرى گراف ها معمولا از نقطه یا دایره براى كشیدن راس ها و از كمان یا خط راست براى كشیدن یال بین راس ها استفاده میشود.

چهارشنبه 8/3/1392 - 14:56 - 0 تشکر 606980

اندازه گراف

اندازه گراف تعداد یال های یک گراف است و به صورت |(E(G| بیان می‌شود.


درجه راس ها

در نظریه گراف ها، درجه یك راس به تعداد یال هاى متصل به آن راس گفته میشود. به عبارت دیگر. درجه یك راس تعداد همسایگى (مجاورت) هاى مستقیم یك راس را بیان میكند. از آنجا كه هر یال در گراف دو راس را به هم وصل میكند، مجموع درجه راس هاى یك گراف با دو برابر تعداد یال هاى ان گراف برابر است.


انواع گراف

گراف ساده: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از تمام زیرمجموعه‌های دو عضوی V می‌باشد. اعضای V را رأسهای G و اعضای E را یالهای G مینامیم. به بیان ساده تر بین دو رأس یک گراف ساده حداکثر یک یال وجود دارد.

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

گراف جهت دار: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از مجموعهٔ تمام زوج مرتب‌های متشکل از اعضای V است.

گراف مسطح: گراف مسطح گرافی است که می‌توان آن را در یک صفحه محاط کرد به گونه‌ای که یال هایش یکدیگر را تنها در راس ها قطع کنند.

گراف وزن دار: در یك گراف وزن دار، به هر یال یك وزن (عدد) نسبت داده میشود. معمولا اعداد حقیقى به عنوان وزن یال ها استفاده میشوند. اما بسیارى از الگوریتم هاى پر كاربرد فقط براى گراف هایى كه داراى وزن صحیح یا مثبت هستند طراحى شده اند.

چهارشنبه 8/3/1392 - 14:58 - 0 تشکر 606981

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


گاهی اوقات ما می خواهیم در یک گراف حرکت کنیم.به اینصورت که از راسی به راسی دیگر برویم.در اینصورت ممکن است برای ما مهم باشد که از روی یال یا راس تکراری حرکت نکنیم(مشابه مسالهٔ فروشندهٔ دوره گرد).این مساله در صرفه جویی زمان و هزینه هم مهم است.(یعنی مبحث بهینه سازی).دراینجا دو موضوع گرافهای اویلری(دور زدن در گراف بدون یال تکراری)و همیلتونی(دور زدن بدون راس تکراری) مطرح می‌شود.براحتی می‌توان بررسی کرد که راسهای گراف اویلری باید درجهٔ زوج داشته باشند.اما اینکه شرایط کامل لازم و کافی برای همیلتونی بودن یک گراف چیست هنوز حل نشده مانده است.

چهارشنبه 8/3/1392 - 14:59 - 0 تشکر 606982

مثال‌هایی از گراف کامل


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

img/daneshnameh_up/c/c8/200px-Complete_graph_K1.png img/daneshnameh_up/4/4f/200px-Complete_graph_K2.png
img/daneshnameh_up/3/3e/200px-Complete_graph_K3.png img/daneshnameh_up/b/b5/200px-Complete_graph_K4.png
img/daneshnameh_up/3/38/200px-Complete_graph_K5.png img/daneshnameh_up/1/1c/200px-Complete_graph_K6.png
img/daneshnameh_up/1/1e/200px-Complete_graph_K7.png img/daneshnameh_up/3/36/200px-Complete_graph_K8.png

چهارشنبه 8/3/1392 - 15:1 - 0 تشکر 606984

گراف دو بخشی:


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

شنبه 11/3/1392 - 14:34 - 0 تشکر 607795

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


تعریف ها:


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

اگر یک جنگل با n راس باشد آن گاه از شرایط زیر پیروی می کند:
T یک درخت است.
T مداری ندارد و n-1 یال دارد.
T همبند است و n-1 یال دارد.
هر دو راس T با مسیر منحصر به فرد به هم متصل می شوند.
T مداری ندارد و با افزودن یگ یال جدید دقیقاً یک مدار بوجود می آید.

شنبه 11/3/1392 - 14:40 - 0 تشکر 607796

ماتریس مجاورت گراف


تعریف


ماتریس مجاورت گراف، ماتریس است که خصوصیات و ویژگی های یک گراف را به طور خلاصه نمایش می دهد.
ماتریس مجاورت گراف، ماتریسی است که ویژگی های زیر را دارد:
1) ماتریس مربعی است که تعداد سطر و ستون آن برابر با اندازه (تعداد راس) گراف می باشد.
2) این ماتریس فقط از اعداد یک و صفر تشکیل شده است.
3)رایه های واقع بر قطر اصلی آن فقط و فقط از صفر تشکیل شده باشد.
4)مهمتر از همه این است که این ماتریس باید متقارن باشد.
به کمک این ماتریس می توانیم به آسانی، یک گراف را رسم کنیم. هر سطر نشان می دهد که آن راس مربوط به آن سطر به چه روسی متصل است به ازای هر یالی که آن راس به راس دیگری متصل می شود، عدد یک را می گذاریم و اگر دو راس به هم متصل نباشند، عدد صفر را می گذاریم. پس تعدا یک های یک سطر درجه آن سطر می باشد.


قضایای مربوط به ماتریس مجاورت گراف:


1)اگر M ماتریس مجاورت یک گراف باشد، آنگاه درایه های واقع بر سطر iام ستون iام ماتریس M به توان دو برابر با درجه راس iام است.

برو به انجمن
فعالترین ها در هفته گذشته
انجمن فعال در هفته گذشته
مدیر فعال در هفته گذشته
آخرین مطالب
  • آلبوم تصاویر بازدید از کلیسای جلفای...
    آلبوم تصاویر بازدید اعضای انجمن نصف جهان از کلیسای جلفای اصفهان.
  • بازدید از زیباترین کلیسای جلفای اصفهان
    جمعی از کاربران انجمن نصف جهان، در روز 27 مردادماه با همکاری دفتر تبیان اصفهان، بازدیدی را از کلیسای وانک، به عمل آورده‌اند. این کلیسا، یکی از کلیساهای تاریخی اصفهان به شمار می‌رود.
  • اعضای انجمن در خانه شهید بهشتی
    خانه پدری آیت الله دکتر بهشتی در اصفهان، امروزه به نام موزه و خانه فرهنگ شهید نام‌گذاری شده است. اعضای انجمن نصف جهان، در بازدید دیگر خود، قدم به خانه شهید بهشتی گذاشته‌اند.
  • اطلاعیه برندگان جشنواره انجمن‌ها
    پس از دو ماه رقابت فشرده بین کاربران فعال انجمن‌ها، جشنواره تابستان 92 با برگزاری 5 مسابقه متنوع در تاریخ 15 مهرماه به پایان رسید و هم‌اینک، زمان اعلام برندگان نهایی این مسابقات فرارسیده است.
  • نصف جهانی‌ها در مقبره علامه مجلسی
    اعضای انجمن نصف جهان، در یك گردهمایی دیگر، از آرامگاه علامه مجلسی و میدان احیا شده‌ی امام علی (ع) اصفهان، بازدیدی را به عمل آوردند.