Графы вокруг нас (1)

1.

Дороги
Графы вокруг нас
Метро
Соцсети

2.

Что общего между этими
думаете,
ми? что объединяет эти
кта
ъевы
обКак
системы?
а ро
ем
СхПере
До
писк
ги а
орода
метр
го
Всё это описывается одной математической
моделью — ГРАФОМ! Сегодня мы научимся видеть
графы в окружающем мире и использовать их для
анализа данных.

3.

Основные понятия теории
Верш
гра
Степ
фо
ень
вин
верш
граф
иныПример графа
ный
шен
оина
Граф
Ребр
Взве
Объе
кт:
ба, е,
станц
р ояни
друж
расст
ия метр
гон,
и:
рёбе
Колич
2
в) ивек,
пере
:ниям
о, чело
ество
4 сество
значе
связе
объе
выми
йктами
вебуверш
у (узло
число
межд
Множ
Связь
Граф
31
5
стран
ица
Вершины:
A, B, C, D, E, F
объек
ата
я
(связей)
ссылк
врем
Рёбра: AB, AC, BC, CD, CE, EF

4.

Графы в реальной
Соц
ь ь
иал
Веб
ро
сет
ьна
ая
-гра
мет
я сет
ожн
ма
ф
Схе
Дор
и
зн
жи
Верш
ины:
люди
ины:
Верш
Вершины:
(пользоват
ели)
и о
метр
ии
рёстк
станц
перек
веб-страницы
(с связи
оны
дружги
перег
еские
Рёбра: доро
Рёбр
я)
иями
врем
станц
у—
межда:
весом
гиперссылки

5.

«Граф в
тминутк
ь
л
у
к
з
и
Ф
движении»
а
Най
дит
ее
ньт
Ста
Соз
дай
те
рёб
ра!
2
3тро
ь!
пут
йте
Пос
4
1
степ
ень
!
Дви
и!
жен
нам
ие
ши
«Сое
пом
вершина
вер
дини
рьшин
огае
чку
Посч
т
цепо
итай
звас
луч
с сосед
те,сооб
ше
чере
ый
скол
ом
пон
окна
кажд
ько
спра
до
—
ять
и—
рук
ва
вер
пожа
двер
класс
прот
от
лиу—
е»по
янит
тесь
ы, рёбра и
это
щени
еиз
ести
руку
ваша
разм
, тепе
те
это
степ
итесь»
ребр
едай
ень
ньте
о
«Пер
Вста
а
граф
верш
граф
ин
а степ
ени!
ины
верш

6.

хема школьного
«С
1:
е
ни
да
За
Время:
Группа
1 12
Расс
чита
Опре
йте
дели
путь
те
степ
ени
» кабинет
ный
граф
«важ
ете
рой
дит
Най
Пост
»
ия
ан
зд
Кратч
айши
Посч
минут
как вершины и
й
итайт
путь
е,
от
сколь
кабин
еты школ
ко
ета
двере
кабин
дирек
истепе
ей
й унью
тораыдо
оры
кажд
ольш
ого
е корид
с наиб
разит
Изоб
Кабинет
спорт
зала
кабин
ета
рёбр
вершаины
Пример графа школы
Материалы
План школы Каб. 1
Директор
Лист
А3
Маркеры
Линейка
Спортзал
Каб. 2

7.

Задание 2: «Чат
Время:
12
Группа
2 расп
Обсу
дите
рост
Найд
ите
ние
акти
вны
хране
учас
куски
епи
тников
исти
пер
стат
граф
те
йте
кл
ита
рой
ас
Пост
Посч
са
»
Как распр
остра
нялас
й ения
Опре
ь
ново
дели
вчер
сть?
минут
те
за
по
степе
ения
а вероя
в писал
ни
сообщ
верш
—
тност
ин,Каков
участавовал
ь получ
кто
ки,а рёбр
класс
учени
—ент
боль
проц
шеашни
Верш
Какойины
сообщения?
всех
день
переписке?
Пример
графа чата
Материалы
Скриншот чата
Маша
Петя
Анна
Лист А3
Маркеры разных
Ваня
цветов
степень 4
Катя

8.

орожная сеть
«Д
3:
е
ни
да
За
Время:
Группа
3 12
Проа
нали
Доба
зиру
вьте
йте
маршру
веса
загр
ц йужен
ьны
ули
мал
ностть
граф
опти
ете
рой
дит
Най
Пост
а»
он
ай
ор
кр
ми
Какие
пере
минут
Укаж
крёст
ите
доро
ки
—
врем
самы
а
ным
я прое
е загру
рёбр
маль
и,
мини
сзда
женн
рёстк
на
каждо
парка
доперек
(по
ы—
м ые?ги
ины
Верш
От школ
степе
ни) она
участ
ке
орай
микр
временем
Пример взвешенного
Материалы
графа
Карта
5 мин
микрорайона
ЛистШкола
А3
Маркеры
3 мин
Калькулятор
Пер-к 1
4 мин
Парк
1 мин
Пер-к 2
2 мин

9.

Презентация результатов
зентации (1-1,5 минуты на группу)
матппре
Фор
Время:
6
минут
гр
уп
Группа «Шк
ола»
т»
«Дор
«Ча
оги»
й граф
Како
1Вопрос:
построили
3 ь со статистикой
Каки
2 е выводы сделали Связ
Моде
«Како
й
нится
вапроце
нт лировани
«Как изме
Стати
Процстика
енты
путей
прохо
тность,
дит+ е
вероя
граф, если
+ степень
через
й сть
этот
сть
новы
ново
ить
что
добав вероятно
перек
рёсто
до всех
ёт
к?»
ет?»
дойд
кабин
за день?»

10.

я: что мы узнали
си
ек
фл
Ре
Графы — универсальный язык описания связей в
сего
мир
е! дня?
я
одн
пон
«Сег
«Я
«Мн
е ял,
что
узна
я был
ол,
истиока
что
стат
инте
ресн
ы т…»
огае
граф
пом
стро
ить
найти
есть…»
граф
…»
активных
о
в метр
это
как
карта
ь
делит
опре
загру
тяхость
в соцсе
это
какженн
схема
выяв
гах
можн
на доро
оить
всё
ые узлы
важнть
связа
е
школ
в
рассчитать
наглядно и
пути
понятно

11.

Домашнее
задание
Выполните одно задание на выбор:
Маршрут до
ей
друзмер
Граф при
Свой
шко
лы
2
3
1
Проан
ализи
ойте
те
руйте
умайграф
Постр
Прид
схему
своег
й веррута до
о марш
друзе
прим
свой
ти
школы
и
соцсе
как граф
из жизн
графа
с
) ия в пути)
весам
иимно
его
(врем
ите
опиш
и(анон
свою
ски
найдите
атиче
матем
«степень
влиятельности»
Спасибо за урок!