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

Графтарға қолданылатын амалдар.Графқа төбе қосу

жүктеу 0,75 Mb.

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

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

лекция

Графтарға қолданылатын амалдар.Графқа төбе қосу.

G= графына а төбесін қосқаннан<М {a}, R> графы құралады.

Графқа доға қосу операциясының нәтижесінде <М {(a,b)}, R {(a,b)}> графы құрылады.

Графтан доға алу–R доғалар жиынынан (a,b) жұбы алынады.

Графтан төбе алуоперациясының нәтижесінде. G графынан а төбесі оған инцидентті доғалармен бірге алынады деп айтады.

Графтың a,b төбелерін теңестіру деп графтан a,b төбелерін алып тастап мына тәртіппен төбе мен қабырға қосу: жаңа а¹төбесі мен (а¹, с), егер (а, с) R немесе (b, с) R және (с, а¹) доғасын егер (с, а) R немесе (с, b) R болса:<(M\{a,b}) {a¹}, (R\{(с, d)│c=a немесе d=a, немесе c=b, немесе d=b}) {(a¹,c)│(a, c) R, немесе (b, c) R} {(c, a¹)│(c, a)R, немесе (c, b) R}).

Алынған граф G графынан a,b төбелерін теңестіргеннен алынды делінеді.

a,b төбелері доғамен қосылса, төбелерді теңестіру a,b доғасын созғаннан алынады дейді. Мысалдар: Берілген=<{1,2,3,4},{[1,2],[2,3],,(3,4)}> графынан суреттегі G₁-G₆ графтары қандай операциялармен алынды?

G графына 5 төбені қосқаннан G₁ графы алынды.

G графына (3,1)–доғасын қосқаннан G₂ графы алынды.

G графына (3,2) доғасы алынады G₃ графы алынды.

G графына 2 – төбені алғаннан G₄ графы алынды.

G графының (1,4) төбелерін теңестіргеннен G₅ графы алынды.

G графының (2,3) доғасын қысқаннан G₆ графы алынды.

=2\R Id_М> графы ілгексіз G= графының толықтырушы графы деп аталады.

Мысал:Айталық, G₁=1,R₁>, G₂=2,R₂> графтары берілсін.

G= ; =2 \R Id_М>

жүктеу 0,75 Mb.

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

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