Орындаған: Шады А
жүктеу/скачать 0.56 Mb.
|
- Бұл бет үшін навигация:
- Бағдарланған және бағдарланбаған графтар
| Негізгі анықтамалар
G-графы нҥктелер жиыны тӛбелер { , ,..., } 1 2 n X x x x және осы нҥктелердің барлығын немесе белгілі бір бӛлігін қосатын сызықтар жиыны (қабырғалар) { , ,..., } A a1 a2 am -мен беріледі. Сонымен, G графы (X, A) жҧбымен толық анықталады. Графтарды сипаттаудың басқа бір жиі қолданылатын тҥрі: X тӛбелер жиыны мен осы тӛбелердің арасындағы байланысты кӛрсететін G сәйкестігін беру. Яғни, граф келесі тҥрде беріледі. Айталық, элементтерден тҧратын X жиыны (элементтерді графтың тӛбелері деп атаймыз) және оның әрбір x элементімен оның кейбір G(X) ішкі жиынының арасындағы сәйкестігін анықтайтын G заңы беріле, онда граф X жиыны мен G сәйкестігі арқылы толық анықталады. Граф (X,G) жҧбымен белгіленеді. Функциядаға ҧқсас графты G(X) тҥрінде белгілегенде ыңғайлы. Мысал. Төбелер жиыны { , , , , , , } 0 1 2 3 4 5 6 X x x x x x x х және олардың арасындағы сәйкестіктер тӛменде кӛрсетілген. Графтың қабырғасы – тӛбелерді қосатын сызық, ол графтың тӛбелерінің арасындағы сәйкестікті кӛрсетеді. Егер g қабырғасы ( , ) i j x x тӛбелерін қосатын болса, онда g қабырғасы мен ( , ) i j x x тӛбелері өзара инцидентті - деп аталады. ( , ) i j g x x жазуы g қабырғасының i j x , x тӛбелерімен инцидентті және i j x , x тӛбелерінің g қабырғасымен инцидентті болатындығын кӛрсетеді. Егер i j x , x тӛбелері графтың қабырғасын анықтайтын болса, онда оларды іргелес тӛбелер деп атайды. Графтың ортақ тӛбелері бар екі қабырғасын іргелес қабырғалар деп атаймыз. Графтың ешқандай қабырғасына инцидетті болмайтын тӛбені оқшауланған тӛбе деп атаймыз. Егер граф тек ғана оқшауланған тӛбелерден тҧрса, онда оны нӛль-граф деп атайды. 6.1.2. Бағдарланған және бағдарланбаған Бағдарланған және бағдарланбаған графтар Егер графтың қабырғасының ҧштарының орналасу реті ескерілмейтін болса, онда оны бағдарланбаған қабырға деп атайды. Егер графтың қабырғасының ҧштарының орналасу реті ескерілетін болса, онда оны бағдарланған қабырға деп атайды. Бҧл жағдайда ( , ) i j g x x қабырғасының басы - i x тӛбесі, ал соңы j x тӛбесі деп аталады. Бағдарланған қабырға графтың доғасы деп те аталады. Егер графтың барлық қабырғалары бағдарланбаған болса, онда ол бағдарланбаған граф деп аталады, ал егер графтың барлық қабырғалары бағдарланған болса, онда ол бағдарланған граф деп аталады. Егер графта бағдарланған және бағдарланбаған да қабырғалар бар болса, онда оны аралас граф деп атайды. G(X) графындағы әрбір қабырғаның бағдарын қарама-қарсыға (керіге) ӛзгерту арқылы оған кері граф ( ) 1 G X аламыз. Яғни, әрбір графқа кері граф бар. Бағдарланбаған толық граф деп кез келген х , x X (i j) j i ҥшін қабырғалары әртҥрлі ( , ) i j g x x жҧптары болатын U(X) графын атайды. жүктеу/скачать 0.56 Mb. Достарыңызбен бөлісу:
|