انتقادات و پیشنهادات سوالات و مشکلات کاربران مكاتبه با گروه مديريت
انجمن پايان نامه ها بخش درخواست مقاله مجله الكترونيكي انجمن
بهترين كاربران هفته (به زودي) بهترين مديران هفته ( به زودي) جايزه ويژه ماه (به زودي)

نمایش نتایج: از شماره 1 تا 1 , از مجموع 1

موضوع: آموزش نظریه گراف و انواع گرافها (ریاضیات گسسته)

  1. #1
    آتيشپاره
    Pari آواتار ها
    تاریخ عضویت
    Sep 2011
    محل سکونت
    تو قلب ... :دي
    نوشته ها
    8,922
    پسندیده
    2,271
    مورد پسند : 4,562 بار در 2,252 پست
    حالت من : ShadOsarhal

    آموزش نظریه گراف و انواع گرافها (ریاضیات گسسته)

    تعریف

    فرض کنید V یک مجموعه ناتهی و E زیرمجموعهای از باشد در این صورت زوج را یک گراف می نامند.V را مجموعه راس ها و E را مجموعه یال ها می گویند. اگر ترتیب قرار گرفتن راس ها در مجموعه E مهم باشد،گراف را گراف جهتدار می گویند و یال از راس به سمت راس را به صورت نشان میدهند.در غیر این صورت گراف را بدون جهت مینامند و یال بین راس های و با نماد نشان میدهند.


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

    انواع گرافها

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


    • گراف همبند
    • گراف ناهمبند
    • گراف کامل
    • گراف اویلری
    • گراف همیلتونی
    • گراف درختی
    • گراف مسطح
    • گراف دو بخشی
    • گراف چندبخشی
    • گراف k-مکعب
    • گراف چرخ
    • گراف ستارهای
    • گراف بازهای
    • گراف اشتراکی
    • گراف منظم
    • گراف جهتدار



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


    • یک گراف کامل از مرتبه n،دارای n راس و یال است و آن را با نشان میدهند.
    • یک گراف کامل یک گراف منتظم از درجه n-1 است.


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

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






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


    تعریف گراف دوبخشی:
    گراف دوبخشی گرافی است که بتوان مجموعه رئوس آن را به دو مجموعه X و Y چنان افراز نمود که هر یال آن دارای یک انتها در X و یک انتها در Y باشد، به گونه ای که هیچ دوراسی در X یا در Y با هم مجاور نباشند. چنین افرازی را دوبخشی کردن گراف می نامند.



    • یادآوری: منظور از افراز یک مجموعه چون A به چند مجموعه، تقسیم مجموعه A به چند مجموعه ناتهی دیگر است که باهم اشتراکی نداشته باشند و اجتماع همه آنها برابر مجموعه A باشد. و در اینجا اگر V به عنوان مجموعه رئوس باشد افراز V به دو مجموعه X و Y (ناتهی) به این صورت است که:

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


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



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

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

    پس:

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



    گراف دو بخشی کامل:

    گراف دو بخشی کامل یک گراف دو بخشی است که مجموع رئوس آن به دو مجموعه X و Y چنان افراز شده است و هر راس در ان به هر راس وصل شده است. گراف دو بخشی کامل را با نماد نشان می دهند که در آن m تعداد عناصر مجموعه X و n تعداد عناصر مجموعه Y است.



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





    • قضیه: در گراف دو بخشی کامل همواره داریم: که در آن q اندازه گراف مذکور است.

    برهان:
    می دانیم گراف دارای m راس در یک مجموعه و n راس در مجموعه ای دیگر است.
    تعداد کل راس ها P=m+n می باشد(مرتبه گراف). اما برای یافتن تعداد یالهای گراف دو بخشی کامل ابتدا تعداد کل یالهای یک [فقط کاربران عضو می توانند لینک ها را ببینند. ] از مرتبه P=m+n را محاسبه کرده سپس تعداد کل یالهایی که راس های دو مجموعه را در خود دو مجموعه به هم وصل می کند از آن کم می کنیم. داریم:








    • قضیه: اگر G یک گراف ساده و دو بخشی از مرتبه p و اندازه q باشد آنگاه:

    برهان:
    چون گراف دو بخشی است مطابق قضیه قبل حداکثر یال آن برابر است با:
    که m تعداد یال بخش X و n تعداد یال بخش Y است.(بیشترین تعداد یال مربوط به زمانی است که گراف، دو بخشی کامل باشد).
    از طرفی می دانیم که: پس: , داریم:

    چون u آهنگ تغییرات تعداد یال را نشان می دهد و پس از نتیجه می شود که:
    ضمنا" می دانیم که:

    پس بیشترین مقدار u در نقطه اتفاق می افتد، یعنی:

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

    هر گراف که دارای راس باشد که و یکی از رئوس از درجه ی و بقیه از درجه ی سه باشند، را یک گراف چرخ می نامیم- مانند مثال های زیر:

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


    • تذکر: از حساب دیفرانسیل و انتگرال به یاد داریم که بازه ی باز مجموعه همه اعداد حقیقی بین دو عدد a و b(که شامل خود a و b نمی شود) است.

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

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


    نحوه تشخیص گراف بازه ای:
    سوالی که پیش می آید این است که چگونه می توان تشخیص داد که یک گراف بازه ای است یا نه؟
    به عنوان مثال می خواهیم تحقیق کنیم که آیا این گراف بازه ای است یا نه:

    سعی می کنیم بازه هایی را بیابیم که گراف متناظر آنها (گراف بازه ای آنها) به این صورت باشد.
    5 بازه زیر را در نظر می گیریم:

    (دقت شود که دو بازه a و b نباید اشتراک داشته باشند)
    مشاهده می شود گراف متناظر با این بازه ها به صورت گراف داده شده است پس این گراف بازه ای است.

    حال به این نمونه توجه کنید. می خواهیم بازه ای بودن این گراف را بررسی کنیم:

    قبل از بررسی کردن به توضیحات زیر توجه کنید:

    • در حالت کلی می توان گفت هر گراف دلخواه دارای یک دور از مرتبه 4 گراف بازه ای نمی باشد.

    برهان
    فرض می کنیم دور مرتبه 4 مقابل خود یک گراف یا قسمتی از یک گراف باشد:

    نشان می دهیم این گراف و یا گرافی شامل این دور بازه ای نمی باشد. به برهان خلف اگر این گراف یا گراف شامل ایت دور بازه ای باشد:
    روی محور اعداد حقیقی برای هر یک از راس ها بازه ای به صورت زیر در نظر می گیریم:
    چون a با b مجاور است باید روی محور اعداد بازه های متناظر با این دو راس دارای اشتراک باشند مطابق شکل:

    از طرفی c نیز با b مجاور است و با a مجاور نمی باشد پس بازه متناظر با c با بازه b اشتراک دارد ولی با بازه متناظر a اشتراک ندارد. مطابق شکل:

    حال چون d هم با a و هم با c مجاور است پس بازه متناظر با راس d باید به گونه ای اشد که هم به a و هم به c اشتراک داشته باشد و این تناقض است چرا که در این صورت d با b هم اشتراک پیدا می کند در حالی که از b به d یالی رسم نشده است.

    پس فرض خلف باطل و حکم برقرار است.


    پس در این گراف چون abcd یک دور با طول 4 است بنابر دلایل ذکر شده بازه ای نمی باشد.


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

    به عنوان مثال گراف زیر دارای حفره نمی باشد ولی در عین حال بازه ای نیز نمی باشد:


    • یادآوری(تعریف حفره): در گراف ها هر چهار ضلعی یا n ضلعی (n>3) که بدون قطر باشد را یک حفره می گوییم.

    به عنوان مثال در گراف قبلی به صورت:

    abcd یک حفره محسوب می شود و لذا گراف همان طور که گفته شد بازه ای نمی باشد.
    گرافها و ساختار دادهها

    هر گراف را میتوان با یک ماتریس نمایش داد ، که به آن ماتریس مجاورت گراف گویند. در این روش از آرایه هااستفاده میکنیم.این ماتریس به تعداد راسهای گراف دارای سطر و ستون است.وعدد 1 نشان دهنده وجود یک یال بین دو راس و عدد 0 نشان دهنده عدم وجود ارتباط بین دو راس است.یعنی ماتریس ما شامل دو عدد صفر و یک است. با استفاده از این ماتریس میتوان رئوسی را که با یک راس در ارتباطاند و نیز رئوسی را که با هیچ راس دیگری ارتباط ندارند رامشخص کرد.

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



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

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

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





    درخت «گراف»




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

    تعریف ها:

    یک درخت از شرایط زیر پیروی می کند.


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



    اگر یک جنگل با n راس باشد آن گاه از شرایط زیر پیروی می کند:

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


    مثال:

    در شکل درختی با 6 راس و 5 یال وجود دارد مقدار یالها برابر 5 = 1- 6 است. و بین دو راس 2 و 6 دقیقاً یک مسیر وجود دارد که عبارت است از 6-5-4-2

    بیشتر بدانیم:

    درخت مولد گراف مانند G بزرگترین گراف درختی مانند T در G است که با افزودن یک یال از درخت بودن خارج می شود و واضح است اگر یک گراف n راس و m یال داشته باشد آن گاه درخت مولد n-1 یال داشته و باید m >= n-1 باشد.
    تعداد درخت های مولد متمایز برای گراف کامل با n راس برابر است. این قضیه به قضیه کایلی معروف است.
    تعداد درخت هایی که با n راس با درجات می توان ساخت برابر مقدار زیر است:





  2. # ADS
    نشان دهنده تبلیغات برای شما
    تاریخ عضویت
    همین الان !
    محل سکونت
    توی انجمن
    نوشته ها
    یه عالمه



     

مجوز های ارسال و ویرایش

  • شما نمیتوانید موضوع جدیدی ارسال کنید
  • شما امکان ارسال پاسخ را ندارید
  • شما نمیتوانید فایل پیوست کنید.
  • شما نمیتوانید پست های خود را ویرایش کنید
  •  
طراحی توسط: مرجع حرفه ای ویبولتین
انجمن دانشجویان ایران در یک سال اخیر به وضعیت مقاله در ایران کمک شایانی کرده است.این انجمن هم اکنون به مرجع مقاله در ایران تبدیل شده است. از بودن در جمع صمیمی دانشجویان ایرانی لذت ببرید.
ارتباط با ما در مورد انجمن ارتباط با در مورد مارکت ورود به مدیریت انجمن ایمیل مدیریت انجمن : irdoc.net@gmail.com
تلفن همراه: 0933333333
تلفن ثابت: 00000000-0511

آیدی یاهو:
انتخاب كاربر برتر ماه انجمن دانشجويان ايران