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

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

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

ТЕХНИКАЛЫК ЖАНА МААЛЫМАТТАРДЫ ИШТЕТҮҮ БӨЛҮМҮ

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

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

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

Жалал-Абад - 2019

Сабактын максаты:

• Графтын аныктамасын жана анын түрлөрүн билишет.
• Графтардын үстүнөн жүргүзүүлүүчү амалдарды аткарышат жана түрдүү маселелерди чыгарууда графтарды колдонушат.

Баалоо үчүн критерийлер

• графтын аныктамасын билсе;
• графтын түрлөрүн билсе;
• графтардын үстүнөн жүргүзүүлүүчү амалдары аткара алса;
• графты пайдаланып маселе иштей алса;
• сабакка активдүү катышса;
• топтордо иштей алса;
• мисал иштөөдө формулаларды колдоно алса.

Кайталоо үчүн жана практикалык сабакка өбөлгө түзүүчү суроолор:

• Граф деген эмне жана кандай белгиленет?
• Граф түшүнүгү ким тарабынан жана качан негизделген?
• Графтын кандай түрлөрүн билесиңер?
• Графтын үстүнөн кандай амалдар аткарылат?

Графтар теориясы :

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

Граф

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

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

Биригүү

1.

Кесилишүү

2.

Тегеректелген сумма

3.

Мисалы

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

1-тапшырма (жупта иштөө)

№ 1

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

№ 2

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

№ 3

Токойдо 6 жаныбар жолугуп калышты: карышкыр, түлкү, жолборс, аюу, маймыл жана пил. Алар бири-бири менен кол алышып учурашышты. Кол алышып учурашуу канча жолу болду?

№ 4

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

№ 5

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

Төмөндөгү графтын матрицасын жазгыла:

№ 6

№ 7

Айназиктин 2 конверти болгон: жөнөкөй жана авиалык, ошондой эле, үч маркасы болгон: тик бурчтуу, квадрат, үч бурчтуу. Катты жөнөтүш үчүн Айназик конверт менен марканы канча жол менен тандашы мүмкүн.

№ 8

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

№ 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.

”

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

9

4

5

3

6

8

7

С

Ы

Й

Ы

Р

Т

М

А

К

К

Е

Н

И

Г

Э

Й

Л

Е

Р

Г

Ч

Р

О

К

А

Ф

У

Ж

К

А

А

А

Б

Ы

Р

Г

А

М

Т

М

Б

У

Т

К

Уй тапшырма

• Графтардын биригүүсүн, кесилишүүсүн,

тегеректелген суммасын тапкыла.