Графи. Їхнє походження та графічне подання

Тема: «Графи. Їхнє походження та графічне подання »

Мета:

сформувати поняття графа, ознайомити з походженням графів, графічним поданням ,

розвивати математичні здібності учнів,

виховувати  стійкий інтерес учнів до математики,

Тип заняття: засвоєння нових знань

Обладнання: картки із завданням

 

Хід заняття

 

Не все на світі  просто, але є якась закономірність саме в тому, що істина раптово постає крізь ліс ускладнень, в самому простому.

Віталій Коротич

І.Організаційний етап

 

ІІ. Мотивація навчальної діяльності

 

 Задача:

Зустрілися  7 козаків. Відомо, що, що козак  Іван знайомий із 6 козаками, козак Василь – із 5, козаки Юхим і Грицько – із 3, козаки Семен та Петро - із 2, козак Павло – із 1. З ким знайомий козак Грицько?

Відповідь: козак Грицько знайомий з козаками Іваном, Василем, Юхимом

 

 

ІІІ.Засвоєння нових знань

 

ЩО ТАКЕ ГРАФ?

Граф (від грецького «графо», що пишу, креслю, малюю) — це множина точок (вершин графа), деякі з яких сполучені лініями (ребрами графа). При цьому пара вершин може сполучатися декількома ребрами.

 

 

 

 

•          2 вершини
•          1 ребро

 

•           
•          3 вершини
•          3 ребра

 

 

 

•           
•          4 вершини
•          5 ребер
•           

 

 

•           
•          6 вершин
•          6 ребер

 

 

 

Число ребер, що виходять з вершини графа, називається степенем цього графа. Вершина графа, що має непарну степінь, називається непарною, а що має парну степінь - парною.

                               

Степінь вершин:                                                        

А – 1

В – 3

С – 2

D - 2

 

 

 

 

Степінь вершин:

А – 1,       В – 3        С – 2

D – 3        E – 2         F – 1

 

Для того, щоб знайти кількість ребер графа, потрібно додати степені вершин і отриману суму розділити на два.
(1+3+2+3+2+1):2=6
Або сума степенів вершин графа дорівнює подвоєному числу ребер.

Граф називається зв'язним, якщо його не можна розбити на два, не розриваючи  його в якій-небудь вершині. В такому графі можна, перейти по ребрам із однієї вершини в іншу.

Спробуємо побудувати дані фігури, не відриваючи олівця від паперу ( по ребру можемо провести лінію один раз).

Фігури 1,2,4,5 - можна, 3- ні.

Якщо ми визначимо степінь кожної вершини, то побачимо, що граф можна обійти  (по кожному ребру один раз), тільки якщо граф зв'язний та непарних вершин 2 або 0.

 

Прикладами графів є карти автомобіль них доріг чи залізниць, схеми

метрополітенів, генеалогічні дерева.
 

Перетин двох доріг на різних рівнях з усіма спусками

 

                      

 

Перша робота з теорії графів належить Леонардові Ейлеру. Вона була створена 1736 року. Розпочиналася ця робота з розглядання задачі про кенігсберзькі мости.
 

Видатний математик Леонард Ейлер народився у Швейцарії. На запрошен­ня Петербурзької академії наук 1727 року він переїхав до Росії. Наукова спад­щина Ейлера вражає своїм обсягом і різнобічністю. У списку його праць понад 880 назв. Останні 17 років його життя були затьмаре­ні майже повною втратою зору. Але він продовжував творити, як і в молоді роки. Для багатьох поколінь математиків Ейлер був учителем. Матеріали його досліджень увійшли до сучасних підручників із вищої математики.

 

ЗАДАЧА ПРО КЕНІГСБЕРЗЬКІ МОСТИ

Місто Кенігсберг (нині Калінінград) розташоване на берегах і двох островах річки Преголі. Різні частини міста були сполучені мостами, як показано на рисунку. Щонеділі мешканці прогулювалися містом і цікавилися питанням: чи можна вибрати такий маршрут, щоб пройти кожним мостом тільки один раз і повернутися до початкової точки?

ІV.Формування вмінь                     

   Сварливі сусіди 
Мешканці п'яти будинків посва­рилися між собою і, щоб не зустріча­тися біля колодязів, вирішили поді­лити їх так, щоб господар кожного будинку ходив «своєю» стежкою до «свого» колодязя.

Чи можливо це зробити, якщо будинки і колодязі розташовані так, як показано на ри­сунку?

 

Відповідь: так

 

Не відриваючи олівця від паперу

 

Не відриваючи олівця від паперу і не проводячи по жодному з ребер двічі, побудуйте граф, зображений на рисунку. Занумеруйте ребра в тій послідовності, в якій ви їх проходи­ли.

 

V.Підбиття підсумків уроку

 Задача

Чи може бути, що серед  5 козаків, кожний знайомий з трьома?

(ні ,бо для того, щоб знайти кількість ребер графа, потрібно додати степені вершин і отриману суму розділити на два (3+3+3+3+3)/2=7,5, а це неможливо)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Тема: «Розв’язування задач на використання графів »

Мета:

формувати вміння розв’язувати задач на використання графів ,

розвивати математичні здібності учнів,

виховувати зібраність, звичку до систематичної розумової праці

Тип заняття: формування вмінь і навичок

Обладнання: картки із завданням

Хід заняття

І.Організаційний етап

 

ІІ. Актуалізація опорних знань

1.Що називається графом?

2.

Знайдіть степінь кожної вершини.

 

 Які  з вершин парні?

 

 Які непарні ?

 

Знайдіть кількість ребер

 

3. Коли граф можна обійти  (по кожному ребру один раз)?

 

ІІІ. Формування вмінь і навичок

Завдання1

Чи існують графи, у яких n вершин, степені яких дорівнюють:

Так – а,г,е,     ні – б,в,д

 

Завдання2

Міста України з'єднані авіалініями. Зі столиці виходить 15 ліній, з міста Миколаїв - одна, а з кожного з інших міст - по 8 ліній. Довести, що зі столиці можна долетіти до міста Миколаїв (можливо з пересадками).

 

(Побудуємо граф, поставивши у відповідність містам країни вершини графа, а авіалініям - ребра. Взагалі кажучи, граф може виявитися незв'язним. Потрібно довести, що вершини графа, відповідні столиці і місту, належать одній компоненті графа. Це випливає з наслідку з леми про рукостискання, так в іншому випадку компоненти, що містять вершини, що позначають столицю і місто Миколаїв, матимуть рівно по одній вершині непарній ступеня. Тому потрібні нам вершини будуть належати одній компоненті графа, і зі столиці можна долетіти в Миколаїв.)

Завдання №3

Зустрілися  5 козаків. Відомо, що, що козаки  Іван  і Семен знайомі із 4 козаками, козаки Юхим і Грицько – із 3, козак Петро - із 2. З ким знайомий козак Петро? (з Іваном і Семеном)

Відповідь: козак Петро знайомий з козаками Іваном, Семеном

 

Завдання №4

На цирковій арені.

На цирковій арені виступав канатоходець. На висоті трьох метрів від землі на п'яти стовпах був натягнуті канати, за якими він повинен був проходити. Канати були натягнуті так, як це показано на рис.1.

Канатоходець повинен був пройти по восьми канатів таким чином, щоб по кожному з них пройти всього один раз. І це йому завжди вдавалося, хоча він і не повертався в те ж місце, звідки виходив. Але під час одного з виступів обірвався канат №8, і залишилося всього сім канатів (рис.2).

Чи може тепер канатоходець пройти всі канати, проходячи по кожному з них всього раз? Покажіть, як ходив канатоходець, коли всі канати були цілі, і дайте відповідь на поставлене запитання.

Розв’язок:

Коли всі канати були цілі, канатоходець, виходячи з точки А, закінчував свій шлях у точці В (рис.3). Після того, як обірвався канат №8, канатоходець не зможе обійти всі канати по одному разу

 

Завдання №5

Стежки  в саду.

 

 

 

 

 

 

В саду Олександра Івановича стежки прокладені, як це показано на рис. 4, а у Бориса Борисовича - як показано на рис. 5. Хто з них може обійти всі стежки, проходячи по кожній всього один раз?

Відповідь: Олександр Іванович.

 

Завдання №6

Серед жоржин.

Садівник мав квадратну клумбу 4 * 4 метри, на якій він виростив 16 кущів жоржин. Відстань між кущами було 1 метр. Поки кущі ще не розквітли, квітникар обходив усі кущі, йдучи по найкоротшому шляху, але коли чудові квіти розпустилися, садівник обходив їх по найдовшому шляху. До кожної квітки він підходив всього один раз. Як виглядав найкоротший шлях від куща до куща, а як найдовший?

Розв’язок:

Найкоротший  шлях:

1;2;3;4;8;7;6;5;9;10;11;12;16;15;14;13 (рис.6)

        Найдовший шлях:

5;9;13;10;7;4;3;2;1;6;11;16;12;8;15;14 (рис.7)

 

Завдання №7

 Петро, Іван і Василь навчаються в одному класі. Один їздить додому зі школи на автобусі, інший - на трамваї, третій - на тролейбусі. Одного разу після уроків Петро пішов проводити друга до зупинки автобуса. Коли повз них проходив тролейбус, третій друг крикнув з вікна: «Іван, ти забув у школі зошит!» Хто на чому їздить додому?( Іван на автобусі, Петро - на трамваї, Василь- на тролейбусі)

 

Завдання №8

А, Б, В і Г - друзі. Один з них - лікар, інший - журналіст, третій - тренер спортивної школи та четвертий будівельник. Журналіст написав статті про А і Г. Тренер і журналіст разом з Б ходили в похід. А і Б були на прийомі у лікаря. У кого яка професія? (А - тренер спортивної школи, Б - будівельник, В - журналіст і Г- лікар)

Завдання №9

У пляшці, склянці, глечику і банку налиті молоко, лимонад, квас і вода. Відомо, що вода і молоко знаходяться не в пляшці, у банці - не лимонад і не

вода, а посудина з лимонадом стоїть між глечиком і посудиною з квасом. Стакан коштує близько банки і посудини з молоком. Визначте, де яка рідина?

(У пляшці - лимонад, у склянці- молоко,у глечику-вода і у банці-квас)

 

Завдання №10

У парку 9 озер. Кожне озеро пов'язане з іншими озерами не менше ніж 3 каналами. Яка найменша кількість каналів може бути у парку?

Відповідь: 14 каналів.

 

ІV.Підбиття підсумків уроку

 

Що нового ви дізналися?

Чи сподобався вам урок?