Жұмыс бағдарламасы (силлабус) осы мамандықттардың Қр мжмбс 08. 329-2006, Қр мжмбс 08. 33-2006 Мемлекеттік стандартына сәйкес құрылған
жүктеу/скачать 21,8 Mb.
|
- Бұл бет үшін навигация:
- Графтың байланыс компоненттері. Анықтама.
Анықтама: Егер Ui=(ai, ai+1), i=1, 2,…,n (екі көрші төбені қосатын қабырға ) болса a1, U1, a2, U2, a3,…,Un, an+1 (*) маршрут деп аталады. 
а1-төбесі маршруттың басы, аn+1-соңы болады. (*) Маршрутты төбелердің тізбегі арқылы беруге болады.Маршрут доғаларының саны оның ұзындығы деп аталады. Айталық, G н-граф болсын. Егер (*) маршрутта қабырғалар [a1a2],…,[anan+1] әртүрлі болса, яғни әр қабырға бірден артық кездеспесе, маршрут шынжыр деп аталады, ал графтың кез келген төбесі 2-ден артық емес қабырғаға инцидентті болса (төбелер әртүрлі), онда маршрут қарапайым шынжыр деп аталады. Анықтама. Егер a1=an+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-ке тең. Айталық граф бағытталған болсын. Егер (*) маршруттарындағы доғалар әртүрлі болса, маршрут жол деп аталады. Егер a1=an+1 болса маршрут контур деп аталады. Контур жоқ графтар контурсыз граф деп аталады. 
Маршруттың (жолдың) қабырғаларынаң (доғаларының)саны оның ұзындығы деп аталады. Анықтама. Егер (a, b) жолы бар болса, онда b төбесі а дан жекізетін (достижымый) төбе деп аталады. Мысал: Контур бар (1,2,3). 5-төбеге басқа кез-келген төбеден жетуге болады, ал 5-тен ешқандай басқа төбе жеткізбейді. 
Графтың байланыс компоненттері. Анықтама. Бірдей емес екі төбесі (  , ) G маршрутпен қосылған ( -басы, -соңы) бағытталмаған G графы байланысты граф деп аталады.
жүктеу/скачать 21,8 Mb. Достарыңызбен бөлісу:
|