Салмақтанған графтар.
Көп есептерде графтардың төбесі мен доғалары туралы қосымша ақпарат қажет болады, мысалы, егер граф қалааралық жолдарды бейнелесе салмақтанған графтар қолданылады.
Айталық 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 графы алынды.
Анықтама: G1, G2 графтарының бірігуі деп G1UG2=1UM2,R1UR2> графын айтады.Анықтама:ЕгерМ2∩М2= онда G1,G2 графының қиылысуы деп, G1∩G2=1∩M2,R1∩R2> графын айтады.
Анықтама: G1, G2 графтарының сақиналы қосындысы деп G1 G2=1UM2,R1R2>, мұндағы R1R2=( R1\R2)U(R2 \R1).
Мысалы G1 және G2 графтары берілсін.
G1= < {a1, a2, a3}, {[a1, a2], (a2, a3)} >;
G2= < {a1, a2, a4}, {(a1, a2, ), (a4, a1)}>;
|
|
Табу керек: G1U G2 , G1∩ G2 , G1 G2 ?
Шешуі: Анықтама бойынша:
G1UG2=<{a1, a2, a3, a4},{[a1, a2], (a2, a3), (a4, a1)}>;
G1∩G2 = < {a1, a2}, {(a1, a2)} >.
G1G2=<{ a1, a2, a3, a4}, {( a2, a1), (a2, a3), (a4, a1)} >;
G1, G2 графтарының қосылуы деп G1+ G2 =
|
Мына суреттің а пунктіндегі G1, G2 графтарының қосындысы б пунктте көрсетілген.
|
G1,
|
|
G2 графтарының көбейтіндісі деп G1xG2=1xM2, R>, мұндағы ((a1,b1), (a2, b2)) R тек сонда ғана, егер a1=a2 және (b1,b2) R2 немесе b1=b2 және (a1,a2) R1.
Ішкі графтар және графтардың бөлігі.
Граф бөліктерімен операциялар.
Анықтама: Егер М1 М және R1R∩(M1)2 болса, яғни G1 графының төбелер жиыны G графы төбелер жиынына, ал G1 қабырғалар жиыны G графының қабырғалар жиынына жатса G1- G бөлігі деп аталады.
Анықтама Айталық. G=,G1=1,R1> графтары берілсін. Егер М1М және R1=R∩(M1)2 болса, яғни G1 графының төбелер жиыны G-ң төбелер жиынында жатса ал G1-ң доғалары екі жағымен де G графына жатса G1 – G графының ішкі графы деп аталады.
Анықтама Егер Н графының төбелер жиыны V(H) мен қабырғалар жиыны E(H) G графының сәйкесінше төбелері мен қабырғалар V(G) , E(G) жиындарында жатса  және  , онда Н графы G графының бөлігі деп аталады  .
Анықтама Егер  , G графының бөлігі Н суграф деп аталады. Егер G графының кез келген төбесі Н графының ең болмаса бір қабырғасына инцидентті болса , онда бағытталмаған Н графы G графын жабады дейміз.
Мысалы:а) G=<{1, 2, 3, 4}, {[1, 2], [1, 3], [1,4], [2,3], [3,4]}>
б)G1=<{1, 2, 3}, {[1, 2], [1, 3], [2, 3]}> - G ішкі графы (М1МR1, R1=R∩R1)
в)G11=<{1, 2, 3}, {[1, 2], (2,3)}> - G графының бөлігі (M11 М,R11 R∩( M11)2 )
Граф бөліктеріне қолданылатын амалдар.
Граф бөліктеріне төмендегідей амалдар орындалады:
Н-бөліктің толықтаушы  - G-графының Н-ға жатпайтын барлық қабырғалар жиынымен анықталады.  ,мұндағы E(G) - G-графының қабырғаларының жиыны.
-G графының Н1 , Н2 бөліктерінің қосындысы  :
-  және  ;
- G графының Н1 , Н2 бөліктерінің көбейтіндісі :  және  ;
Егер H1 , H2 бөліктерінің ортақ төбелері болмаса, яғни  , демек ортақ қабырғалары да жоқ  , онда H1 , H2 бөліктері төбелері бойынша қиылыспайды.
Егер H1 , H2 бөліктерінің ортақ қабырғалары болмаса ,онда H1 , H2 бөліктері қабырғалары бойынша қиылыспайды.
Егер болса онда тура қосынды деп аталады.
Графтар мен бинарлы қатынастар.
V жиынында берілген R қатынасына өзара бір мәнді анықталған,  орындалса ғана  қабырғасы бар болатын V төбелер жиындарымен қабырғалар еселі емес бағытталған G(R) графы сәйкес келеді.
1-мысал: Симметриялы, антисиметриялы, рефлексивті, антирефлексивті, транзитивті R бинарлы қатынасына өзара бір мәнді сәйкес G графының қандай ерекшеліктері бар?
Айталық , R бинарлы қатынасы  жиынында анықталсын.
а) симметриялы R қатынасына еселі қабырғалары жоқ, орындалса ғана  қабырғасы бар болатын бағытталмаған G(R) графы сәйкес келеді (симметриялы болғандықтан  ) .
б) Антисиметриялы R қатынасына еселі қабырғаларсыз,(әртүрлі төбелерге қарама-қарсы бағытталған қабырғалары бар төбелер болмайтын) өзара бір мәнді бағытталған G(R) графы сәйкес келеді .
в) Егер R рефлексивті болса, барлық төбелерінде ілгектері бар еселі қабырғаларсыз G(R) графы сәйкес келеді.
г) Егер R антирефлексивті болса, еселі қабырғаларсыз G(R) графында бір де бір ілгек болмайды.
д) Егер R транзитивті болса, еселі қабырғаларсыз G(R) графының әрбір және  қабырғалар жұбына оларды тұйықтайтын  қабырғасы бар болады.
Негізгі әдебиет: 1 [161-180]; 2[108-114] .
Қосымша әдебиет: 7[88-130] .
Бақылау сұрақтары:
Қандай графтар бағытталған графтар деп аталады? Қандай графтар бағытталмаған деп аталады? Графтарда қандай төбелер сыбайлас төбелер деп аталады?
Төбелер дәрежесі деген не?
Графтардың берілу тәсілдерін атаңыз.
Графтармен қандай операциялар орындалады.
Достарыңызбен бөлісу: |
