Графтар теориясы жана анын элементтери

ЖАЛАЛ-АБАД МАМЛЕКЕТТИК УНИВЕРСИТЕТИ

ЖАЛАЛ-АБАД КОЛЛЕДЖИ

АЧЫК САБАКТЫН ИШТЕЛМЕСИ

Предмет: Дискреттик математика

Тема: Графтар теориясы жана анын элементтери

Окутуучу: Полотова А.З.

Тайпа: БАСк-2-18

Жалал-Абад – 2020

Тема: Графтар теориясы жана анын элементтери

Сабактын түрү: Практикалык сабак.

Сабактын жабдылышы: ватман, маркерлер, карточкалар, көрсөтмө куралдар, проектор.

Сабактын жүрүшү: 1. Сабакты уюштуруу

2. Үй тапшырмасын текшерүү

3. Кайталоо үчүн жана жаңы темага өбөлгө түзүүчү суроолор:

- Граф деген эмне жана кандай белгиленет?

- Граф түшүнүгү ким тарабынан жана качан негизделген?

- Графтын кандай түрлөрүн билесиңер?

- Графтын кандай касиеттери бар?

- Графтын үстүнөн кандай амалдар аткарылат?

- “Граф” деген термин ким тарабынан киргизилген?

- Графтардын колдонулуштарын атап бергиле.

Ж аңы теманы түшүндүрүү: Графтар теориясы – графтардын касиеттерин үйрөтүүчү дискреттик математиканын бөлүгү. Графтар заманбап турмуштун чиеленишкен проблемаларыны чечүү үчүн колдонулуп келе жатат. Ал: экономика, методология, соода-сатык, ташып жеткирүү планы сыяктуу бир катар тармактарды өз ичине камтууда. Графтар көптөгөн проблемаларды аныктоодо жана структуралык карым-катнаштарды белгилөөдө пайдалуу, б.а. жолдордун, газ түтүкчөлөрүнүн, жылуулук жана электр тармактарынын схемалары сүрөттөлөт. Ошондой эле, билимдин түрдүү областарында: автоматикада, электроникада, физикада, химияда, биологияда графтардын жардамында маселелердин чыгарылыштары жөнөкөйлөтүлөт.

Графтар теориясы 1736-жылдагы Л.Эйлердин “кенигсберг көпүрөлөрү жөнүндөгү маселени” чыгарылышын аныктаганы менен пайда болгон. Леонард Эйлер (1707-1783) – математик, физик, астроном,механик. Ал эми, “граф” термини биринчи жолу 200 жылдан кийин, 1936-жылы Венгер математиги Денеш Кениг тарабынан киргизилген.

Аныктама: Граф чоку деп аталган чекиттер менен бул чекиттерди туташтырган кабырга деп аталган чиймелердин жыйындысы.

Чокулардын көптүгүн , ал эми кабыргалардын көптүгүн

аркылуу белгилейбиз. V чокусу жана U кабыргасы аркылуу берилген G граф аркылуу белгиленет.

Графтардын үстүнөн төмөндөгүдөй амалдар аткарылат:

1. Биригүү

2. Кесилишүү

3. Графтардын тегеректелген суммасы.

Мисалы: жана графтарынын биригүүсүн, кесилишин, тегеректелген суммасын тап.

Ч ыгаруу:

1-тапшырма. Жуптарда иштөө: мисалдар жазылган карточкалар студенттерге таркатылып, эсептөө үчүн убакыт берилет.

№1. 0 жана 1 цифраларын колдонуп, үч орундуу канча сан жазса болот?

Ч ыгаруу.

Жообу: Баары 4 үч орундуу сан жазууга болот.

№2. Илимий конференцияга келген 5 окумуштуу бири-бири менен кол алышып учурашышты.

Баары канча жолу кол алышып учурашылды?

Ч ыгаруу:

Жообу: 10 жолу.

№3. Токойдо 6 жаныбар жолугуп калышты: карышкыр, түлкү, жолборс, аюу, маймыл жана пил.

Алар бири-бири менен кол алышып учурашышты. Кол алышып учурашуу канча жолу болду?

Ч ыгаруу:

5+4+3+2+1=15.

Жообу: 15 кол алышып учурашуу болот.

№4. Мектеп участкасында 8 дарак өсүп турат: алма, терек, кайың, гларс, эмен, ак чечек, өрүк жана

мажрум тал. Гларс өрүктөн бийик, алма ак чечектен бийик, эмен кайыңдан жапыз, бирок мажрум

талдан бийик, мажрум тал гларстан бийик, терек кайыңдан бийик, өрүк алмадан бийик.

Дарактардын бийиктиги боюнча төмөндөн жогору карай жазгыла.

Ч ыгаруу:

Жообу: Ч-А-Ө-Г-М-Э-К-Т.

№ 5. Берилген таблицаны пайдаланып граф түзгүлө.

Чыгаруу:

№6. Төмөндөгү графтын матрицасын жазгыла. Чыгаруу:

№7. Айназиктин 2 конверти болгон: жөнөкөй жана

авиалык, ошондой эле, үч маркасы болгон: тик

бурчтуу, квадрат, үч бурчтуу. Катты жөнөтүш

үчүн Айназик конверт менен марканы канча жол

менен тандашы мүмкүн.

Жообу: 6 жол менен тандашы мүмкүн.

№8. Керим 6чы этажда, Искендер 9чу этажда жашайт. Болот жана Самат – Керимден жогору ,

Искендерден төмөн жашашат. Ал эми Самат Болоттон төмөн жашайт. Болот жана Самат ар бири

канчанчы этажда жашашат.

Чыгаруу: “Жогорку” катышына карата иштейбиз.

Жообу: Самат 7чи этажда, Болот 8чи этажда жашашат.

№9. Күн системасындагы 9 планетада өз ара космостук байланыш маршруту түзүлгөн. Рейстик ракеталар төмөнкү маршруттар бюнча жүрүшот: Жер – Меркурий, Плутон – Венера, Жер – Плутон, Плутон – Меркурий, Меркурий – Вененра, Уран – Нептун, Нептун – Сатурн, Сатурн – Юпитер, Юпитер – Марс, Марс – Уран. Ушул рейстик ракеталар менен Жерден Марска учса болобу?

Ч ыгаруу:

Жообу: Графта көрүнүп тургандай Жерден Марска учса болбойт.

№10. A, B, C, D, E айылдарынын арасында жолдор курулган. А айлынан Е айлына баруунун эң кыска

жолун тапкыла, эгерде: (A,B)=1, (B,C)=2, (C,D)=3, (D,E)=4,(E,B)=2,(D,B)=7.

Ч ыгаруу:

Жообу: А-В-С-D=6 – эң кыска жол.

2-тапшырма. Топтордо иштөө: топторго бөлүп, суроолор берилет, убакыт бөлүнөт, өз жоопторун ватманга жазып, ар бир топтон 2ден студент чыгып презентация жасайт. Башка топтордун суроолоруна жооп беришет.

1-топ. A, B, C, D айылдарынын арасында жолдор курулган, ал жолдор ар бир эки айылды бириктирип

турат. D айлында почта жайгашкан. Почтальон каттарды калган үч айылга жеткирип келүүсү

керек. Эгерде айылдардын арасындагы аралыктар: (A,B)=7, (B,C)=6, (C,D)=6, (A,D)=8, (A,C)=11,

(B,D)=10 берилсе, анда почтальон жүрүүчү эң кыска жолду тапкыла.

Жообу:

2-топ. көптүгүндө катышындагы графты түзгүлө жана анын

матрицасын жазгыла.

Жообу:

3-топ. Графын келип чыгышын, колдонулушун, түрлөрүн, касиеттерин чагылдырып көрсөткүлө.

Кроссворд . Суроолору:

1. Чокулардын жана кабыргалардын жыйындысы?

2. Графтар териясын ким негиздеген?

3. Чокуларды бириктирген сызык эмне деп аталат?

4. Бир чокудан чыгып кайра ошол чокуга кирген сызык?

5. Граф терминин киргизген окумуштуу?

6. Графтагы чекиттер?

7. Багытталган кабырга?

8. Дарактагы кабыргалар эмне деп аталат?

10. Илимдердин падышасы?

Жыйынтыктоо: Студенттер менен биргеликте өтүлгөн теманы талкуулоо.

Үй тапшырма: №11. графтарынын биригүүсүн тап. Чыгаруу:

Баалоо.

9