پایه عکاسی مونوپاد
مدرسان شریف ۹۳
سایت علمی دانشجویان ایران
دانـلـود مقـالات آی اس آی 
از تـمامـی پـایـگـاه های آنـلایــن، بـه سـادگـی!
هنر ایران پژوهش (توسعه)
در حال نمایش 1 تا 5 از مجموع 5

تاپیک: نظریه گراف

  1. Top | #1

    • مدیر ارشد سابق سایت
    • تاریخ عضویت
      01-Jan-2006
    • پست‌ها
      4,328
    • سپاس
      506
    • 4,308 تشکر در 1,923 پست
    • قدرت امتیاز دهی
      19
    • امتیاز
      30

    لبخند نظریه گراف

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


    تا که بودیم نبودیم کسی
    کشت ما را غم بی همنفسی
    تا که رفتیم همه یار شدند
    خفته ایم و همه بیدارشدند
    قدر آینه بدانیم چون هست
    نه در آن وقت که اقبال شکست


    سلام دوران خوش سربازی

    ترنسیس
  2. 4 کاربر از H A M E D برای پست مفید تشکر نموده اند:


  3. Top | #2

    • مدیر ارشد سابق سایت
    • تاریخ عضویت
      01-Jan-2006
    • پست‌ها
      4,328
    • سپاس
      506
    • 4,308 تشکر در 1,923 پست
    • قدرت امتیاز دهی
      19
    • امتیاز
      30

    پیش فرض

    گراف کامل


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



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



    یک گراف کامل یک گراف منتظم از درجه n-1 است.


    تا که بودیم نبودیم کسی
    کشت ما را غم بی همنفسی
    تا که رفتیم همه یار شدند
    خفته ایم و همه بیدارشدند
    قدر آینه بدانیم چون هست
    نه در آن وقت که اقبال شکست


    سلام دوران خوش سربازی

  4. 4 کاربر از H A M E D برای پست مفید تشکر نموده اند:


  5. Top | #3

    • مدیر ارشد سابق سایت
    • تاریخ عضویت
      01-Jan-2006
    • پست‌ها
      4,328
    • سپاس
      506
    • 4,308 تشکر در 1,923 پست
    • قدرت امتیاز دهی
      19
    • امتیاز
      30

    پیش فرض

    گراف دو بخشی
    -----------------------

    گراف دو بخشی:
    مفهوم شهودی:
    فرض کنید در یک شرکت صنعتی تعدادی شغل بدون متصدی می باشند و تعدادی متقاضی برای این مشاغل اعلام آمادگی نموده اند. حال این سوال مطرح می شود که آیا می توان به هر متقاضی شغلی متناسب او اختصاص داد؟
    برای حل چنین مسئله ای که به مسئله ی تخصیص موسوم است، با استفاده از گراف می توان وضعیت های خاص را پیاده سازی نمود. بدین ترتیب که گروهی که متقاضی مشاغل هستند در مجموعه ای به نام 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-منتظم داریم:

    پس:

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


    تا که بودیم نبودیم کسی
    کشت ما را غم بی همنفسی
    تا که رفتیم همه یار شدند
    خفته ایم و همه بیدارشدند
    قدر آینه بدانیم چون هست
    نه در آن وقت که اقبال شکست


    سلام دوران خوش سربازی

  6. 4 کاربر از H A M E D برای پست مفید تشکر نموده اند:


  7. Top | #4

    • مدیر ارشد سابق سایت
    • تاریخ عضویت
      01-Jan-2006
    • پست‌ها
      4,328
    • سپاس
      506
    • 4,308 تشکر در 1,923 پست
    • قدرت امتیاز دهی
      19
    • امتیاز
      30

    پیش فرض گراف

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


    تا که بودیم نبودیم کسی
    کشت ما را غم بی همنفسی
    تا که رفتیم همه یار شدند
    خفته ایم و همه بیدارشدند
    قدر آینه بدانیم چون هست
    نه در آن وقت که اقبال شکست


    سلام دوران خوش سربازی

  8. 4 کاربر از H A M E D برای پست مفید تشکر نموده اند:


  9. Top | #5

    • مدیر ارشد سابق سایت
    • تاریخ عضویت
      01-Jan-2006
    • پست‌ها
      4,328
    • سپاس
      506
    • 4,308 تشکر در 1,923 پست
    • قدرت امتیاز دهی
      19
    • امتیاز
      30

    پیش فرض نظریه گراف

    نظریه گراف دانشی است که درباره موجوداتی به نام گراف بحث می‌کند. به صورت مرئی گراف «چیزی» است شامل تعدادی رأس که با یالهایی به هم وصل شده‌اند. تعریف دقیق‌تر نظریهٔ گراف به این صورت است که گراف مجموعه‌ای از رأس‌ها است که توسط خانواده‌ای از زوج‌های مرتب که همان یال‌ها هستند به هم ربط داده شده‌اند.

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

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

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


    تا که بودیم نبودیم کسی
    کشت ما را غم بی همنفسی
    تا که رفتیم همه یار شدند
    خفته ایم و همه بیدارشدند
    قدر آینه بدانیم چون هست
    نه در آن وقت که اقبال شکست


    سلام دوران خوش سربازی

  10. 4 کاربر از H A M E D برای پست مفید تشکر نموده اند:


اطلاعات تاپیک

کاربران حاضر در این تاپیک

در حال حاضر 1 کاربر در حال مشاهده این تاپیک هستند. (0 عضو و 1 مهمان)

این مطلب را به اشتراک بگذارید

قوانین ارسال

  • شما نمی‌توانید تاپیک جدید ارسال کنید.
  • شما قادر به ارسال پاسخ نیستید .
  • شما نمی‌توانید فایل ارسال کنید.
  • شما نمی‌توانید پست ‌های خود را ویرایش کنید.
  •  
دانشجو در شبکه های اجتماعی
افتخارات دانشجو
لینک ها
   
سایت برگزیده مردمی در چهارمین و پنجمین جشنواره وب ایران
سایت برگزیده مردمی در چهارمین و پنجمین جشنواره وب ایران
به دانشجو امتیاز دهید:

آپلود مستقیم عکس در آپلودسنتر عکس دانشجو

توجه داشته باشید که عکس ها فقط در سایت دانشجو قابل نمایش می باشند.

Search Engine Friendly URLs by vBSEO 3.6.1