Жұмыс бағдарламасы (силлабус) осы мамандықттардың Қр мжмбс 08. 329-2006, Қр мжмбс 08. 33-2006 Мемлекеттік стандартына сәйкес құрылған



бет91/214
Дата13.02.2017
өлшемі21,8 Mb.
#9109
түріМазмұндама
1   ...   87   88   89   90   91   92   93   94   ...   214

Салмақтанған графтар.

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

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

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

Мысалы: Айталық M={a1, a2, a3, an}, R={[a1a2], [a2 a3], [a1 a4], [a2 a4]};

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

f(a1)=Омск, f(a2)=Новосибирск, f (a3)=Кемерово, f (a4)=Павлодар

g([a1 a2])=681; g([a2 a3])=274, g([a1 a4])=413; g([a2 a4])=589. Таңбалаған графты–белгілі бір қалалар арасындағы ұзындығы көрсетілген автомобиль жолдарының схемасы. Салмақталған графтардағы доғалардың салмағы туралы ақпаратты салмақ матрицасы арқылы кескіндеуге болады. W=(ij) – мұндағы ij – (ai,aj) доғасының салмағы жоқ доғалар әдетте ноль немесе белгісімен белгіленеді. Қарастырылған мысал үшін салмақтылық матрицасының түрі





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

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

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

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

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

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

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



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

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

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

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

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

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



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

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

Мысал: Айталық, G1=1,R1>, G2=2,R2> графтары берілсін.





G= ; =2 \RIdМ>



Достарыңызбен бөлісу:
1   ...   87   88   89   90   91   92   93   94   ...   214




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет