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

жүктеу 0,75 Mb.

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

1 2 3 4 5 6 7 8 9 ... 23

лекция

Анықтама:Бағытталмаған графтың әр қабырғасын қарама қарсы бағытталған доғалармен алмастырғаннан алынған граф берілген графқа сәйкес канонды граф деп аталады.

Анықтама: Еселі доғаларсыз бағытталған графты көбіне диграф деп атайды. G= - V-бос емес (төбелерінің) жиын; E VxV;

А нықтамаG н-графының төбесіне инцидентті қабырғалар саны ( ) V төбесінің локальді дәрежесі деп аталады. Н-графта барлық төбелердің локальды дәрежелерінің қосындысы графтың 2 еселенген қабырғалар санына тең, яғни жұп сан. Ілгек төбе дәрежесіне 2-ге тең үлес қосады:

Анықтама Егер локальды дәреже жұп болса,төбе жұп деп,ал тақ болса төбе тақ төбе деп аталады. 0 дәрежелі төбе оқшауланған төбе деп аталады.

V= {1,2,3,4}.

; Мұндағы, =7–графтың қабырға ларының саны. Бағытталған графтың төбелері үшін 2 локаль ды дәреже анықталады. - төбесінен шығатын қабырғалар саны. - төбесіне кіретін қабырғалар саны. Бағытталған графта барлық төбелердің локальды дәрежелері , осы графтың қабырғалар санына тең, демек олар өзара тең

; Мысалы:

1-ші,2-ші типті дәрежелер қосындысы бірдейқабырғалар санына тең..Егер G¹ төбелері мен қабырғалары G₂ графының төбелері мен қабырғалары бірдей болса,яғни: V₁=V₂, E₁=E₂ болса, онда G₁=G₂.

жүктеу 0,75 Mb.

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

1 2 3 4 5 6 7 8 9 ... 23