۱۳۹۹/۰۴/۱۹

گراف Graph در ساختمان داده ها

گراف Graph ۱۳۹۸/۰۴/۲۶

گراف Graph

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

1-مجموعه ای از عناصر که گره یا راس vetex نام دارند و از مجموعه ای از یال ها یا Edge تشکیل شده اند

Graph-graph-GRAPH-گراف-ساختمان داده ها-برنامه نویسی-علوم کامپیوتر

مثال :گرافی مانند G که تشکیل شده باشد V={a,b,c,d} و edge های به این شکل E={{a,b},{b,c},{a,c}{d,b},{a,d}}

این گراف شچهار گره و پنج لبه است

گراف-لبه-گره-گراف با چهار گره و  لبه4 5

بطور کلی گراف ها دو نوع هستند

1-گراف های جهت دار

2-گراف های غیر جهت دارد.در گراف های غیر جهت دار یال ها جهت ندارند.یعنی یالی که bرا به a وصل میکنند همان یالی است که a را به b وصل میکنند.و با شکل های زیر نمایش داده می شوند.

graph-گراف-ساختمان داده ها-ساختمان داده

اما در گراف های جهت دار بالی که a را به b وصل میکند با یالی که b را به a وصل میکند متفاوت است

گراف Graph

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

طوقه یا حلقه بالی است که راس انتهایی آن یکسان باشد.

گراف ساده یا simple گرافی است که یال موازی یا حلقه ندارد.

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

گراف کامل یا complet گرافی است که بین هر دو راس آن یک یال وجود دارد.اگر n راس داشته باشیم به آن kn میگوییم.

گراف کامل n راس دارای چند بال میباشد.n(n-1)/2

در گراف جهت دار کامل n در n-1 بال وجود دارد. n(n-1)

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

گراف مسیر patch

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

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

تعریف درخت:گراف همبندی هستند که سیکل یا دور ندارند.در هر درخت n راس و e یال داریم n=e+1

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

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

مکمل یک گراف :برای پیدا کردن مکمل یک گراف راس های یک گراف تغییر نمیکنند.یال هایی که دجود دارند حذف میشوند.و یال هایی که وجود ندارند رسم میشوند.

گراف تهی یا گراف نال گرافی است که راس دارد اما یال ندارد.در واقع مکمل گراف کامل است.

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

در هر گراف غیر جهت دار تعداد رئوس از درجه فرد زوج است.

گره منبع گره ای است که درجه ورودی آن صفر است .و گره چان گره ای هست که درجه خروجی آن صفر است.

در گراف جهت دار جمع درجات خروجی برابر است با تعداد یال ها

در یک گراف بیشترین درجه راس های آن را درجه خود گراف می گویند.

 


رای :

گراف-Graph-ساختمان داده ها-یال-edge-vetex

ارسال نظر
Copyright © All right reserved.