منو
 کاربر Online
450 کاربر online

تعریف گراف

تازه کردن چاپ
علوم ریاضی > علو م رایانه
(cached)



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


هر مفهومی هنگامی معنا می پذیرد که به درستی تعریف گردد:
لذا گراف را به صورت زیرتعریف می کنیم:
گراف ساده را به صورت زوج مرتب تعریف می گردد که در آن مجموعه ای از رئوس یا تقاطع ها می باشد ( مجموعه ای متناهی و غیر تهی ) و مجموعه ای است از زوج های نامرتب و نامساوی از عناصریعنی


نکته

چون در تعریف آمده " زوج نامرتب " پس

به عنوان نمونه می تواند باشد که
شکل آن به صورت زیر می باشد.
img/daneshnameh_up/8/8b/mco0046a.jpg

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

گرافهای نامتناهی

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

گراف عمومی

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



گراف چندگانه

اگر بپذیریم که علاوه بر طوقه،‌ میان دو راس بیش از یک یال داشته باشیم آنگاه گراف چند گانه خواهد بود.
مانند
img/daneshnameh_up/c/c7/mco0046b.jpg

که و به صورت زیر تعریف می شوند:


که:


گراف جهت دار

اگر شرط نامرتب بودن اعضای را به زوج مرتب تبدیل کنیم گراف جهت دار خواهد بود یعنی

در این صورت اگر آنگاه یک نمونه از گراف جهت دار مانند زیر است:
img/daneshnameh_up/1/1e/mco0046c.jpg



توضیح کامل تر گراف های جهت دار در مطلب مربوطه داده خواهد شد.

نکته

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

نکته

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

مجاورت

دو راس از مجموعه رئوس را مجاور گویند هر گاه

یعنی یالی بین موجود باشد. به مجاور، همسایه نیز می گویند.
مانند مثال زیر که با و با مجاور یا همسایه بوده ولی با مجاور نیست.
img/daneshnameh_up/1/1b/mco0046d.jpg


پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0062.pdf

همچنین ببینید



تعداد بازدید ها: 18577


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..