گراف نقشه راه‌ها

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

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

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

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

منابع

Kenneth H, Rosen (1998). "Graphs". Discrete Mathematics and its Applications. SIGS Reference Library (به انگلیسی). William C Brown Pub; 4th edition. Retrieved 2007. {{cite book}}: Check date values in: |بازبینی= (help)