23-12-2024, 07:53 PM
در ریاضیات و علوم کامپیوتر، گراف (Graph) ساختاری است که مجموعه ای از نود ها ( یا رأس ها و نقاط و یال ها و لبه ها را شامل می شود.نود ها یا
رأس ها نشان دهنده اشیاء یا عناصر هستند و یال ها نشان دهنده روابط بین این عناصر هستند.
تعریف گراف :هر گراف را به صورت )G = )V,Eکه از مجموعه ناتهی از رأس ها )V)Vertex و مجموعه ای از یال های )E)Edge تشکیل شده است.
انواع گراف
جهت دار :
ترتیب گره ها در زوج مرتب اهمیت دارد.
2-غیرجهت دار :
گرافی است که درآن جای دو رأس در مجموعه یالها اهمیت نداشته باشد.
گراف پوچ :گرافی است که مجموعه یال های آن تهی باشد به عبارت دیگر یعنی فقط رأس ها در آن وجود دارند.
گره مجاور: گره X مجاور گره Y است اگر بین آنها یک یال وجود داشته باشد .
راس منفرد (منزوی) : رأسی که هیچ رأس مجاوری نداشته باشد.
طوقه (Loop ) : یالی که گره ابتدا و انتها آن یکی باشد.
گراف چندگانه (Multi Graph) : گرافی است که در آن داشتن یال های چندگانه و طوقه مجاز باشد.
گراف برچسب دار: گرافی است اطلاعاتی به یال های آن نسبت داده شده است.
گراف وزن دار : گرافی است که به هر یال آن یک مقدار عددی غیر منفی نسبت داده شده است.
گراف کامل (complete Graph) :گرافی است که بین هر دو رأس آنیک یال وجود دارد به عبارتی گرافی است که حداکثر تعداد یال
ها را دارد.
درجه گره : درجه گره برابر است با مجموع تعداد یال های متصل به یک گره .
درجه گراف : برابر است با بزرگترین درجه گره های گراف .
درجه ورودی : به تعداد یال های وارد شده به یک رأس در یک گراف جهت دار درجه ورودی آن رأس می گویند.
درجه خروجی : به تعداد یال های خارج شده از یک رأس در یک گراف جهت دار درجه خروجی آن رأس می گویند.
مسیر: مجموعه ای از یال های پشت سر هم که دو رأس را به هم وصل می کنند.
مسیر ساده : مسیری است که همه رأس های آن مجزا باشد به جز اولی و آخری .
طول مسیر : تعداد یال های موجود در مسیر است.
حلقه یا سیکل : مسیر ساده ای که گره اول و آخر آن یکی باشد.
گره چاه : گره ای که درجه خروجی صفر و درجه ورودی
مثبت داشته باشد را گره چاه می گوییم.
گره منبع : گره ای که درجه خروجی مثبت و درجه ورودی
صفر داشته باشد را گره منبع می گوییم.
گراف همبند و غیر همبند :
گراف همبند: یک گراف همبند گرافی است که درآن از هر
رأس می توان به تمام رأس های دیگراز طریق یال ها رسید .
به عبارت دیگر برای هر دو رأس دلخواه در گراف یک مسیر
از یال ها وجود دارد که این دو رأس را به هم وصل کند .
گراف ناهمبند : در گراف ناهمبند ممکن است بعضی رأس ها
به یکدیگر متصل نباشند به عبارت دیگر برای بعضی رأس ها
هیچ مسیری برای رسیدن به دیگر رأس ها وجود ندارد و
گراف به چند بخش مجزا تقسیم شود.
گراف جهت دار همبند قوی و ضعیف :
گراف همبند قوی جهت دار : در این نوع گراف بین هر جفت از رأس ها مسیر های جهت دار به طور کامل در هر دو جهت وجود دارند.یعنی اگر از یک رأس
شروع کنیم می توانیم به راس های دیگر برسیم.
گراف همبند ضعیف جهت دار: به گرافی گفته می شود که در آن جهت یال ها نادید گرفته شود به عبارت دیگر در این گراف هیچ گونه مسیری از یک رأس به
رأس های دیگر وجود نداشته باشد.
تفاوت درخت با گراف
1- درخت یک گراف بدون حلقه است که یک گره خاص بنام ریشه دارد و از ریشه ی درخت یک مسیر ساده به گره های دیگر وجود دارد. پس میتوان گفت که
درخت یک گراف متصل است.
2- پیمایش درخت از ریشه به گرههای دیگر صورت میپذیرد. پس میتوان گفتن ه درخت یک گراف جهت دار است .
ما به دو روش می توانیم گراف را نمایش دهیم :
1- ماتریس مجاورت 2- لیست مجاورت
1 – ماتریس مجاورت : ماتریس مجاورت یا همجواری یک گراف با n رأس آرایه ای n × n است که به صورت زیر تعریف می شود .
نکته1: ماتریس مجاورتی یک گراف بدون جهت حتما متقارن است و
می توان برای نگهداری آن از ماتریس بالا یا پایین مثلثی استفاده کرد.
نکته2:ماتریس مجاورت یا همجواری گراف جهت دار لزوما متقارن نیست.
نکته3: در ماتریس مجاورتی برای گراف جهت دار مجموع سطری درجه خروجی و مجموع ستونی درجه ورودی رأس نظیر یاسطر یا
ستون را نشان می دهد ولی برای گراف بدون جهت مجموع سطری یا ستونی درجه هر رأس نظیر است.
نکته 4:تعداد « 1» ها در ماتریس مجاورتی گراف بدون جهت دو برابر یال ها و در گراف جهت دار برابر با یال ها است .
نکته5: از نقاط قوت ماتریس مجاورتی می توان به سرعت دسترسی به مجاور بودن یا نبودن دو گره اشاره کرد که با زمان )O)1انجام
می شود.
نکته 6:با استفاده از ماتریس مجاورتی همه الگوریتم های لازم برای گراف با n رأس با زمان )O)n² انجام می شود
لیست مجاورت :
یکی از ایراد های روش ماتریس مجاورتی مشکل حذف و اضافه کردن گره هاست زیرا در این صورت اندازه ماتریس بایدتغییر کند. و
دلیل دیگر این است که اگر تعداد یال ها کم باشد(مثلا در گرافی n رأس تعداد یال ها n یا logn n)اباشد نگاه ماتریس خلوت به
وجود می آید و فضای زیادی اشغال میشود.
نکته 1: در یک گراف بدون جهت با n رأس و e یال نباز به آرایه ای به طول n و 2eگره لیست پیوندی است.
نکته2:در یک گراف جهت دار با n رأس و e یال نیاز به آرایه ای به طول n و e گره لیست پیوندی است.
نکته 3:اگر تعدا رأس ها گراف n باشد تعداد کل یال ها ) O)n+e تعیین می شود.
نکته 4:درجه هر رأس را در یک گراف بدون جهت را می توان با شمارش تعداد گره های آن در لیست مجاورتی تعیین نمود
رأس ها نشان دهنده اشیاء یا عناصر هستند و یال ها نشان دهنده روابط بین این عناصر هستند.
تعریف گراف :هر گراف را به صورت )G = )V,Eکه از مجموعه ناتهی از رأس ها )V)Vertex و مجموعه ای از یال های )E)Edge تشکیل شده است.
انواع گراف
جهت دار :
ترتیب گره ها در زوج مرتب اهمیت دارد.
2-غیرجهت دار :
گرافی است که درآن جای دو رأس در مجموعه یالها اهمیت نداشته باشد.
گراف پوچ :گرافی است که مجموعه یال های آن تهی باشد به عبارت دیگر یعنی فقط رأس ها در آن وجود دارند.
گره مجاور: گره X مجاور گره Y است اگر بین آنها یک یال وجود داشته باشد .
راس منفرد (منزوی) : رأسی که هیچ رأس مجاوری نداشته باشد.
طوقه (Loop ) : یالی که گره ابتدا و انتها آن یکی باشد.
گراف چندگانه (Multi Graph) : گرافی است که در آن داشتن یال های چندگانه و طوقه مجاز باشد.
گراف برچسب دار: گرافی است اطلاعاتی به یال های آن نسبت داده شده است.
گراف وزن دار : گرافی است که به هر یال آن یک مقدار عددی غیر منفی نسبت داده شده است.
گراف کامل (complete Graph) :گرافی است که بین هر دو رأس آنیک یال وجود دارد به عبارتی گرافی است که حداکثر تعداد یال
ها را دارد.
درجه گره : درجه گره برابر است با مجموع تعداد یال های متصل به یک گره .
درجه گراف : برابر است با بزرگترین درجه گره های گراف .
درجه ورودی : به تعداد یال های وارد شده به یک رأس در یک گراف جهت دار درجه ورودی آن رأس می گویند.
درجه خروجی : به تعداد یال های خارج شده از یک رأس در یک گراف جهت دار درجه خروجی آن رأس می گویند.
مسیر: مجموعه ای از یال های پشت سر هم که دو رأس را به هم وصل می کنند.
مسیر ساده : مسیری است که همه رأس های آن مجزا باشد به جز اولی و آخری .
طول مسیر : تعداد یال های موجود در مسیر است.
حلقه یا سیکل : مسیر ساده ای که گره اول و آخر آن یکی باشد.
گره چاه : گره ای که درجه خروجی صفر و درجه ورودی
مثبت داشته باشد را گره چاه می گوییم.
گره منبع : گره ای که درجه خروجی مثبت و درجه ورودی
صفر داشته باشد را گره منبع می گوییم.
گراف همبند و غیر همبند :
گراف همبند: یک گراف همبند گرافی است که درآن از هر
رأس می توان به تمام رأس های دیگراز طریق یال ها رسید .
به عبارت دیگر برای هر دو رأس دلخواه در گراف یک مسیر
از یال ها وجود دارد که این دو رأس را به هم وصل کند .
گراف ناهمبند : در گراف ناهمبند ممکن است بعضی رأس ها
به یکدیگر متصل نباشند به عبارت دیگر برای بعضی رأس ها
هیچ مسیری برای رسیدن به دیگر رأس ها وجود ندارد و
گراف به چند بخش مجزا تقسیم شود.
گراف جهت دار همبند قوی و ضعیف :
گراف همبند قوی جهت دار : در این نوع گراف بین هر جفت از رأس ها مسیر های جهت دار به طور کامل در هر دو جهت وجود دارند.یعنی اگر از یک رأس
شروع کنیم می توانیم به راس های دیگر برسیم.
گراف همبند ضعیف جهت دار: به گرافی گفته می شود که در آن جهت یال ها نادید گرفته شود به عبارت دیگر در این گراف هیچ گونه مسیری از یک رأس به
رأس های دیگر وجود نداشته باشد.
تفاوت درخت با گراف
1- درخت یک گراف بدون حلقه است که یک گره خاص بنام ریشه دارد و از ریشه ی درخت یک مسیر ساده به گره های دیگر وجود دارد. پس میتوان گفت که
درخت یک گراف متصل است.
2- پیمایش درخت از ریشه به گرههای دیگر صورت میپذیرد. پس میتوان گفتن ه درخت یک گراف جهت دار است .
ما به دو روش می توانیم گراف را نمایش دهیم :
1- ماتریس مجاورت 2- لیست مجاورت
1 – ماتریس مجاورت : ماتریس مجاورت یا همجواری یک گراف با n رأس آرایه ای n × n است که به صورت زیر تعریف می شود .
نکته1: ماتریس مجاورتی یک گراف بدون جهت حتما متقارن است و
می توان برای نگهداری آن از ماتریس بالا یا پایین مثلثی استفاده کرد.
نکته2:ماتریس مجاورت یا همجواری گراف جهت دار لزوما متقارن نیست.
نکته3: در ماتریس مجاورتی برای گراف جهت دار مجموع سطری درجه خروجی و مجموع ستونی درجه ورودی رأس نظیر یاسطر یا
ستون را نشان می دهد ولی برای گراف بدون جهت مجموع سطری یا ستونی درجه هر رأس نظیر است.
نکته 4:تعداد « 1» ها در ماتریس مجاورتی گراف بدون جهت دو برابر یال ها و در گراف جهت دار برابر با یال ها است .
نکته5: از نقاط قوت ماتریس مجاورتی می توان به سرعت دسترسی به مجاور بودن یا نبودن دو گره اشاره کرد که با زمان )O)1انجام
می شود.
نکته 6:با استفاده از ماتریس مجاورتی همه الگوریتم های لازم برای گراف با n رأس با زمان )O)n² انجام می شود
لیست مجاورت :
یکی از ایراد های روش ماتریس مجاورتی مشکل حذف و اضافه کردن گره هاست زیرا در این صورت اندازه ماتریس بایدتغییر کند. و
دلیل دیگر این است که اگر تعداد یال ها کم باشد(مثلا در گرافی n رأس تعداد یال ها n یا logn n)اباشد نگاه ماتریس خلوت به
وجود می آید و فضای زیادی اشغال میشود.
نکته 1: در یک گراف بدون جهت با n رأس و e یال نباز به آرایه ای به طول n و 2eگره لیست پیوندی است.
نکته2:در یک گراف جهت دار با n رأس و e یال نیاز به آرایه ای به طول n و e گره لیست پیوندی است.
نکته 3:اگر تعدا رأس ها گراف n باشد تعداد کل یال ها ) O)n+e تعیین می شود.
نکته 4:درجه هر رأس را در یک گراف بدون جهت را می توان با شمارش تعداد گره های آن در لیست مجاورتی تعیین نمود