Презентація до факультативу з математики "Графи"

1 5 6 3 4 2 7 8 1 5 6 3 4 2 7 8 Вчитель математики Соромотіна О.О. Графи та їх застосування

Сім мостів Кенігсберга – видатна історична задача з математики. Доведення неможливості її розв'язання Леонардом Ейлером у 1735 році привело до створення теорії графів. Історія виникнення графів

Г р а ф и Графи - це малюнки, які складаються з точок і ліній, що з'єднують ці точки.

Карти зіркового неба Схеми авіаліній Графи є істотним елементом математичних моделей в найрізноманітніших галузях науки і практики

Мережі доріг України Приклади графів

Схема водопостачання Приклади графів

Схема структурної формули хімічної сполуки Схема електричного ланцюга Приклади графів у науці

Вершини графа Ребра графа Степінь вершини графа Неповні графи Повні графи Неорієнтований граф Орієнтований граф Ейлеровий граф Зважений граф Основні поняття в теорії графів

Вершини Ребра Точки називаються вершинами графа. Лінії називаються ребрами графа.

п=2 (парна) п=3 (непарна) п=2 (парна) п=1 (непарна) п=1(непарна) Степінь вершин графа Кількість ребер, що виходить з вершини графа, називається степінь (n) вершини графа. Вершини графа, що мають непарну степінь, називають непарною, а вершини графа, що мають парну степінь, називають парною.

1. У повного графа кожна вершина сполучена ребром з кожною вершиною, крім самої себе. 3. Якщо у повного графа n вершин, то всього сполучень (ребер) - n(n-1)/2 Повний граф 2. Якщо у повного графа вершин n, то з кожної вершини виходить сполучень (ребер) n-1.

Орієнтований граф – це граф, ребрам якого присвоєно напрямок Орієнтований граф

Якщо ребрам (дугам) графу приписані деякі ваги (мітки, додаткова інформація), то такі графи називаються зважені або відзначені графи Зважені (відзначені) графи

Ейлеровий граф – це зв'язний граф, який містить ейлеровий цикл. Ейлеровий шлях – це шлях, який проходить по всім ребрам, і лише по одному разу. Якщо цей шлях замкнутий, то це – ейлеровий цикл Граф називається зв'язним, якщо існує хоча б один маршрут між будь-якими двома його вершинами. Ейлеровий граф

Будь-яку замкнену фігуру, що має 2 непарні вершини, можна накреслити одним розчерком без повторень, почавши в одній з непарних вершин, та закінчивши у іншій.  Якщо зв'язна фігура немає жодної непарної вершини, то існує ейлерів цикл, що можна почати у будь-якій вершині графа. Ознака, якою користуються для знаходження ейлерового шляху Приклад ейлерового графа Саблі Магомета Приклади ейлерових графів

Задача Вільяма Гамільтона – кругосвітня подорож Застосування графів Графи і підрахунки комбінацій Моделювання задач за допомогою графів Графи в іграх та головоломках Графи і логічні задачі

Розв'язання Число 5 5 2 5 5 5 5 5 2 2 2 2 2 2 Сотні Одиниці Десятки Числа 555 552 522 255 252 225 222 525 Задача про кількість трицифрових чисел Знайдіть всі тризначні числа, які можна скласти з цифр 5 і 2

Задача про шаховий турнір У шаховому турнірі прийняли участь сім учнів. За правилами турніру кожен учасник грає з кожним один раз. Вже зіграно декілька партій, причому: Василь зіграв шість партій; Максим зіграв п'ять партій; Семен і Антон - по три партії; Іван і Денис – по дві партії; Євген – одну партію. Знайди: з ким зіграв Антон.

Розв'язання задачі про шаховий турнір Побудуємо граф з сімома вершинами (за кількістю учасників турніру). Позначимо вершини буквами: Василь – В, Євген – Є, Максим – М, Іван – І, Денис – Д, Антон – А, Семен – С. Кількість зіграних партій – це степінь вершини. Розмірковуємо: 1)Василь зіграв шість партій, отже він зіграв з усіма учасниками. Тому розпочинаємо заповнювати граф ребрами з вершини В. 2) Євген зіграв одну партію, то більше ребер з вершини Є не виходить. 3) Далі однозначно можна визначити сполучення з вершини М - п'ять ребер (всі, крім Євгена). 4) Всі можливі ребра побудовані для вершин В, Є, М і для тих, у кого зіграно по дві партії – І, Д. 5) Залишилися Семен і Антон. Сполучення вершин С і А дасть по три сполучення для цих вершин. Отже, Антон зіграв з Василем, Максимом і Семеном.

В М Є С І Д А 6 5 3 3 2 2 1 В М Є С І Д А 6 5 3 3 2 2 1 В М Є С І Д А 6 5 3 3 2 2 1 В М Є С І Д А 6 5 3 3 2 2 1 1. 2. 3. Відповідь Граф до задачі про шахи

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

Ч Ч С З Ж Ж З С Розв'язання задачі про олівці у коробках Позначимо точками олівці та коробки. Суцільна лінія буде означати, що олівець лежить у потрібній коробці, а пунктирна, що не лежить. Отже маємо граф, в якому з кожної вершини (олівець) виходить до вершини (коробка) одна суцільна лінія, а інші – пунктирні, в залежності від умови задачі.

Задача 1 Розв'яжи самостійно Клоун Бам, Бім, Бом вийшли на арену цирка в червоній, синій та зелених сорочках. Їх черевики були таких же кольорів. Черевики і сорочка Біма були одного кольору. На Бомі не було нічого червоного. Туфлі Бама були сині, а сорочка ні. Якого кольору були сорочка та черевики у клоунів Бім та Бом.

Задача 2 А С В Розв'яжи самостійно З міста А в місто В ведуть три дороги, а з міста В в місто С ведуть чотири дороги. Скількома способами можна проїхати з міста А в місто С.

Завдання: 1. Які основні ознаки для креслення графа одним розчерком олівця? 2. Знайди інші фігури, які можна накреслити одним розчерком. Дізнайся самостійно! Побудова фігур одним розчерком олівця. Всім знайома задача: Не відриваючи олівця від паперу і не проводячи по одній лінії двічі накреслити “відкритий конверт”.

Маргарита Артем Поліна Свєта Антон Паша Оля Коля Женя Іра Діма Марина Женя ? Дякую за увагу! Граф дружби учнів 6 класу