Дәріс жоспары: Графтарда жолды іздеу есебі

• Дәріс жоспары:

• 3. Графтарда жолды іздеу есебі

• Граф және оның элементтері

• 2. Графтағы маршруттар

• 1. Граф және оның элементтері.

• Граф – өзара байланысты объектілер жиынтығы. 
• Объектілер төбелер немесе графтың түйіндері, ал байланыстар доғалар немесе қырлар ретінде қарастырылады. Графтың қыры доға деп аталады, егер оның бір төбесі бастапқы, ал екіншісі соңғы төбе болатын болса.

• А

• Б

• В

• Граф доғасы

• Граф доғасы

• Граф қыры

• Граф төбесі

• Граф төбесі

• Граф төбесі

• Бағытталмаған граф 

• Бағытталған граф 

• Аралас граф

• G=(V,E) графындағы маршрут (жол) — бұл төбеден басталып төбеден аяқталатын төбелері мен қырлары алмасып келетін v0, e1, v1, e2,…,vk-1, ek, vk ақырлы тізбек, сонымен бірге vi-1 және vi төбелері ei (1 i  k) қырының шеткі төбелері болып табылады.
• Егер графтың кез келген 2 төбесін қосатын маршрут бар болса, граф байланысқан деп аталады, ондай маршрут болмаса ол байланыспаған граф болады.

• 2. Графтардағы маршруттар

Маршрут ашық деп аталады, егер шеткі төбелері әртүрлі болса (v1, e1, v2, e2, v3, e8, v6, e9, v5, e7, v3, e11, v6).

• Маршрут ашық деп аталады, егер шеткі төбелері әртүрлі болса (v1, e1, v2, e2, v3, e8, v6, e9, v5, e7, v3, e11, v6).
• Маршрут тұйық деп аталады, егер шеткі төбелері беттесетін болса (v1, e1, v2, e2, v3, e7, v5, e3, v2, e4, v4, e5, v1).

• G