Салмақтанған графтар.
Көп есептерде графтардың төбесі мен доғалары туралы қосымша ақпарат қажет болады, мысалы, егер граф қалааралық жолдарды бейнелесе салмақтанған графтар қолданылады.
Айталық 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] .
Бақылау сұрақтары:
-
Қандай графтар бағытталған графтар деп аталады? Қандай графтар бағытталмаған деп аталады? Графтарда қандай төбелер сыбайлас төбелер деп аталады?
-
Төбелер дәрежесі деген не?
-
Графтардың берілу тәсілдерін атаңыз.
-
Графтармен қандай операциялар орындалады.
Достарыңызбен бөлісу: |
