Цикломатикалық сан. Бағытталмаған G(V, E) графы берілсін. υ(G)=m-n+p, Мұндағы m–граф қабырғаларының саны; n–граф төбелерінің саны; p–байланысты компоненттер саны G(V, E) графының цикломатикалық саны деп аталады. Цикломатикалық санының физикалық мағынасы бар: ол графтың тәуелсіз циклдарының санына тең. Электр шынжырларын есептеген кезде цикломатикалық сан тәуелсіз контурлар санын есептеуге қолданылады.
1-Теорема.Егер G1 графы G графының суграфы болса, онда υ(G1)≤ υ(G).
2-Теорема.Байланысты графта цикл болмауы үшін υ(G)=0 қажетті және жеткілікті.
3-Теорема. Егер G графтың екі байланысты G1 және G2 компоненттері бар болса, онда υ(G)=υ(G1)+υ(G2).
4-Теорема. Графта цикл болмауы үшін υ(G)=0 қажетті және жеткілікті.
Айталық, G(V, E) бағытталмаған граф. G графының S1, S2,…,Sk циклдар жүйесі сызықты тәуелді деп аталады, егер қандай да бір i1, i2, …,ir (1≤ i1 ≤ i2 ≤…≤ ir ≤ k) Si1∆ Si2∆…∆Sik ноль граф болса. Керісінше болса S1, S2, …,Sk циклдары сызықты тәуелсіз циклдар деп аталады. Сызықты-тәуелсіз циклдардың ең көп саны G графындағы тәуелсіз циклдар саны деп аталады.
5-Теорема. Графтың цикломатикалық саны оның тәуелсіз циклдарының санына тең.
Хроматикалық сан. Әр төбесіне қандай да бір бояу сәйкестендірілген және сыбайлас төбелер әртүрлі бояулармен боялған граф деп аталады. 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-ден артық емес қабырғаға инцидентті болса (төбелер әртүрлі), онда маршрут қарапайым шынжыр деп аталады.
1
|
№ 15 дәріс
|
Қарастырылатын сұрақтар (дәріс жоспары):
Кодтау теориясының негізгі ұғымдары.
Кодтаудың түрлері.
Хеминг коды.
Дәрістің қысқаша мазмұны:
Мысал,
, А алфавиттегі А сөзі, n – сөздің ұзындығы.
l(A) – А-ның ұзындығы
бос емес барлық сөздер жиыны
- шығу алфавиті
алфавитіндегі сөз.
-алфавитіндегі барлық бос емес сөздер жиыны.
сөз В-ны хабар А-ның коды деп атаймыз.
1. Алфавиттік кодтау
2. Статистикалық кодтар
3. Бірқалыпты кодтау
4. Автокоррекциялық кодтар
5. Хемминг коды
|
Достарыңызбен бөлісу: |
