گراف جهت دار در مقابل گراف بدون جهت
گراف یک ساختار ریاضی است که از مجموعه ای از رئوس و یال ها تشکیل شده است. یک گراف مجموعه ای از اشیاء را نشان می دهد (که توسط رئوس نمایش داده می شوند) که از طریق برخی پیوندها (که توسط یال ها نشان داده می شوند) به هم متصل شده اند. با استفاده از نمادهای ریاضی، یک نمودار را می توان با G نشان داد، که در آن G=(V, E) و V مجموعه رئوس و E مجموعه یال ها است. در یک گراف بدون جهت، هیچ جهتی با لبه هایی که رئوس را به هم متصل می کنند، وجود ندارد. در یک گراف جهت دار یک جهت مرتبط با یال هایی وجود دارد که راس ها را به هم متصل می کنند.
گراف بدون جهت
همانطور که قبلاً ذکر شد، گراف بدون جهت گرافی است که در آن هیچ جهتی در لبه‌هایی که رئوس نمودار را به هم پیوند می‌دهند وجود ندارد.شکل 1 یک گراف بدون جهت را با مجموعه ای از رئوس V={V1, V2, V3} نشان می دهد. مجموعه ای از یال ها در نمودار بالا را می توان به صورت V={(V1, V2), (V2, V3), (V1, V3)} نوشت. همچنین می توان اشاره کرد که هیچ چیزی مانع از نوشتن مجموعه یال ها به صورت V={(V2, V1), (V3, V2), (V3, V1)} نیست زیرا لبه ها جهت ندارند. بنابراین یال ها در یک گراف غیر جهت دار جفت مرتب نیستند. این ویژگی اصلی یک گراف بدون جهت است. نمودارهای بدون جهت را می توان برای نشان دادن روابط متقارن بین اشیایی که با رئوس نمایش داده می شوند استفاده کرد. به عنوان مثال، یک شبکه جاده ای دو طرفه که مجموعه ای از شهرها را به هم متصل می کند، می تواند با استفاده از یک نمودار غیر جهت دار نمایش داده شود. شهرها را می توان با رئوس در نمودار نشان داد و یال ها نشان دهنده جاده های دو طرفه هستند که شهرها را به هم متصل می کنند.
گراف جهت دار
گراف جهت دار گرافی است که در آن یال هایی در نمودار که رئوس را به هم پیوند می دهند دارای جهت هستند. شکل 2 یک گراف جهت دار را با مجموعه رئوس V={V1, V2, V3} نشان می دهد. مجموعه ای از یال ها در نمودار بالا را می توان به صورت V={(V1, V2), (V2, V3), (V1, V3)} نوشت. یال ها در یک گراف بدون جهت، جفت مرتب شده اند. به طور رسمی، یال e در یک گراف جهت دار را می توان با جفت مرتب شده e=(x, y) نشان داد که در آن x راس است که مبدا، منبع یا نقطه اولیه یال e نامیده می شود و راس y پایانه نامیده می شود. ، راس پایانی یا نقطه پایانی. به عنوان مثال، یک شبکه جاده ای که مجموعه ای از شهرها را با استفاده از جاده های یک طرفه به هم متصل می کند، می تواند با استفاده از یک نمودار غیر جهت دار نمایش داده شود. شهرها را می توان با رئوس در نمودار نشان داد و لبه های جهت دار نشان دهنده جاده هایی است که شهرها را با توجه به جهتی که ترافیک در جاده جریان دارد، به هم متصل می کنند.
تفاوت بین گراف جهت دار و گراف غیر جهت دار چیست؟
در یک گراف جهت دار، یال یک جفت مرتب است، که در آن جفت مرتب نشان دهنده جهت یالی است که دو راس را به هم پیوند می دهد. از طرف دیگر، در یک گراف بدون جهت، یک یال یک جفت نامرتب است، زیرا هیچ جهتی با یک یال وجود ندارد. نمودارهای بدون جهت را می توان برای نشان دادن روابط متقارن بین اشیاء استفاده کرد. درجه درون و برون درجه هر گره در یک گراف بدون جهت برابر است اما این برای یک گراف جهت دار صادق نیست. هنگام استفاده از ماتریس برای نشان دادن یک گراف بدون جهت، ماتریس همیشه به یک گراف متقارن تبدیل می شود، اما این برای گراف های جهت دار صادق نیست. یک گراف بدون جهت را می توان با جایگزین کردن هر یال با دو یال جهت دار که در جهت مخالف هستند به یک گراف جهت دار تبدیل کرد. با این حال، امکان تبدیل یک گراف جهت دار به یک گراف غیر جهت دار وجود ندارد.
