Применение теории графов на уровне "ЕГЭ"

1.

Применение теории графов на уровне "ЕГЭ"
ПРЕЗЕНТАЦИЮ ПОДГОТОВИЛИ: КОТОВ ДЕНИС, ШОМПОЛОВ МИХАИЛ, ДОРСКИЙ КОНСТАНТИН 102 ГРУППА ИФТИС

2.

Цель
презентации:
Разобраться что такое
граф, где его можно
применять, а также
донести эту
информацию до
слушателей.

3.

Что такое
граф?
Граф - это
топологичекая
модель, которая
состоит из множества
вершин и множества
соединяющих их
рёбер. При этом
значение имеет
только сам факт,
какая вершина с
какой соединена.

4.

Определения
Два ребра называются смежными, если у них есть
общая вершина.
Два ребра называются кратными, если они соединяют
одну и ту же пару вершин.
Ребро называется петлей, если его концы совпадают.
Степенью вершины называют количество ребер, для
которых она является концевой (при этом петли
считают дважды).
Вершина называется изолированной, если она не
является концом ни для одного ребра.
Вершина называется висячей, если из неё выходит
ровно одно ребро.
Граф без кратных ребер и петель называется
обыкновенным.
Путем называется последовательность вершин

5.

Классификации
По степени отношения к
математкие
-
Математические
-
Нематематические
По видам применяемых графов
-
-
простые графы, то есть не
мультиграфы, орграфы или
псевдографы;
мультиграфы и псевдографы, но не
орграфы;
По областям применения
-
Приложения к экономике и
исследованию операций.
-
Комбинаторные задачи.
-
Головоломки к игры.
-
простые орграфы;
-
Паросочетания.
-
(псевдо)орграфы.
-
Технические приложения.
-
Естественные науки.

6.

Виды графов

7.

Первое использование теории
Швейцарский, прусский и российский математик
Леонард Эйлер в статье (на латинском языке,
изданной Петербургской академией наук) о
решении знаменитой задачи о кёнигсбергских
моста, датированной 1736 годом, первым
применил идеи теории графов при доказательстве
некоторых утверждений. При этом Эйлер не
использовал ни сам термин «граф», ни какие-либо
термины теории графов, ни изображения графов.
Леонард Эйлер считается отцом теории графов
(как и топологии), открывшим понятие графа, а
1736 год назначен годом рождения теории графов.

8.

Примеры
применения в жизни
Теория графов широко
применяется в
решении
экономических и
управленческих задач,
в программировании,
химии,
конструировании и
изучении
электрических цепей,
коммуникации,
психологии,
социологии,
лингвистике и в других
областях.

9.

Примеры применения в IT
Реальный пример использования графов это sea-of-nodes JIT-компилятора. JITкомпилятор строит граф потока данных и граф
потока выполнения, в которых узлы - это
инструкции программы, а рёбра - это порядок
вызова инструкций и порядок присвоения данных
переменным, потом ищет способы этот граф
оптимизировать и по оптимизированному графу
генерирует бинарный код. Если кратко, то это
упрощение и оптимизация кода.

10.

Решение задач ЕГЭ(Графы)

11.

Решение задач ЕГЭ(Графы)

12.

Решение задач ЕГЭ(Фано)

13.

Решение задач ЕГЭ(Теория игр)

14.

Решение задач ЕГЭ(Рекурсия)

15.

Спасибо
за
внимание!