Қазақстан республикасының білім және ғылым министірлігі

Көп есептерде графтардың төбесі мен доғалары туралы қосымша ақпарат қажет болады, мысалы, егер граф қалааралық жолдарды бейнелесе салмақтанған графтар қолданылады.

Айталық S_M, S_R - таңбалар жиыны болсын. f: M→S_M (төбелерді таңбалау), g: R→S_R (доғаларды таңбалау) функциялары G= графын таңбалау бөлінуі деп аталады. G= таңбаланған немесе салмақтанған граф деп аталады.

f(a)-a төбесінің салмағы деп, ал g(e) e доғасының салмағы деп аталады. Доға мен төбенің біреуінің ғана таңбалануы жиі кездеседі.

Мысалы: Айталық M={a₁, a₂, a₃, a_n}, R={[a₁a₂], [a₂ a₃], [a₁ a₄], [a₂ a₄]};

f:M→C мұндағы, С- қалалар жиыны, g:R→W.

f(a₁)=Омск, f(a₂)=Новосибирск, f (a₃)=Кемерово, f (a₄)=Павлодар

g([a₁ a₂])=681; g([a₂ a₃])=274, g([a₁ a₄])=413; g([a₂ a₄])=589. Таңбалаған графты–белгілі бір қалалар арасындағы ұзындығы көрсетілген автомобиль жолдарының схемасы. Салмақталған графтардағы доғалардың салмағы туралы ақпаратты салмақ матрицасы арқылы кескіндеуге болады. W=(_ij) – мұндағы _ij – (a_i,a_j) доғасының салмағы жоқ доғалар әдетте ноль немесе белгісімен белгіленеді. Қарастырылған мысал үшін салмақтылық матрицасының түрі

графына а төбесін қосқаннан <М{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\RId_М> графы ілгексіз G= графының толықтырушы графы деп аталады.

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

G= ; =2 \RId_М>

жүктеу 21,8 Mb.

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