Чилүүлэлттэй ба Чиглэлгүй график
График нь орой ба ирмэгүүдийн багцаас тогтсон математик бүтэц юм. График нь зарим холбоосоор (ирмэгээр дүрслэгдсэн) холбогдсон объектуудын багцыг (оройгоор дүрсэлсэн) илэрхийлдэг. Математик тэмдэглэгээг ашиглан графикийг 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 оройг төгсгөл гэж нэрлэдэг., төгсгөлийн орой эсвэл төгсгөлийн цэг. Жишээлбэл, нэг чиглэлтэй зам ашиглан олон хотыг холбосон замын сүлжээг чиглүүлээгүй график ашиглан дүрсэлж болно. Хотуудыг график дээрх оройгоор, чиглүүлсэн ирмэгүүд нь тухайн замд хөдөлгөөний урсгалын чиглэлийг харгалзан хотуудыг холбосон замыг төлөөлж болно.
Чилүүлэлттэй график болон чиглээгүй график хоёрын ялгаа нь юу вэ?
Чилтгэсэн графикт ирмэг нь эрэмбэлэгдсэн хос бөгөөд эрэмбэлэгдсэн хос нь хоёр оройг холбосон ирмэгийн чиглэлийг илэрхийлдэг. Нөгөө талаас, чиглүүлээгүй графикт ирмэгтэй холбоотой чиглэл байхгүй тул ирмэг нь эрэмбэлэгдээгүй хос юм. Чиглэлгүй графикийг объект хоорондын тэгш хэмтэй харилцааг илэрхийлэхэд ашиглаж болно. Чиглэлгүй график дахь зангилаа бүрийн зэрэг болон гадна зэрэг нь тэнцүү боловч чиглэсэн графикийн хувьд энэ нь үнэн биш юм. Чиглэлгүй графикийг дүрслэхийн тулд матрицыг ашиглах үед матриц нь үргэлж тэгш хэмтэй график болж хувирдаг боловч чиглэсэн графикуудын хувьд энэ нь үнэн биш юм. Чиглэлгүй графикийг ирмэг бүрийг эсрэг чиглэлд чиглэсэн хоёр ирмэгээр сольж, чиглүүлсэн график болгон хувиргаж болно. Гэхдээ чиглүүлсэн графикийг чиглүүлэлтгүй график болгон хувиргах боломжгүй.
