Өндірістік үрдістерде графтар теориясын қолдану

 

Және  2) барлық тұтынушылардың қажеттіліктері толығымен қанағаттандырылуы тиіс,яғни

       x₁₁+x₂₁+...+x_m1=b₁

      x₁₂+x₂₂+...+x_m2=b₂

     – – – – –  – – – – –                                                               (1.27)

x_1n+x_2n +...+x_mn=b_n

i-жабдықтаушыдан j-тұтынушыға  тасымалданатын жүк мөлшері теріс емес санға тең болғандықтан, есептің математикалық моделіне оған енетін айнымалылардың теріс емесін шарты қосылады.

                          x_ij ≥0 (i= j= )                                  (1.28)    

Сонымен, тасымалдау есебінің (көлік есебінің) математикалық моделінің жалпы түрде жазылуын былайша беруге болады:

                             

                             

             x_ij =b_j(j= )

            

             x_ij≥0(i= ; )

 

Теорема.  Tасымалдау есебінің оптималь шешімі болуы үшін барлық жабдықтаушылардағы жүк қоры мөлшерінің барлық тұтынушылардың қажеттіліктерінің мөлшеріне тең болуы қажетті және жеткілікті, яғни

            

       a_i=  b_j                                                                                             (1.29)

шартының орындалуы қажетті және жеткілікті.

       (1.29) шарты орындалатын тасымалдау есебін жабық моделді тасымалдау есебі жабық моделді тасымалдау есебі деп атайды. (1.29) шарты орындалмайтын тасымалдау есебін ашық моделді тасымалдау есебі деп атайды. Ашық моделді тасымалдау есебін шешу үшін оны жабық моделді тасымалдау есебіне келтіреді. Егер a_i > b_j

болса, онда  b_n+1= a_i – b_j жалған тұтынушы қосылады, яғни

                             

жоспарлау кестесіне бір бағана қосылады. Жүк бірлігін тасымалдаудың бағасы нөл деп алынады.

 

                                                                     

Егер   а_i < b_j    болса ,  онда а_m+1= b_j -  а_i       жалған жабдықтаушы қосылады яғни жоспарлау кестесіне бір қатар қосылады .Жүк бірлігін тасмалдау бағасы нөл деп алынады.

 

 

ІІ  тарау . Графтар теориясы және оны қолдану.  

2.Графтар теориясының анықтамалары және негізгі теоремалары.

 

G – графы деп (V(G),E(G))- жұбын айтамыз, онда (V(G)) – төбелер  деп аталатын, бос емес аяқталатын элементтер жиыны, E(G))-қабырғалар деп аталатын, (V(G))-элементтер жұбынан тұратын аяқталған реттелмеген жиынтық. «Жиынтық» сөзін қолдану, қысқа қабырғаларды қолдануға болатындығын айқындайды. (V(G))-қабырғалар жиыны деп атайды. Ал E(G))-G-графының қабырғалар жиынтығы. -түріндегі әрбір қабырғаға ол  және - төбелерін жалғап тұрады деп айтады. - әрбір түйіні төбесін өз-өзімен жалғайды.

Графтарды суреттерде немесе схемаларда бейнелегенде кескіндер  тік сызықтық немесе қисық сызықты  болуы мүмкін; кескіндердің ұзындығы және нүктелердің орналасуы еркін.

 

Орграф анықтамасы

D – орграфы деп  (V(D), A(D)) – жұбын айтамыз, онда V(D) – төбелер деп аталатын, бос емес аяқталатын элементтер жиыны, ал A(D) – доға деп аталатын реттелген V(D) – элементтер жұбынан тұратын аяқталған семействосы.  - төбесі бірінші элемент, ал - төбесі екінші элемент болып табылатын доға - дан - ға - доғасы  деп аталады.

 

Графтар теориясының  негізгі теоремалары

Жоғарыда келтірілген графтар теориясының анықтамасына сүйене отырып, теоремалардың келбетін және дәлелдерін келтірейік, олар өзінің қолданбаларын есептерді шешу барысында табады.

Теорема 1. кез – келген графтың төбелер дәрежесінің екеселенген қосындысы оның қабырғалар санына тең.

Дәлелдеуі: - осы графтың төбелері, ол - бұл төбелердің дәрежесі делік. Әрбір төбеден түсетін қабырғалар санын санап шығайық, сосын осы сандарды қосайық. Бұл барлық төбелердің дәрежелер қосындысын табумен бірдей. Осылайша есептегенде әрбір қабырға екі рет ескерілетін болады.

Бұдан p(A₁)+р(А₂)+ ... +p(A_n)=0,5N, немесе 2(p(A₁)+р(А₂)+ ... +p(A_n))=N , бұл жерде N – қабырғалар саны.

Теорема 2. кез – келген графтың тақ төбелерінің саны жұп болады.

Дәлелдеуі: a₁, a₂, a₃, …, a_k –графтың жұп төбелерінің саны, ал b₁, b₂, b₃, …, b_m - графтың тақ төбелерінің саны делік.

a₁+a₂+a₃+…+a_k+b₁+b₂+b₃+…+b_m- қосындысы граф қабырғаларының санынан екі есе артады. a₁+a₂+a₃+…+a_k - қосындысы жұп, онда b₁+b₂+b₃+…+b_m – жұп болуы керек. Бұл тек m- жұп сан болған кезде ғана болуы мүмкін, яғни графтың тақ төбелерінің саныда жұп болып табылады.

Бұл теорема бірнеше қызықты  қорытындыға ие:

1. Қорытынды. Кез-келген компаниядағы таныстардың тақ саны әрдайым жұп.
2. Қорытынды. Тақ қабырғалар саны бірігетін көп қабырғалылық төбелер саны жұп.
3. Қорытынды. Бір - бірінің қолын тақ сан рет алған барлық адамдар саны жұп болып табылады.

Теорема 3. n-төбелі кез-келген графта, онда , әрдайым бірдей дәрежелі екі немесе оданда көп төбелер табылады.

Дәлелдеуі: Егер графтың n-төбесі бар болса, онда олардың әрбірі     0, 1, 2, ..., (n-1) – дәрежесіне ие болуы мүмкін. Шыныда да, егер р(А)=0 болса, онда бұл А –оқшауланған төбе екендігін білдіреді, сондықтан графта р(Х)=n-1 дәрежелі Х- төбесі табылады. Шын мәнінде бұл төбе (n-1) төбесімен қосылуы тиіс, соның ішінде А мен де, бірақ бізде А оқшауланғанғой. Бұдан шығатыны, n  төбеге ие графта, бір мезгілде 0 және (n-1)  дәрежесі бар төбелер болуы мүмкін емес.

Бұл дегеніміз, n төбелерде екі бірдей дәрежеге ие төбелер табылады деген.

Теорема 4. Егер n төбелі графта , тек қана бір жұп бірдей дәрежеге ие болса, онда бұл графта әрдайым жалғыз оқшауланған төбе немесе барлық төбелермен қосылған жалғыз төбе табылады.

Бұл теореманың дәлелін біз қарастырмаймыз. Бұл теореманың мазмұны келесі есеп арқылы жақсы түсіндіріледі: n - оқушылар санынан тұратын топ суреттермен алмасуда. Уақыттың кейбір мезгілінде екеуі бірдей алмастырулар санын жасағаны айқындалды. Оқушылар арасында алмастыруды бастамаған немесе оны аяқтап қойған оқушы бар екендігін дәлелдеу керек.

 

2. Графтың түрлері: толық, толық бағытталған граф, екі үлесті граф.

 

Толық граф

  Толық граф деп аталады, егер оның әрбір екі бөлек төбелері тек қана бір қабырғамен қосылған болса. Толық графта оның әрбір төбесі бірдей қабырғалар санына тәуелді. Толық графты беру үшін оның төбелер санын білу жеткілікті. n - төбесі бар толық граф әдетте  - арқылы белгіленеді.

Толық емес графты  дәл  сол төбелерімен жетпей тұрған қабырғаны қоса тұрып толық графқа айналдыруға болады. G – графының төбелері және қосылған қабырғаларда графты құрайды. Мұндай граф G – графының толықтауышы деп аталады және - арқылы белгіленеді. G- графының толықтауышы деп, G- графындағы дәл сол төбелермен және толық граф алу үшін  G- графына қосатын тек қана сол қабырғалармен құралған -графы болып табылады.

Граф толық немесе толық еместігі, бұл жалпы оның мінездемесінің мақсатында.

Толық бағытталған  граф

Толық бағытталған граф деп төбелерінің әрбір жұбы бір  бағытталған қабырғамен қосылған графты айтамыз. Егер толық бағытталған графтың әрбір қабырғасынан бағытты алып тастасақ, онда қабырғалары бағытталмаған толық граф пайда болады.

Әрбір  команда қалған командалардың  әрқайсысымен бір реттен ойнап шығатын  жарысты  қарастырайық. Мұндай жарысты бір айналымды турнир деп атайды.

Егер әрбір кездесу міндетті түрде бір команданың жеңісімен аяқталу керек болса, онда айналмалы турнир компромисты емес деп аталады. Мұндай турнир мысалы, валейбол мен баскетболда жүргізіледі.

                                                          

Әрбір турнирге толық  бағыттлған граф сәйкес келеді, онда төбелер  командалар болып есептеледі, ал әрбір  бағытталған қабырға    жеңіс - қатынасын білдіреді.

 

Екі үлесті граф

          Графтың төбелер жиынын екі қиылыспайтын жиыншаға және бөлуге болады деп есептейік, G графындағы  әрбір қабырға -ге кейбір төбесін - нің кейбір төбесімен қосады, онд G – ны екі үлесті граф деп атаймыз. Мұндай графтарды кей кезде - деп белгілейді, егер екі көрсетілген жиыншаны  ерекшелегісі келсе . Екі үлесті графты басқаша да анықтауға болады: оның төбе төбелерінің екі түспен  бояу терминдерінде айталық қызыл және көкпен. Бұл жағдайда граф екі үлесті деп аталады, егер оның әрбір төбесін қызыл немесе көк түспен бояуға боатын болса және бұл кезде кез – келген қабырғаның бір соңы қызыл, ал екіншісі – көк болуы керек. Екі үлесті графта - дің әр бір бұрышы - ның әр бір төбесі  мен қосылу міндетті емес, егер ол сондай болса және де осы кезде граф G қарапайым болса, онда ол толық екіүлесті граф деп аталады және әдетте - арқылы белгіленеді, онда - сәйкесінше және - дегі төбелер саны.

 

Мысалы,          

                                                                жұлдызды граф

 

  

 

 

 

 

  - графы дәл  - төбелер және - қабырғаларға ие екендігін ескерейік.

 

3.Шыңдар (төбелер) дәрежесі.

Графтағы төбелер бір  – бірімен, олар қанша қабырғаларға сәйкес келетіндігімен  ерекшелінеді. Төбе дәрежесі деп, осы төбе сәйкес келетін графтың қабырғалар санын айтамыз. Төбе жұп деп аталады, егер оның дәрежесі – жұп сан болса. Төбе тақ деп аталады, егер оның дәрежесі тақ сан болса. Екі төбесі біріктірілген деп аталды, егер оларды біріктіретін  қабырға бар болса, яғни - түріндегі қабырға; бұл жағдайда және - төбелері осы қабырғаға инцидентті деп аталады, ал қабырға – осы төбелерге инцидентті. Осылайша, графтың екі бөлек қабырғасы біріктірілген деп аталады, егер  олар кем дегенде бір ортақ төбеге ие болса. Әйтпесе төбенің дәрежесін анықтауға болады.

G- графының  - төбесінің дәрежесі  немесе валенттігі деп   - ға инцидентті қабырғалар санын айтамыз, төбе дәрежесін - арқылы белгілейміз. төбесінің дәрежесін есептеген кезде күйіні 2 рет ескереміз. 0 дәрежелі төбе оқшауланған төбе деп аталады, бірінші дәрежелі төбе ілініп тұрған немесе соңғы төбе деп аталады. Барлық төбелері бірдей дәрежеге ие графты жүйелі граф деп атайды.

G₁ және G₂ – графтары изоморфтық деп аталады, егер олардың төбелері жиындарының арасында қарама – қарсы бірмәнді сәйкестік бар болса, ол G₁ - ге кез – келген екі төбені біріктіретін қабырғалар санын G₂ – де сәйккес төбелерді біріктіретін қабырғалар санына тең болатын қасиетіне ие.

Граф турлы жалпы тусінікке ие бола отырып, кейбір кезде оның төбелерінің дәрежесі туралы айтуға болады. Осылайша толық графтың әрбір төбесінің дәрежесі оның төбелер санынан бірге кем. Бұл кезде төбелер дәрежесімен байланысты кейбір ережелер тек қана толық графтарға тән емес.

1. G- графында оның барлық төбелер дәрежесінің қосындысы – графтық екі еселенген қабырғалар санына тең жұп сан, өйткені әрбір қабырға бұл қосынды да екі рет қатысады. 200 – жыл алдын Эйлерге танымал болған бұл нәтижені жиі қол – алу леммасы деп аталады. Бұдан шығатыны, егер бірнеше аджам қол алысқан болса онда қол алысқан қолдардың саны міндетті түрде жұп, өйкені әрбір қол алысуда екі қол қатысады.
2. Кез – келген графтың тақ төбелер саны жұп болады.
3. n - төбелі әрбір графта, әрдайым кем дегенде бірдей дәрежелі екі төбе табылады.
4. Егер төбелі графта дәл екі төбе бірдей дәрежеге ие болса, ондаа бұл графта дәл бір 0 - дәрежелі төбе немесе дәл бір   дәрежелі төбе әрдайым табылады.

 

Графтың байланысуы

  Графты байланысқан деп атаймыз, егер оны екі графтың бірігуі түріндегі көрініске келмесе және байланыстырушы емес – кері жағдайда.

Берілген G- графтағы маршрут  деп  көрінісіндегі қабырғалардың аяқталған тізбегін айтамыз.

Маршруттың келесі қасиеті анық: кез - келген екі тізбектелген қабырғалар біріктірілген немесе бірдей. Бірақ осы қабілетке ие барлық қабырғалар тізбегі маршрут болып табылмайды. (мысал ретінде жұлдызша графты қарастырайық және оның қабырғаларын  кез- келген тәртіпте алайық). Әрбір маршрутқа - төбелер тізбегі сәйкес келеді. - бастапты төбе деп аталады, ал - маршруттың соңғы төбесі. Осылайша, біз -ден -ге маршрут туралы айтамыз. Кез-келген төбесі үшін тривиальды маршрут болып қабырғалары жоқ, -ден -ға болып маршрут болып табылады. Маршруттың ұзындығы деп ондағы қабырғалар санына айтылады. Маршшрут тізбек деп аталады, егер оның барлық қабырғалары әр-түрлі болса, және қарапайым тізбек деп аталады, егер барлық төбелер әр-түрлі болса, - дан тыс болуы мүмкін. Кем дегенде бір қабырғаны қамтитын қарапайым біріккен тізбек цикл деп аталады. Кез-келген түйін немесе кез-келген екі еселенген қабырғалар жұбы циклды құрайды. - төбесінен - төбесіне дейін болған ара-қашықтық қарапайым деп аталады, егер ол графтың ешбір төбелерінен бір реттен артық өтпесе.