Граф
Граф гэж юу вэ? edit
Бидний бодит амьдрал дээр объектууд , тэдгээрийн хоорондын холбоогоор тодорхойлогдсон олон асуудлууд байдаг. Тухайлбал хот хооронд онгоцоор аялах аяллыг хэлж болно. Энэ тохиолдолд хамгийн богино замаар нэг хотоос нөгөө хотод бусад бүх хотуудыг дамжин очих асуудал тавигдах болно. Магадгүй хамгийн богино замаас илүү хамгийн хямд замыг ч тодорхойлох шаардлага гарч болох юм. Өөр нэгэн тохиолдол нь тодорхой тооны ажлыг тодорхой тооны гүйцэтгэгчдэд хуваарилах ажил төлөвлөлтийн асуудал байж болно.Ийм төрлийн асуудлыг загварчлах математик объектыг граф гэнэ.
Графын үндсэн ойлголт edit
Граф нь орой болон ирмэгүүдээс бүрддэг . Оройг зарим тохиолдолд зангилаа гэж нэрлэж болох бөгөөд хоёр оройг холбосон холбоосыг ирмэг гэдэг. Ирмэгээр холбогдсон хоёр зангилааг хөрш зангилаа гэнэ. Зургаар нэг графын хоёр ялгаатай дүрслэлийг үзүүллээ . Зурагт үзүүлсэн граф нь 1,2,3,4,5,6 гэсэн оройнууд ба 1 3, 1 2, 1 5, 1 4, 1 6 гэсэн ирмэгүүдээс тогтоно.
Графын x оройгоос y орой хүрэх зам нь дамжин гарах оройнуудын цуваагаар тодорхойлогддог. Жишээлбэл 3 оройгоос 5 оройд хүрэх нэг зам бол 42561 гэж байна. Хэрэв графын зангилаа бүрээс бусад зангилаа бүрт хүрэх зам олдож байвал уг графыг холбогдсон граф гэнэ. Хэрэв граф нь холбогдоогүй бол салангид дэд графуудаас тогтдог. Ялгаатай оройнуудаас тогтох замыг энгийн зам гэнэ. Хэрэв энгийн замын төгсгөлийн зангилаанаас эхний зангилаанд хүрэх ирмэг олдвол үүнийг тойрог буюу давталттай зам гэнэ.
Мод edit
Давталт агуулаагүй графыг мод гэнэ. Өөрөөр хэлбэл графын бүх оройг хүрэлцэхүйц ирмэгүүдээр холбосон дэд графыг мод (spanning tree) гэнэ. Холбогдоогүй модуудыг ой гэж нэрлэдэг. Жишээлбэл зургаар үзүүлсэн графын 1 2, 1 3, 1 4, 1 5, 1 6 гэсэн ирмэгүүдийг агуулах дэд граф нь мод юм. Хэрэв энд нэг ирмэг нэмбэл давталттай зам үүснэ. Хэрэв граф нь v оройтой , v-1 – ээс багагүй ирмэгтэй бол холбогдсон байж чадахгүй. V оройтой , E ирмэгтэй графыг G=(V,E) гэж тодорхойлъё E ирмэгийн тоо нь 0 – оос v(v - 1) /2 – ийн хооронд байх боломжтой. Ирмэгийн тоогоор гарфыг сийрэг эсвэл нягт гэж тодорхойлж болно. Хэрэв V Log V – ээс цөөхөн ирмэгтэй бол сийрэг граф гэнэ. Энд яригдаж буй ойлголтууд нь чиглэлгүй графад хамаарах юм. Хэрэгв х оройгоос у оройд хүрэх ирмэг нь у – ээс х – д хүрэх ирмэгээс ялгаатай бол чиглэлт граф гэнэ. Чиглэлт графыг зарим тохиолдолд сүлжээ гэж нэрлэдэг. Мөн орой хоорондын зай эсвэл үүнийг илэрхийлэх бүхэл тоон утгыг(жин) ирмэгүүдэд олгодог. Ийм графыг жинтэй граф гэнэ.