Дәріс тақырыбы: Графтар теориясы (5 сағат) Негізгі сұрақтар

жүктеу 0,75 Mb.

бет	11/23
Дата	03.02.2022
өлшемі	0,75 Mb.
	#35463

1 ... 7 8 9 10 11 12 13 14 ... 23

лекция

Анықтама: Егер U_i=(a_i, a_i+1), i=1, 2,…,n (екі көрші төбені қосатын қабырға ) болса a₁, U₁, a₂, U₂, a₃,…,U_n, a_n+1(*) маршрут деп аталады.

а₁-төбесі маршруттың басы, а_n+1-соңы болады. (*)Маршрутты төбелердің тізбегі арқылы беруге болады.Маршрут доғаларының саны оның ұзындығы деп аталады. Айталық, G н-граф болсын. Егер (*) маршрутта қабырғалар [a₁a₂],…,[a_na_n+1] әртүрлі болса, яғни әр қабырға бірден артық кездеспесе, маршрут шынжыр деп аталады, ал графтың кез келген төбесі 2-ден артық емес қабырғаға инцидентті болса (төбелер әртүрлі), онда маршрут қарапайым шынжыр деп аталады.

Анықтама. Егер a₁=a_n+1 болса (*) маршруты циклды деп аталады (басы мен соңы бірдей маршрут).

Анықтама. Циклы бар маршрут шынжыр болса цикл деп аталады, ал маршрут қарапайым шынжыр болса қарапайым цикл деп аталады.

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

Бұл графта (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)–қрапайым емес цикл;

(1, 2, 4, 1)–қарапайым цикл; Графтың құлашы 3-ке тең. Айталық граф бағытталған болсын. Егер (*) маршруттарындағы доғалар әртүрлі болса, маршрут жол деп аталады.Егер a₁=a_n+1 болса маршрут контур деп аталады. Контур жоқ графтар контурсыз граф деп аталады.

Маршруттың (жолдың) қабырғаларынаң (доғаларының)саны оның ұзындығы деп аталады.

Анықтама. Егер (a, b) жолы бар болса, онда b төбесі а дан жекізетін (достижымый) төбе деп аталады.

Мысал: Контур бар (1,2,3).

5-төбеге басқа кез-келген төбеден жетуге болады, ал 5-тен ешқандай басқа төбе жеткізбейді.

жүктеу 0,75 Mb.

Достарыңызбен бөлісу:

1 ... 7 8 9 10 11 12 13 14 ... 23