X
تبلیغات
نماشا
رایتل

علم ریاضی

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

تعریف گراف

تعاریف گراف

یک گراف شامل دو مجموعه است؛ مجموعه غیر تهی از گره ها یا رئوس (vertex) و مجموعه ای از یال ها (edge) که راس ها را به هم متصل می کنند.

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

به هر راس یا هر یال گراف نامی اختصاص داده می شود.

یک گراف تهی (null graph) گرافی است که تنها شامل راس است و مجموعه یال های آن تهی است یعنی یالی ندارد.

جهت

یک گراف می تواند به دو شکل جهتدار(directed) یا غیرجهتدار (undirected) باشد.

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

تعاریف گراف

یک گراف شامل دو مجموعه است؛ مجموعه غیر تهی از گره ها یا رئوس (vertex) و مجموعه ای از یال ها (edge) که راس ها را به هم متصل می کنند.

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

به هر راس یا هر یال گراف نامی اختصاص داده می شود.

یک گراف تهی (null graph) گرافی است که تنها شامل راس است و مجموعه یال های آن تهی است یعنی یالی ندارد.

جهت

یک گراف می تواند به دو شکل جهتدار(directed) یا غیرجهتدار (undirected) باشد.

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

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