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

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

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

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

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

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

منابع

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)