بسم الله الرحمن الرحیم

 

 

تعریف
گراف

گراف از لحاظ لغوی به معانی نمودار است و روی مجموعه های گسسته قابلیت تعردف دارد گراف ها ممکن است بر دو نوع متناهی یا نامتناهی باشند آن دسته از گراف ها که دارای تعداد یال یا رأس نامتناهی اند جزء گراف های نامتناهی لحاظ میشوند در تعریف دقیق گراف ساده ی G داریم گراف G زوج مرتبی مانند (V,E) است که در آن Vمجموعه ای ناتهی ومتناهی است وهرعضو E زیرمجموعه ای دوعضوی از Vاست هر عضوV را رأس وهر عضو Eرا یال گراف G گوییم از تعریف گراف ساده میتوان تیجه گرفت که بین هر دو رأس متمایز در گراف تنها یک یال وجود دارد اما گاهی نیاز است که بین دو رآس تعداد یال بیشتری قرار گیرد این نوع از گراف ها تحت عنوان گراف های چندگانه شناخته میشوند به این ترتیب میتوان گفت مجموعه ای ناتهی از رئوس ویال ها که این رأس ها بوسیله ی یال هایی بهم مرتبط میشوند وارتباط هر راس با راس دیگر بوسیله ی یال مشروط براین است که رابطه ی موردنظر بین دو راس برقرار باشد تعریف شهودی مناسبی برای گراف بنظر میرسد در تعریف گراف محل قرارگیری رأس ها ,شکل هندسی گراف, ونحوه ی اتصال رأس ها بهم وطول یال ها مورد اهمیت نیست بلکه تنها موضوع مورد توجه این است که کدام رأس ها با یکدیگر اتباط دارند.بابسط این تعریف مفهوم گراف درسایرعلوم از جمله پزشکی, مهندسی, کامپیوتر,  زیست شناسی, مخابرات, کدگذاری, آمار, ژنتیک و...مورد استفاده قرار میگیرد.اصلی ترین کاربرد گراف در سایر علوم استفاده از آن جهت مدلسازی های موردنیاز به منظور بررسی دقیق تر پدیده ها در مقیاسی مناسب و شکلی ساده است.