Цикл. Эйлер және Гамильтон циклдары. Цикломатикалық және хроматикалық сан. Ағаш және оның қасиеттері. Маршрут. Графтың байланыс компоненттері. Ағаштар, ағаштардың негізгі қасиеттері.
Шексіз бағытталмаған байланысты граф ағаш деп, ал циклсыз байланыссыз граф орман деп аталады. Анықтама бола алатындай G ағашының кейбір қасиеттерін қарастырамыз:
а) G байланысты және циклы жоқ;
б) G циклы жоқ және n-1 қабырғасы бар;
в) G байланысты және n-1 қабырғасы бар;
г) G графында цикл жоқ, бірақ сыбайлас емес төбелер арасында қабырға қосу тек бір ғана циклдың пайда болуына әкеледі;
д) G байланысты, бірақ бұл қасиетін кез келген қабырға алынып тасталса жоғалтады;
е) G графының кез келген төбелер жұбы тек бір ғана шынжырмен байланысқан.
Маршруттар. Айталық G= Н-граф болсын.
Мұндағы a1, a2,…,an+1 M U1 U2, … , Un R Анықтама: Егер 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 болса (*) маршруты циклды деп аталады (басы мен соңы бірдей маршрут).
Анықтама. Циклы бар маршрут шынжыр болса цикл деп аталады, ал маршрут қарапайым шынжыр болса қарапайым цикл деп аталады.
Анықтама. Бағытталмаған циклсыз граф ациклды граф деп аталады. Бағытталмаған графтың циклдарының ұзындықтарының ең кішісі құлаш деп аталады (обхват).
2
15
№15 дәріс Кодтау теориясының негізгі ұғымдары. Кодтаудың түрлері. Хеминг коды.
Мысал,
, А алфавиттегі А сөзі, n – сөздің ұзындығы.
l(A) – А-ның ұзындығы
бос емес барлық сөздер жиыны
- шығу алфавиті
алфавитіндегі сөз.
-алфавитіндегі барлық бос емес сөздер жиыны.
