Құрастырған: Математика және математиканы оқыту әдістемесі кафедрасының оқытушысы Ахметқалиева А. С. 2014ж

• 
  Бағдарланбaғaн граф (Неориентированный граф) — төбелерді қосатын доғаларының бағыты болмайтын граф.
  
• 
  Бағдарланған граф (Ориентированный граф; directed graph) - әр түрлі төбелер жұбын жалғастыратын қабырғалармен бірге түйіндердің (немесе төбелердің) құр ақырғы жиыны. Егер е қабырғасы Vl және V2 төбелерін жалғастырса, онда Vl мен И,-ні инцидент деп атайды және бұл төбелер көршілес болып саналады, е — реттелмеген жұп (К, и V2). Әдетте, граф көрнекті формада ұсынылады, сонымен бірге төбелері нүктелермен немесе кейде ұқсастыру мақсатымен ентаңбаланған басқа мүсіндермен, ал қабырғалары сәйкес нүктелерді жалғастыратын сызықтармен кескінделеді. Егер әрбір қабырғаға бағыт көрсетілсе, онда мұндай граф бағдарланған граф деп аталады. Бұл жағдайда қабырға әр түрлі төбелердің реттелген жұбының жиынын үйымдастырады және оларды көбінесе доға деп атайды. Бағдарланған граф көрнекті түрде ұсынылған кезде әрбір доға жебелікпен жабдықталады.
  

&&&
$$$002-007-000$3.2.4. Дәріс №4.

1. 
   Жиындар арасындағы сәйкестік
   
2. 
   Сәйкестік графигі
   
3. 
   Кері сәйкестік
   
4. 
   Сәйкестіктің жеке түрлері
   

  Қайсыбір класс оқушылары Арманға, Еділге, Қайратқа, Динаға, Талғатқа және Сәулеге: ²Сендер футбол, волейбол, жүзу, гимнастика және теннис сияқты спорт түрлерімен шұғылданасыңдар ма?²деп сұрақ қойылған. Олардың жауаптары кестеге орналастырылды.

Бұл мысалда екі жиын берілген: оқушылар аттарының жиыны және спорт түрлері аттарының жиыны. Бірінші жиынды Х, ал екінші жиынды У арқылы белгілейік. Сонда Х={Арман, Еділ, Қайрат, Дина, Талғат, Сәуле}, ал У={футбол, волейбол, жүзу, гимнастика, теннис} деп жазуға болады. ²Спорттың қайсыбір түрімен шұғылдану² деген сөз арқылы осы екі жиын элементтерінің арасында қандай да бір байланыс тағайындалып отыр. Осындай байланыс математикада сәйкестік деп аталады. Таблицада бұл сәйкестілік штрихталған клеткалармен көрсетілген. Осы таблицадағы барлық клеткалардың жиыны Х және У жиындарының декарттық көбейтіндісі болатындығы белгілі. әрбір штрихталған клетка осы жиынға тиісті болғандықтан, штрихталған клеткалар жиыны декарттық көбейтінді Х´У жиынының ішкі жиыны болады. Сонымен, Х және У жиындарының арасындағы сәйкестікті біз үш жиынды пайдаланып тағайындадық: оқушылар аттарының Х жиыны, спорт түрлері аттарының У жиыны және Х´У декарттық көбейтіндінің ішкі жиыны.

Декарттық көбейтіндінің ішкі жиынын G әрпімен белгілеп, оның элементтерін атап шығайық: G={<Арман, волейбол>, <Арман, теннис>, <Еділ, футбол>, <Еділ, волейбол>, <Еділ, теннис>, <Қайрат, футбол>, <Қайрат, жүзу>, <Дина, волейбол>, <Сәуле, волейбол>, <Сәуле, теннис>}.

Жалпы, Х және У жиындарының арасындағы сәйкестік деп жиындар үштігі аталады: Х жиыны, У жиыны және Х´У декарттық көбейтіндінің қандай да ішкі жиыны G. Х - жиыны сәйкестіктің шығу жиыны У жиыны сәйкестіктін келу жиыны, ал GÌ Х´У жиыны осы сәйкестіктің графигі деп аталады.

Жиындар арасындағы сәйкестікті R,P,Q,S,T әріптермен белгілеуге келісейік. Осы келісімді пайдаланып, жоғарыдағы мысал туралы былай деуге болады: біз оқушылар аттарының жиыны Х (шығу жиыны) және спорт түрлері аттарының жиыны У (келу жиыны) арасында R сәйкестігін анықтадық, мұндағы R - ²оқушы хÎХ спорттың уÎУ түрімен айналысады².

Х´У декарттық көбейтінді хÎХ уÎУ болатын барлық мүмкін болатын <х;у>жұптардан турады. Егер Х және У жиындары арасындағы сәйкестік R, ал G жиыны оның графигі және <х;у> ÎG екендігі белгілі болса, онда R сәйкестікте у элементі х элементіне сәйкес немесе х және у элементтерінің арасында R сәйкестігі орындалады дейді, және оны хRу түрінде жазады. хRу жазуын былай оқиды: ²R сәйкестікте у элементі х элементіне сәйкес болады².

Мысалы, егер Х={1, 3, 5, 7}, У={2, 4, 6, 8, 10}, ал Х және У арасындағы қандайда бір R сәйкестігінің графигі G={<3, 2>, <5, 2>, <5, 4>, <7, 2>, <7, 4>, <7, 6>} болса, онда, мәселен G жиынының <3, 2>жұп туралы 3ÎХ және 2ÎУ сандарының арасында R сәйкестілігі орындалады деп немесе R сәйкестігінде 2 саны 3 санына сәйкес келеді деп айтуға болады және оны былай жазуға болады: 3R2.

Осы мысалдағы R сәйкестігіне сөзбен айтқанда мынадай нақтылы мағына беруге боладв: ²Х жиынынан алынған х саны У жиынынан алынған у санынан үлкен². Сонда, 3R2 жазуын былай оқуға болады: ²Х жиынынан алынған 3 саны У жиынынан алынған 2 санынан үлкен². ²х саны у санынан үлкен² деген Х={1, 3, 5, 7} және У={2, 4, 6, 8, 10} жиындарының арасындағы R сәйкестігін чертеж арқылы көрнекті түрде елестетуге болады. Ол үшін берілген жиындарының Эйлер-Венн диаграммаларын құрып, олардың элементтерін нүктелер арқылы кескіндейміз. Сонаң соң сәйкестіктің графигіне тиісті әрбір <х,у>жұптарының элементтерін басы х элементін кескіндейтін нүктеде, ал соны у элементін кескіндейтін нүктеде болатын стрелкамен қосамыз (19-сурет). Сонда шыққан чертежді R сәйкестігінің графы деп атайды.

б) У жиынының тек бір ғана элементі сәйкес келуі;

в) У жиынының бірде-бір элементі сәйкес келмеуі мүмкін.

Шынында да егер R Х={1, 3, 5, 7} және У={2, 4, 6, 8, 10} жиындарының арасындағы ²х саны у санынан үлкен² сәйкестік болса, онда 7ÎХ элементіне У жиынының үш элементі сәйкес келеді: 7R2, 7R4, 7R6. Графта (19-сурет) 7 санын өрнектейтін нүктеден үш стрелка шығатындығы көрініп тұр. 3ÎХ элементіне У жиынын тек қана бір элементі 2 сәйкес келеді. Графта 3 санын өрнектейтін нүктеден бір ғана стрелка шығады. Ал 1ÎХ элементіне У жиынының бірде-бір элементі сәйкес келмейді, сондықтан да графта оны өрнектейтін нүктеден ешқандай стрелка шықпайды.

Келу У жиынының элементі шығу Х жиынының бірнеше элементтеріне, не тек бір элементіне сәйкес келуі, немесе бірде-бір элементіне сәйкес келмеуі мүмкін. Бұл ескертуді түсіндіретін мысалдарды өздеріңіз оңай-ақ келтіре аласыз.

Жиындар арасындағы сәйкестік ұғымы математикадағы негізгі ұғымдарының қатарына жатады. Олай болатын себебі: бұл ұғым математикадағы функция және бейнелеу сияқты аса маңызды ұғымдарды анықтаудың негізі болып табылады. Сонымен қатар арасындағы кез келген ғылымда объектілердің өздері ғана емес, олардың арасындағы байланыстар да зерттеледі. Мысалы, географияда қалалар жиыны Х және елдер жиыны У арасында ²х қаласы у у еліне қарайды² деген сәйкестік қарастырылады. Қазақ тілінде ²х сөзі у сөз табына жатады ² деген сияқты әр түрлі сөздер жиыны мен сөз таптары жиынының арасындағы сәйкестік кеңінен таралған. Физикада: ²х денесінің массасы у-ке тең²; химияда: ²х затының формуласы у болады².

 Х және У жиындарының арасындағы R сәйкестігінің графигі Х´У декарттық көбейтіндінің ішкі жиыны болатындықтан, ХУдекарттық көбейтіндінің графигі туралы айтылғандардың бәрі R сәйкестігінің графигі үшін де тура болады.

Мысалы, Х={а, в, с}, ал У={m,n} болсын және G={<а,m>, <в, m>, <с,n>, <в,n>}- берілген Х және У жиындарының арасындағы қайсыбір R сәйкестігінің графигі болсын. Онда - суретте көрсетілген нүктелердің жиыны берілген R сәйкестігінің графигін кескіндейді.

Декарттық көбейтінді сияқты Х және У жиындарының арасындағы R сәйкестігінің графигін де тік бұрышты координаталар системасында нүктелер жиыны ретінде кескіндеуге болады. Мысалы, егер Х={5, 10}, У={1, 2, 3} және G={<5, 1>, <10, 1>, <10, 2>}-Х және У жиындарының арасындағы қайсыбір R сәйкестігінің графигі болса, онда координаттық жазықтықта координаталары G жиынының жұптары болатын барлық нүктелерді салатын болсақ, ол R сәйкестігінің графигі болады (20-сурет).

Егер Х=У=R, ал сәйкестік алдағы мысалдағыдай болса, онда ол сәйкестіліктің графигі түзу сызық болады (22-сурет).

 

Кері сәйкестік

Осы граф арқылы аÎУ элементінің Х жиынының екі элементіне - 1 және 2 сандарына -сәйкес екендігін де анықтауға болады. Басқаша айтқанда, аÎУ элементі бойынша керісінше а элементіне сәйкес келетін Х жиынының элементтерін табуға болады. Осы процесті жүзеге асыру үшін біз У жиынынан ²шығып² Х жиынына ²келеміз²(24-сурет). Мұндай жағдайда Х және У жиындарының арасындағы R сәйкестілігіне У және Х жиындарының арасында кері сәйкестік бар болады дейді. R сәйкестігіне кері сәйкестікті R^-1 түрінде белгілейді (оны ²эрдің минус бір дәрежесі² деп оқиды). R^-1 сәйкестігінің графы R сәйкестігінің графындағы стрелкаларын кері бағыттаудан келіп шығады.

Біздің мысалымызда Х және У жиындарының арасындағы R сәйкестігінің графигі мынадай: {<1, а>, <1, в>, <2, а>, <2, в>, <2, с>}, ал R сәйкестігіне кері У және Х жиындарының арасындағы R^-1 сәйкестігінің графигі мынадай жиын болады: {<а, 1>, <в, 1>, <а, 2>, <в, 2>, <с, 2>}, яғни егер R сәйкестігінің графигіндегі оған тиісті әрбір жұптың компоненттерінің орындарын ауыстырса, онда R^-1 сәйкестігінің графигі келіп шығады.

R және R^-1 сәйкестіктерін тік бұрышты координаталар системасында кескіндегенде олардың графиктері өзара қандай байланыста болатынын анықтайық. Х={-3, -2, -1, 0} және У={0, 1, -2} жиындарының арасындағы ²хÎХ саны уÎУ санынан аз² деген R сәйкестік бар болсын. Сонда R сәйкестігінің графигі {<-3, 0>, <-3, 1>, <-3, -2>, <-2, 0>, <-2, 1>, <-1, 0>, <-1, 1>, <0, 1>} болады да, тік бұрышты координаталар системасында 25-суретте көрсетілген сегіз нүкте болады.

Берілген сәйкестікке кері R^-1 сәйкестігінің графигі мынадай болады: {<0, -3>, <1,-3 >, <-2, -3>, <0, -2>, <1, -2>, <0, -1>, <1,-1>, <1, 0>}. Оның координаттық жазықтықтағы кескінін сіздер 26-суреттен көріп отырсыздар.

Сонымен, егер Х және У жиындарының арасындағы сәйкестік R болса, онда У және Х жиындарының арасындағы уR^-1х, уÎУ, хÎХ болатындай R^-1 сәйкестігі хRу болғанда және тек сонда ғана R сәйкестігіне кері сәйкестік болып табылады.

Кері сәйкестік ұғымын біз жиі пайдаланамыз. Бірнеше мысал келтірейік.

Х - әр түрлі қазақ сөздерінің жиыны, ал У - қазақ тіліндегі сөз таптарының жиыны болсын. Осы жиындардың арасында ²х сөзі у сөз табына жатады² деген сәйкестік бар (мысалы, ²үй²сөзі - зат есім, ²жаз² - сөз -етістік т.с.с.). Осы сәйкестікке кері У және Х жиындарының арасындағы сәйкестік ²у сөз табына х сөзі жатады² (мысалы, зат есімге ²үй²сөзі, етістікке ²жаз² сөзі жатады деп айтамыз) түрінде айтылатын болады.

Егер Х - әлемдегі мемлекеттер жиыны, ал У - олардың астаналарының жиыны болатын болса, онда Х және У арасындағы R сәйкестігі ²х мемлекетінің астанасы у² деген түрде болуы мүмкін. Онда У және Х жиындарының арасындағы R^-1 сәйкестігін біз ²у қаласы - х мемлекетінің астанасы² деген түрде тұжырымдауымыз керек.