АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Мысалы.

Прочитайте:
  1. Мысалы.

 

Теорема 1 (В.Г. Визинга). ,

мұнда - ең көп төбелік дәрежесі.

(дәлелдеусіз)

Ескерту. Кейбір графтар үшін нақты нәтижелер алынған.

Теорема 2. .

Теорема 3 (Кёниг). .

ДС 13. Бүркитін ағаштар.

 

Анықтама 1 Ағаш деп бағдарсыз байланысқан циклсіз граф аталады оны басқаша да анықтауға болады төбесінен және қабырғасынан тұратын байланысқан граф. Бағдарсыз байланысқан графы үшін, әр ағашы, мұндағы , созылатын ағаш деп аталады (каркас, кереге). Мұндай ағаштардың қабырғалары бұтақтары, ал графтың басқа қабырғалары – хордалары деп аталады.

 

Анықтама 2 графының орманы деп - графының ағашының k - керегесі аталады, мұндағы k – -дағы компоненттер саны. Егер графы компонентіне ие болса, онда кез келген графының ағашының k-керегесі үшін . графының орманы графының ағашының k-керегесі мен бірге болғандықтан, компоненттерінің әрқайсысы -ның компоненттерінің біреуінің керегесі болу керек. Осылайша компоненттерінен құралған -дан тұратын графының орманы компоненттерінен құралған р-дан тұрады, -дің керегесі, .

 

Созылатын ағаштарды табу үшін тереңдігі мен енін табу процедурасын қолдануға болады.

Созылатын ағашты тереңдікте табу алгоритмі.

2 массив алынады:

СТЕК – бірөлшемді массив

АҒАШ ­­­­­­– екіөлшемді

 

Қадам 1. Туынды төбесін табамыз, СТЕК массивіне қосамыз және белгіленген деп есептейміз.

Қадам 2. СТЕК массивінен белгіленген төбені қарастырамыз, яғни АҒАШтың массивіне қосылмаған қабырға бар ма, жоқ па соны қарастырамыз, цикл пайда болмайды деген шартпен:

а) иә – 3 қадамға өту;

б) жоқ – 4 қадамға өтеміз.

Қадам 3. Осындай қабырғаның біреуін таңдаймыз (мысалы, ең аз нөмірлі төбеге бағытталған). Бұл қабырғаны АҒАШ массивіне қосамыз, ал бұл қабырғаның ақырғы төбесін СТЕК массивіне қосамыз және оны белгіленген деп санаймыз. 2 қадамға өтеміз.

Қадам 4. СТЕК массивіндей бірінші төбе белгіленген бола ма:

а) иә – алгоритм өз жұмысын тоқтатады, АҒАШ массивінде ізделінді созылатын ағаш орналасқан;

б) жоқ – 5 қадамға өтеміз.

Қадам 5. СТЕК массивінен соңынан екінші төбені тағы да СТЕК массивіне қосамыз, оны белгіленген деп санаймыз және 2-ші қадамға өтеміз.

Ескерту 1 Егер графтың барлық төбелері СТЕК массивіне кірмесе, онда графы байланыспайтын болады, алгоритмнің жұмысын жалғастыру арқылы, созылатын орман салуға болады.

Мысал 1 Тереңдікті іздеу арқылы созылатын ағашты табу керек (сурет 1.5).

Сурет 1.5 – алғашқы граф

 

Есептің шешуінің қадамы 1.1 кестеде берілген, тереңдікті іздеу арқылы табылған созылатын ағаш 1.6 суретінде көрсетілген.

 

Кесте 1.1

Есептің шешу қадамы

СТЕК                      
АҒАШ 1 - 2 2 - 3 3 - 4 4 - 5 4 - 5   3 - 6        

 

Сурет 1.6 – созылатын ағаш

Алгоритм нахождения стягивающего дерева в ширину.

2 массив алынады:

КЕЗЕК – бірөлшемді массив

АҒАШ ­­­­­­– екіөлшемді

Қадам 1. Бірінші төбені таңдаймыз, КЕЗЕКке енгіземіз, осыдан кейін оны белгілейміз.

Қадам 2. Белгіленген төбелерді қарастырамыз, белгіленген төбеден бастаушы өтілмеген қабырға цикл құрамыз мына шартымен бар ма:

а) иә, 3 қадамға өтеміз;

б) жоқ, 4 қадамға өтеміз.

Қадам 3. Осы барлық қабырғаны АҒАШ массивіне қосамыз, ал бұл қабырғалардың апаратын төбелерін КЕЗЕК массивіне қосамыз, ескі белгіні жоямыз, ал төбені КЕЗЕК массивінен өшіреміз, 2-ші қадамға өтеміз.

Қадам 4. Барлық төбелер қарастырылды ма:

а) иә, 6 қадамға өтеміз;

б) жоқ, 5 қадамға өтеміз.

Қадам 5. Соңынан екінші төбені КЕЗЕК массивіне қосамыз және оны белгіленген деп есептейміз және 2 қадамға өтеміз.

Қадам 6. Алгоритм өзінің жұмысын тоқтатады және АҒАШ массивінде ізделінді созылатын ағаш орналасған.

Мысал 2 Енібойынша табу арқылы созылатын ағашты табу керек(сурет 1.7).

 

Сурет 1.7 – алғашқы граф

 

Есептің шешуінің қадамы 1.2 кестеде берілген, ал созылатын ағаш ені арқылы табылған (сурет 1.8).

 

Кесте 1.2

Есептің шешу қадамы

КЕЗЕК            
АҒАШ 1 - 2 1 - 4 1 - 6 2 - 3 2 - 5  

 

Сурет 1.8 – созылатын ағаш

 

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

Ескерту 3 Қарастырылған алгоритмдер тек бір ғанасозылатын ағаш құруға мүмкіндік береді. Тағы да созылатын ағаштар алгоритм құратыны мәлім.

Минималды және максималды бүркелетін ағаштар мен ормандар

Анықтама 1 графындағы бүркелген ағашы - минималды (максималды), егер оған кіретін қабырғалар салмағының саны осы графтың барлық бүркелген ағаштардың минималы (максималы) болса.

Минималды (максималды) салмақтағы бүркелген ағашты табудың екі алгоритмін қарастырамыз.

Краскала алгоритмі.

1). Қабырғалардың өспейтін салмағы бойынша реттейміз.

2). Өте келе осы қабырғаларды минималды (максималды) бүркелген ағашқа қосамыз, айналым пайда болмауы үшін, осыны да есепке аламыз.

3). Егер барлық қабырғалар қаралып шықса, алгоритм өз жұмысын бітіреді.

Прим алгоритмі.

1). Көптеген төбесін 2 көпшелерге бөлеміз:

Ø, ,

мұндағы көптеген төбелердің қосындылары,

көптеген төбелердің ажыратылғандары

2). Ең кіші (ең үлкен) салмақты қабырғаларын таңдаймыз және төбелерін -ге қосып, -ден оларды шығарамыз.

3). және төбелерін қосатын барлық қабырғалардың ішінен қабырғаларын ең кіші (ең үлкен) салмақпен таңдап, -ды -ден шығарып және -ге қосамыз.

4). Егер -мен сәйкес келіп, ал Ø болса, алгоритм өз жұмысын аяқтайды.

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

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

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

Мысал 1 Краскала және Прим алгоритмі көмегімен бүркелген ағаштың минималды (максималды) салмағын табу керек (сурет 1.9)

Cурет 1.9 – алғашқы граф

 

Краскала алгоритмі.

1) БА минималды салмағы

Есептің шешуінің қадамы 1.3 кестеде берілген, Краскала алгоритмі арқылы табылған бүркелген ағаштың минималды салмағы 1.10 суретте берілген.

 

Кесте 1.3

Есептің шешу қадамы

ҚАБЫРҒАЛАР 1 - 6 2 - 3 4 - 5 1 - 2 5 - 6 3 - 4 3 - 6 3 - 5 2 - 5 2 - 6
САЛМАҒЫ                    

Осылайша, бүркелген ағаштың минималды салмағы:

Сурет 1.10 – бүркелген ағаштың минималды салмағы

2) БА максималды салмағы

Есептің шешуінің қадамы 1.4 кестеде берілген, Краскала алгоритмі арқылы табылған бүркелген ағаштың максималды салмағы 1.11 суретте берілген.

 

Кесте 1.4

Есептің шешу қадамы

ҚАБЫРҒАЛАР 2 - 6 2 - 5 3 - 5 3 - 6 3 - 4 5 - 6 1 - 2 1 - 6 2 - 3 4 - 5
САЛМАҒЫ                    

 

Осылайша, бүркелген ағаштың максималды салмағы:

 

Сурет 1.11 – бүркелген ағаштың максималды салмағы

 

Прим алгоритмі.

1) БА минималды салмағы

Есептің шешуінің қадамы 1.5 кестеде берілген, Прим алгоритмі арқылы табылған бүркелген ағаштың минималды салмағы 1.12 суретте берілген.

 

Кесте 1.5

Есептің шешу қадамы

 

V1 Ø   1,6 1,6,2 1,6,2,3 1,6,2,3,5 1,6,2,3,5,4
V2 V 2,3,4,3,5,6 2,3,4,5 3,4,5 4,5   Ø

 

Осылайша, бүркелген ағаштың минималды салмағы:

 

Сурет 1.12 – бүркелген ағаштың минималды салмағы

 

2) БА максималды салмағы

Есептің шешуінің қадамы 1.6 кестеде берілген, Прим алгоритмі арқылы табылған бүркелген ағаштың максималды салмағы 1.13 суретте берілген.

 

Кесте 1.6

Есептің шешу қадамы

V1 Ø   1,2 1,2,6 1,2,6,5 1,2,6,5,3 1,2,6,5,3,4
V2 V 2,3,4,5,6 3,4,5,6 3,4,5 3,4   Ø

Осылайша, бүркелген ағаштың максималды салмағы:

Сурет 1.13 – бүркелген ағаштың максималды салмағы

 

ДС 14. Қысқа жол туралы тапсырма.

 

Қабырғаларының салмағы теріс емес болған жағдайдағы қысқа жолы туралы тапсырманың шешімі туралы Дейкстр алгоритмін қарастырайық. решения задачи о кратчайшем пути для случая, когда веса ребер (дуг) неотрицательны.

 

Дейкстр алгоритмінің формальды сипаттамасы.

Қадам 1. Бастапқы мәндердің игерілуі. алғашқы (бастапқы) төбесі үшін тұрақты белгісін аламыз, ал қалған төбелер үшін белгісін аламыз. төбесін СТЕК массивіне қосамыз және оны белгіленді деп санаймыз.

Қадам 2. Белгілердің жаңартылуы. СТЕК массивінен төбесін қарастырамыз. төбесінен қабырғаларды жүргізетін барлық төбелері үшін белгілерін жаңартайық: , где – вес дуги

Қадам 3. Белгілерді тұрақты айналдыру. Уақытша белгілермен берілген барлық төбелерден белгісі ең аз болатын төбені іздестіреміз. Осы төбенің белгісін тұрақты деп аламыз және оны СТЕК массивіне енгіземіз. Оны төбесі деп қарастырамыз.

Қадам 4. Егер барлық төбелерде тұрақты белгілер болса, демек бұл белгілер – - тан осы төбелерге қарай бастаушы ең қысқа жолдардың ұзындықтары.

Мысал 1. -тан -ға бағытталған ең қысқа жолды және оның ұзындығын табу керек (сурет 1.22)

 

Сурет 1.22 – алғашқы граф

 

Есептің шешу қадамы 1.8 кестесінде көрсетілген.

СТЕК: 1, 2, 4, 5, 6, 7, 8, 3

 

Кесте 1.8

Есептің шешу қадамы

№ верш. итер1 итер 2 итер 3 итер 4 итер 5 итер 6 итер 7 итер 8
  0              
  ∞ 2            
  ∞ ∞ ∞         11
  ∞   7          
  ∞ ∞   7        
  ∞ ∞     8      
  ∞ ∞ ∞     8    
  ∞ ∞ ∞ ∞     10  

 

. 8 5 2 1

Кейбір қабырғаларының (доға) салмақтары теріс болған кездегі қысқа жолы туралы тапсырманың шешімі туралы Форд алгоритмін қарастырайық.

Мысал. -тан -ға бағытталған ең қысқа жолды және оның ұзындығын табу керек (сурет 1.23)

Сурет 1.23 – алғашқы граф

 

1-ден 3-ке қарай ең қысқа жолды табу үшін Дейкстр алгоритмін қолданайық (кесте 1.9).

 

Кесте 1.9

№ вер 1 итер. 2 итер.
   
  ∞  
  ∞ 1

 

Дейкстр алгоритмі бойынша -тан -ға дейінгі ең қысқа жолдың ұзындығы 1-ге тең. Бұл шындыққа келіспейді. Яғни егер болса, онда Дейкстр алгоритмі қолданылмайды. Келесі айырмашылықтарға ие Форд алгоритмін қолдануға болады:

Қадам 2. Тек қана уақытша белгілері бар төбелердің ғана емес, сонымен қатар төбесінің қабырғаларынан өтетін барлық төбелердің белгілерін жаңартамыз.

 

Қадам 3. Егер барлық төбелер тұрақты белгілерге ие болса, онда алгоритм өз жұмысын тоқтатады.

Мысал 3 -тан -ға бағытталғын ең қысқа жолды және оның ұзындығын табу керек (сурет 1.24)

 

 

Сурет 1.24 – алғашқы граф

 

Есептің шешу қадамы 1.10 кестесінде көрсетілген.

СТЕК: 1,3,2,4

 

Кесте 1.10

Есептің шешу қадамы

№верш итер. 1 итер. 2 итер. 3 итер. 4
  0 0 0 0
  ∞   0 0
  ∞ 1 1 1
  ∞ ∞   1

Ең қысқа жолмен іздейтін алгоритм. Ең қысқа жол туралы топтастырылған есеп.

 

Дейкстра мен Фордтың алгоритмдері дағы тан келетін ең қысқа жолдың тек қана біреуін таба алады. Барлық мүмкіншілікті қысқа тан ға апаратын жолды іздейтін бір алгоритмді қарастырайық. (сурет 1.25)

Сурет 1.25 – алғашқы граф

Алгоритмнің формальді сипаттамасы

Қадам 1. Барлық байланысып тұрған төбелерді алып тастаймыз (мысалы, 9 төбесін аламыз)

Қадам 2. Ең қысқа дан басқа төбелерге апаратын жолдардың ұзындығын табамыз, мысалы, Дейкстр алгоритмін қолданып. (кесте 1.11).

Кесте 1.11

Қысқа жолдардың ұзындығы

N                
               

 

Қадам 3. үшін, алып тастаймыз.

(Мысал: 8 төбесін алып тастаймыз)

Қадам 4. Өшірілгеннен кейінгі алынған доға мен қабырғалардың салмағы сақталған, кері төбелі граф құрамыз. (сурет 1.26).

Сурет 1.26 – кері граф

Қадам 5. Табылған кері графының ең қысқа, төбесінен басқа қалған төбеге жеткізетін жолын табамыз. (кесте 1.12).

 

Кесте 1.12

Ең қысқа жолдардың ұзындығы

N              
             

 

Қадам 6. Тек қана төбелерін қалдырамыз, олар . Қалған және дан басқа төбелерді алып тастаймыз.

Қадам 7. Қабырғалары болатын тек қана қабырғаларын қалдырамыз, оның ішінде - қабырға салмағының матрица элементі. Егер қабырға болса, онда оны доғамен алмастырамыз .(сурет 1.27)

Сурет 1.27 – түрлендірілген граф

 

Қадам 8. графында тан жолдарының барлығын табамыз. Олар ізделінді болады.

Мысал:

дей тан жолдарының барлығын табу үшін іздестіру ағашының тұрғызу алгоритмін пайдалануға болады.

 

Ескерту 1 Егер қабырға (доға) салмағы оң болса ғана бұл алгоритм қарастырылады.

 

Барлық мүмкін жұп төбе арасындағы Флойд қысқаша жолдар іздестіру алгоритмі.

 

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

Қойылған есептің Флойд алгоритмінің шығару жолын қарастырайық.

Флойд алгоритмінің маңызды сипаттамасы.

1). – тек қана бірінші төбесін қоса алатын төбесінен төбесіне келетін қысқа жолдың ұзындығы, егер мұндай жолдар болмаса, онда деп есептейік.

2). Бастапқы шарт: – қабырға салмағы . , мұнда төбелер саны және қысқа жолдың ізделінді ұзындығы болып табылады.

3). деп белгілейік, онда қадам бойынша матрицаларын табу керек.

4). табылған болсын. -ді табу үшін қолданамыз: бірінші төбесі.

Онда қысқаша жол болып, -дан -ға әкелетін, төбесі бар болып саналуы мүмкін:

а) төбелерін құрайтын қысқаша жол;

б) төбеден өтетін қысқаша жол, яғни .

 

Мысал 1 Барлық мүмкін жұптар арасындағы граф төбелерінің қысқаша жолдар арасындағы ұзындығын табу, оған қоса ең қысқаша жолдарды табу. (сурет 1.28)

 

Сурет 1.28 – алғашқы граф

 

Матрица графының төбелерінің алғашқы графын құрайық және алғашқы матрицасын жазып алайық:

 

матрица элементтері осы жолдармен табылады:

Қалған , , , матрицалардың элементтері аналогиялық тәсілмен табылады:

 

Қашықтықтың ізделінді матрицасы:

 

Ескерту 1 табуды жеңілдету үшін келесі теңдіктерді қолдануға болады: , , .

 

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

Мәндестірейік:

1). – -дан -ға жүргізілетін соңғы ең қысқа жолдың нөмірі.

2).

3). Ретті түрде матрицаларды табайық , бұдан матрицасын табу үшін келесі ойларды қолданамыз:

а) егер , онда ;

б) егер ,онда .

Мысалы, :

 

Онда осы матрицаларды ретпен тауып, “кері табуды” қолдана отырып, -дан -ға жүретін ең қысқа жолдардың бірін табуға болады.


ДС 15. Максимал ағыс туралы есеп.

 

Анықтама 1 Ағаш деп бағдарсыз байланысқан циклсіз граф аталады оны басқаша да анықтауға болады төбесінен және қабырғасынан тұратын байланысқан граф. Бағдарсыз байланысқан графы үшін, әр ағашы, мұндағы , созылатын ағаш деп аталады (каркас, кереге). Мұндай ағаштардың қабырғалары бұтақтары, ал графтың басқа қабырғалары – хордалары деп аталады.

 

Анықтама 2 графының орманы деп - графының ағашының k - керегесі аталады, мұндағы k – -дағы компоненттер саны. Егер графы компонентіне ие болса, онда кез келген графының ағашының k-керегесі үшін . графының орманы графының ағашының k-керегесі мен бірге болғандықтан, компоненттерінің әрқайсысы -ның компоненттерінің біреуінің керегесі болу керек. Осылайша компоненттерінен құралған -дан тұратын графының орманы компоненттерінен құралған р-дан тұрады, -дің керегесі, .

 

Созылатын ағаштарды табу үшін тереңдігі мен енін табу процедурасын қолдануға болады.

Созылатын ағашты тереңдікте табу алгоритмі.

2 массив алынады:

СТЕК – бірөлшемді массив

АҒАШ ­­­­­­– екіөлшемді


6. ПРАКТИКАЛЫҚ САБАҚТАР ЖОСПАРЫ

«Графтар теориясы» пән бойынша 5B010900 «Математика»мамандығының студенттеріне арналған

№ 1семестрлік тапсырманы орындау үшін әдістемелік нұсқаулар

№ 1 семестрлік тапсырмада 15 нұсқада 19 есептен бар.

 

Бір нұсқаның мысалын келтірейік:

§2 §3 §4 §5 §6 §7 §8 §9 §10 §11 §12 §13 §14 §15 §16 §17 §18 §19  
 
А11 В12 А15 С13 А10 В1 А15 С2 А10 В1 А15 В14 А8 В1 А15 В9 А10 С6  

 

Барлық есептер Акбердин Р.А., Курсанов А.Г. Сборник задач по теории графов (ч.I). – Петропавловск: СКГУ, 2008 оқулықтан алынған.

 

А деңгейдегі есептер 1 баллмен бағаланады (9 есеп 1 балл = 9 балл).

В және С деңгейдегі есептер 1,5 баллмен (9 есеп 1,5 балл = 13,5 балл).

§ 20 есептері (олимпиадалық есептер) № 1 сесметрлік тапсырманың қосымшасында келтірілген және әрбір есеп 1,5 баллмен бағаланады, яғни, 3 есеп шығаруы жеткілікті болады. (3 есеп 1,5 балл = 4,5 балл).

 

№ 1 семестрлік тапсырманың қосымшасында 30 нұсқа бар, әрбір нұсқада 12 есептен.

 

Бір нұсқаның мысалы:

§ 20 (олимпиадалық есептер)
3.16 3.31 4.26 5.13 6.3 8.20 9.3 10.7 11.6 12.5 13.6 15.3

№ 1- № 10 нұсқаның есптері Мутанов Г.М., Акбердин Р.А. Теория графов. – Алматы: Рауан, 1999 оқулықтан берілген.

№ 11- № 20 нұсқаның есептері Мельников О. И. Занимательные задачи по теории графов. - М.: ТетраСистемс, 2001 оқулықтан берілген

№ 21- № 30 нұсқаның есептері Горбачев Н.В. Сборник олимпиадных задач по математике. - М.: МЦНМО, 2004 оқулықтан берілген.

7. СӨЖ материалдары

5B010900 «Математика» мамандығының студенттеріне арналған

«Графтар теориясы» пән бойынша № 1 семестрлік тапсырма

 

  §2 [1] §3 [1] §4 [1] §5 [1] §6 [1] §7 [1] §8 [1] §9 [1] §10 [1] §11 [1] §12 [1] §13 [1] §14 [1] §15 [1] §16 [1] §17 [1] §18 [1] §19 [1]
нұсқа№
  А11 В12 А15 С13 А10 В1 А15 С2 А10 В1 А15 В14 А8 В1 А15 В9 А10 С6
  А14 (а) В5 А14 С3 А11 В2 А13 С3 А11 В2 А14 В13 А9 В2 А14 В10 А11 В5
  А14 (в) В9 А10 В4 А12 В3 А12 С4 А12 В3 А13 В12 А10 В3 А13 В11 А12 В4
  А14 (г) В10 А9 В5 А13 В4 А11 С6 А13 В4 А12 В3 А11 В4 А12 В12 А13 В3
  А15 (а) В12 А8 В6 А14 В5 А10 В1 А14 В5 А11 В2 А12 В5 А11 В13 А14 В2
  А15 (б) С8 А7 В7 А15 В5 А9 В2 А15 В12 А10 В1 А13 В6 А10 С10 А15 В1
  В4 А9 В4 А7 С5 А7 В1 А15 В1 А7 В1 А15 В1 А6 В9 А12 В3 А5
  В1 А10 В11 А8 С4 А8 В2 А14 В2 А8 В2 А14 В2 А5 В8 А11 В4 А6
  В2 А11 В13 А9 С3 А9 В3 А13 В3 А9 В3 А13 В3 А6 В7 А10 В5 А7
  В3 А12 В15 А10 С2 А10 В4 А12 В4 А10 В5 А12 В4 А7 В6 А9 В10 А8
  В4 А13 С5 А11 С1 А11 В5 А11 В5 А11 В6 А11 В5 А8 В5 А8 В11 А9
  В5 А14 С6 А12 В4 А12 В6 А10 В1 А12 С9 А10 В6 А9 В4 А7 С8 А10
  В6 А15 С3 А13 В3 А13 С4 А9 В2 А13 С10 А9 В7 А10 В3 А6 С9 А11
  В8 А8 С4 А14 В2 А14 С5 А8 В3 А14 С11 А8 В1 А11 В2 А5 В3 А12
  В9 А7 С8 А15 В1 А15 С6 А7 В4 А15 С12 А7 В2 А12 В1 А4 В4 А13

Әдебиет:

1. Акбердин Р.А., Курсанов А.Г. Сборник задач по теории графов (ч.I). – Петропавловск: СКГУ, 2008

Ескерту 1. А есептері 1 баллмен бағаланады (9 есеп 1 балл = 9 балл). Ал В мен С есептері 1,5 баллмен (9 есеп 1,5 балл = 13,5 балл).

Ескерту 2. § 20 есептері (олимпиадалық есептер) № 1 семестрлік тапсырманың қосымшасында келтірілген және әрбір есеп 1,5 баллмен бағаланады, яғни таңдалған 3 есепті шығаруға жеткілікті болады. (3 есеп 1,5 балл = 4,5 балл).

№ 1 семестрлік тапсырманың қосымшасы

олимпиадалық есептер (§ 20)
нұсқа №                        
Мутанов Г.М., Акбердин Р.А. Теория графов. – Алматы: Рауан, 1999
  3.16 3.31 4.26 5.13 6.3 8.20 9.3 10.7 11.6 12.5 13.6 15.3
  3.17(а) 3.32 4.25 5.12 6.5 8.16 9.4 10.8 11.7 12.6 13.8 15.4
  3.18 3.33 4.24 5.11 6.6 8.10 9.5 10.9 11.8 12.7 13.9 15.7
  3.20 3.34 4.23 5.10 6.7 8.8 9.7 10.10 11.9 12.8 13.13 15.8
  3.21 3.35 4.22 5.8(а) 6.8 8.6 9.8 10.17 11.10 12.9 13.17 15.14
  3.23 3.36 4.21 5.7 6.9 7.10 9.9 10.14 11.11 12.10 14.5 15.17
  3.24 3.37 4.20 5.6 6.12 7.9 9.10 10.13 11.12 12.11 14.6 16.10
  3.27 3.29 4.19 5.5 6.13 7.8 9.11 10.12 11.13 12.12(а) 14.9 16.12
  3.28 3.30 4.18 5.4 6.15 7.5 9.12 10.11 11.14 12.13(а) 14.13 16.13
  3.17(в) 3.38 4.16 5.9(б) 6.11 7.6 9.13 10.5 11.5 12.14(а) 14.14 16.14
Мельников О. И. Занимательные задачи по теории графов. - М.: ТетраСистемс, 2001
                         
                         
                         
                         
                         
                         
                         
                         
                         
                         
Горбачев Н.В. Сборник олимпиадных задач по математике. - М.: МЦНМО, 2004
                         
                  107(б)      
                  107(а)      
                         
                         
                         
                         
                         
                         
                         

&n

Дата добавления: 2015-09-27 | Просмотры: 1018 | Нарушение авторских прав

При использовании материала ссылка на сайт medlec.org обязательна! (0.062 сек.)