Маршрут шынжыр деп аталады, егер оның барлық қырлары әртүрлі болса

Маршрут шынжыр деп аталады, егер оның барлық қырлары әртүрлі болса.

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

• G

Ашық шынжыр жол деп аталады, егер оның барлық төбелері әртүрлі болса (v1, e1, v2, e2, v3).

• Ашық шынжыр жол деп аталады, егер оның барлық төбелері әртүрлі болса (v1, e1, v2, e2, v3).
• Цикл – бұл тұйық шынжыр (қарапайым цикл, егер шынжыр қарапайым болса) (v1,e1,v2,e3,v5,e6,v4,e5,v1).
• Жолдағы қырлардың саны жолдың ұзындығы деп аталады. Сол сияқты циклдың ұзындығы анықталады.

• G

Бағытталмаған циклсыз граф ациклды граф деп аталады. Бағытталмаған графтың циклдарының ұзындықтарының ең кішісі құлаш деп аталады (обхват).

• Бағытталмаған циклсыз граф ациклды граф деп аталады. Бағытталмаған графтың циклдарының ұзындықтарының ең кішісі құлаш деп аталады (обхват).
• Төмендегі графта (1,2), (1,2,4,7), (3,4,5,6) - қарапайым шынжыр. (1,2,4,7,8,4) -қарапайым емес шынжыр (4-екі рет). (1, 2, 4, 7, 8, 4, 2) – шынжыр емес маршрут; (1, 2, 4, 7, 8, 4, 1) – қарапайым емес цикл;

• G

• 12

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

• №1 есеп. A, B, C, D, E, F, G, H, K, L, M қалаларын байланыстыратын жолдардың сұлбасы төмендегі суретте көрсетілген. Әрбір жол бойынша бағыттаушы стрелкамен бір бағытта ғана жүруге болды. А қаласынан M қаласына неше жолмен баруға болады?

• B

• A

• K

• C

• E

• G

• F

• H

• L

• M

• №1 есептің шешімі.

• Маршруттың соңынан, яғни М қаласынан бастап жолдардың санын есептеуді бастаймыз.
• NX — А қаласынан Х қаласына дейінгі әртүрлі жолдардың саны, N — жалпы жолдар саны. «М» қаласына C, F, L немесе H қалаларынан келуге болады, сондықтан
• N = NM = NC + NF + N H + N L (1)

• C

• F

• H

• L

• M

• 2. Сол сияқты:
• NC = NB;
• NF = NE;
• NH = NF + NG;
• NL = NK.

• C

• F

• H

• L

• M

• B

• E

• G

• K

• A

• 3. Тағы да төбелерді қосамыз:
• NB = NA = 1;
• NE = NB + NA + NG = 1 + 1 + 2 = 4;
• NG = NA + NK = 1 + 1 = 2;
• NK = NA = 1.

• 4. Төбелерді қайта бейнелейміз:
• NC = NB = 1;
• NF = NE = 4;
• NH = NF + NG = 4 + 2 = 6;
• NL = NK = 1.

• 5. (1)-ші формулаға қоямыз:
• N = NК = 1 + 4 + 6 + 1 = 12

• B

• A

• K

• C

• E

• G

• F

• H

• L

• M

• Жауабы: 12

• №2 есеп.

• А, Б, В, Г, Д, Е, Ж, З, И қалаларын байланыстыратын жолдардың сұлбасы төмендегі суретте көрсетілген. Әрбір жол бойынша бағыттаушы стрелкамен бір бағытта ғана жүруге болды. А қаласынан И қаласына неше жолмен баруға болады?

• A

• И

• №2 есептің шешімі

• N = NИ = NД + NЖ + N З (1)

• 2. Сол сияқты:
• NД = NБ; NЖ = NБ + NВ + NЕ; NЗ = NЖ + NЕ.

• 3. Тағы да төбелер қосамыз:
• NБ = NА = 1;
• NВ = NА + NГ = 1 + 1 = 2;
• NЕ = NВ + NГ = 2 + 1 = 3;
• NГ = NА = 1.

• 4. NД = NБ = 1;
• NЖ = NБ + NВ + NЕ = 1 + 2 + 3 = 6;
• NЗ = NЖ + NЕ = 6 + 3 = 9.

• 5. (1)-ші формулаға қоямыз:
• N = NК = 1 + 6 + 9 = 16. Жауабы: 16

• Үйге тапсырма:
• A, B, C, D, E, F, G, H, K, L, M қалаларын байланыстыратын жолдардың сұлбасы төмендегі суретте көрсетілген. Әрбір жол бойынша бағыттаушы стрелкамен бір бағытта ғана жүруге болды. А қаласынан M қаласына неше жолмен баруға болады?

• B

• C

• D

• E

• F

• G

• H

• K

• L

• M

• А