Графтар теориясы

Графтар теориясы

 Жазық графтар қасиеттерін , ашық графтар қасиеттерін білу; Эйлер графтарымен қолды үзбей сызу есептерін шығару жолдарын меңгеру..

Қарапайым ұғымдар (түсініктер) мен  анықтамалар. Көбейту мен қосу қағидасы ( принципі). Орын ауыстыру, орналастыру мен үйлестіру. Графтар дәрежесінің қасиеттері. Эйлер теориясы Бағытталған графтар. Графтардын ең қарапайым қасиеттері. Ашық (дерево) және тұйық (цикл) графтар ұғымы. Жазық графтар қасиеттері. Ашық графтар қасиеттері. Эйлер графтарымен қолды үзбей сызу есептері.

 

Компьютерлік жүйелерде ақпараттарды қорғау

 Графтар теориясы. ЭЕМ архитектурасы, Компьютерлік желілер, Программалау.

 Ақпаратты қорғау негізінде криптография элементтерін пайдалану.

 Қазіргі заман ақпараттарды қорғау құралдарына: криптографиялық, алгоритмдік және протоколдық талдау жасау; симметриялы және симметриялы емес кілттеріне негізделген белгілі криптография стандарттарын меңгеру; қазіргі заман криптография әдістерін қолдана отырып идентификация құралдары мен әдістерін білу.

 Антивирустық программалар. Архивтеу программалары. Ақпаратты қорғау тәсілдері. Файлдық жүйелер. Windows NT қолданылатын жүйелік ресурстар. Ақпараттың қауіпсіздігін қамтамасыз ету. Деректердің жоғалуын алдын алу. Ақпараттың құрылғылары. Ақпаратты жариялау, әдістері. Ақпаратты құқықтық және қаржылық тұрғыдан қарау. Қорғау обьектілері. Қауіп түрлері. Ақпаратты қорғаудың жаңа әдістерін шолу. Ақпаратты қорғау концепциясын дамыту. Ақпаратты қорғаудың элементар, көпсатылы және көпмүшелі моделі.

Граф деп – бейнеленген заттардың екі – екіден жұпталып

келген заттардың  бір – бірімен қатынасының  жүйесін айтады. Графтармен

коммуникация  жолдарын қолайлы бейнелейді, үздіксіз емес көп қадамды

 

Page 41

41

процестерде («бинарлық  қатынастардың жүйелерін, химиялық формулалардың

құрылымында, тағы басқа әр түрлі схемалардың диаграммаларында»)

қолданылады.

Граф G - жүйе

(

)

{ }V

V

EVG

=

∙

Γ

,,

жиынының элементі граф төбесінен тұрады

да,

{ }e

E =

қыры болып  келген бейнелеуді көрсетеді.

2

:

V

E →

Γ

егер әрбір

элементтің Ee

∈

реттелген санға сәйкес реттелген екі элементті

VVV

∈

2

1,

– ның

қырларының  соңы сәйкес келеді.

EV

∪

(V және

E жиындарының бірігуі) – графтың көптеген

элементтерінен  тұрады да, ал EV

⋂

= ø (E мен V қиылысуы) құр жиынды

көрсетеді. Γ бейнесі әрбір соңғы қырының инцинденттігін анықтайды.

(

)Γ

= ,,

EV

G

үшін ең қысқа

( )

EV

G

,

=

. Мұнда инцинденттілігі  көрсетілмеген. Олар

контекстпен анықталады. Элементтерінің санына байланысты шекті  және

шексіз болып  бөлінеді. Біз тек ғана шекті графпен  танысамыз.

Егер

( ) (

)2

1,VV

er =

– екі – екіден таралып реттелген.

(

) (

)1

2

2

1

,

,

VV

VV ≠

2

1

VV

=

болғанда, онда e бағытталған доғал болады да,

шыққан 1

V

- төбесі e доғасының басы, кіретін 2

V

төбесі e доғасының соңы деп

аталады.

Егер

( ) (

)2

1,VV

er =

жұбы ретсіз болса, онда e қыры бағытсыз деп аталады.

Кез – келген G графқа сәйкестендіріліп алынған бағытсыз граф

~

G ,V және

E жиындарынан және инцинденттіктерінен тұрады, бірақ барлық парлары

ретсіз болады.

Төбелері бірде  – бір қырымен инциндентті  болмаса, онда ондай қырды

бөлектенген қыр деп атаймыз, ал төбесі бір қырымен инциндентті болса, онда

оны аяқталған қыр, не ілінген қыр деп атаймыз. Қырдың басы мен соңы

біріккен болса, оны ілмек деп атаймыз.

Егер екі  төбе бір қырға инциндентті болса, ондай төбелерді көршілес, не

сыбайлас төбелер деп атайды. Егер екі қыр бір төбеге инциндентті болса, онда

ондай қырды сыбайлас деп атаймыз. Қырға сәйкес қойылған екі төбені еселік,

не параллель  төбелер деп атаймыз.

Әртүрлі есептер  үшін бір тек сол затқа графтың  әртүрлі салыстыруы

қажет.

Мысалы: жолдар тармағының үзіндісі ретсіз қырмен көрсетіледі де, бір–

бірімен қатынастарының аяқталуын бейнелейді (қоныстанған  орындарымен,

қала көшелерімен, көшенің түйіскен жерімен құралдарындағы бір жақты, не екі

жақты қозғалыстар). Бірнеше доғаларымен бөлектеген әрбір бірнеше

қозғалысты  – қырға қосымша жазылған сандар, оның ұзындығын, енін,

епкіштігін  және сандар не басқа сипаттамасын көрсетеді.

Қандай графтар  ажыратылатын және ажыратылмайтын болып  бөлінуін

анықтау өте  қажет болып табылады, оны тіпті  графтардың изоморфизм

ұғымымен байланыстырады. Өзара сақталып инцинденттік пайда  болған

 

Page 42

42

бірімен – бірінің  мәнді сәйкес бейнелеуін екі графтың

(

)1

1

1

1

,,Γ

= EV

G

және

(

)2

2

2

2

,,Γ

= EV

G

изоморфизмі деп  атаймыз да, оны былай белгілейміз

2

1

:

V

Vf ⇔

және

2

1

:

E

Eg ⇔

кез

–

келген

1

1

Ee

∈

теңдікке

( ) (

)2

1

1

1

,VV

er =

=>

( ) (

)2

1

2

2

, fV

fV

ger =

көптеген жағдайларда  графтарды изоморфизмге

дейінгі дәлдікпен қарастыруға  болады, яғни изоморфты графтастыруы

байқалмау, бірақ қайсібір графтардың төбелерінің немесе қырларының әртүрлі

ерекшеліктері болса, мысалы, номерленген немесе оларға сандық мәндер

сәйкестендірілген (қырының  салмағы, қырының ұзындығы және т. б.) болса,

онда екі графты салыстыру  кезінде олардың ерекшеліктерін ескеру заңды.

Графтарды бірнеше жолдармен беруге болады. Шекті графты оның

қырларының тізімінің  санын көрсетіп санау арқылы, оған қоса жеке тұрған

төбенің тізімін көрсету.