گراف و انواع آن

گراف یک مجموعه از نقاط (که رئوس یا گره‌ها نامیده می‌شوند) و خطوطی است که بین این نقاط قرار دارند (که یال‌ها یا لبه‌ها نامیده می‌شوند). این خطوط نشان دهندهٔ ارتباط بین نقاط هستند. گراف می‌تواند به صورتی باشد که این خطوط جهت داشته باشند (یعنی یک جهت خاص داشته باشند) یا به صورتی که جهت نداشته باشند. همچنین می‌تواند وزن‌دار یا بدون وزن باشد، به این معنی که هر خط می‌تواند دارای یک عدد (وزن) باشد یا نباشد.

کاربرد گراف ها در کجاست؟

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

انواع گراف

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

• گراف ساده

گراف ساده یک گراف بدون یال تکراری و بدون حلقه است. یعنی هر دو راس (نقطه) در گراف ساده حداکثر یکبار با یک یال به هم متصل هستند. به عبارت دیگر، هیچ دو یال در گراف ساده نمی‌توانند بین دو راس یکسان قرار داشته باشند.

• گراف جهت‌ دار

گراف جهت‌دار، گرافی است که هر یال آن دارای جهت خاصی است. به عبارت دیگر، هر یال در گراف جهت‌دار دارای یک سمت است که از راسی شروع می‌شود و به راس دیگری ختم می‌شود. به همین دلیل، گراف جهت‌دار گاهی به عنوان گراف گراف جهت‌دار یا دی‌گراف (Digraph) نیز نامیده می‌شود.

• گراف تهی

گراف تهی، گرافی است که هیچ یالی ندارد. به عبارت دیگر، هیچ دو راسی در گراف تهی با یکدیگر متصل نیستند. گراف تهی ممکن است شامل یک یا چند راس باشد، اما هرگز شامل یال نیست.