X
تبلیغات
پیکوفایل
رایتل

علم ریاضی

این وبلاگ جهت استفاده علاقمندان به ریاضی ایجاد شده است.
جمعه 29 دی‌ماه سال 1391

نظریه گراف


تعریف

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

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

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

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

گراف‌ها و ساختار داده‌ها

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

نظرات (0)
نام :
ایمیل : [پنهان می ماند]
وب/وبلاگ :
برای نمایش آواتار خود در این وبلاگ در سایت Gravatar.com ثبت نام کنید. (راهنما)