Граф, вершина, ребро. Представление задачи с помощью графа

1. Граф, вершина, ребро. Представление задачи с помощью графа.

2. Часть родословного дерева потомков Николая Бернулли

3. Схема молекулы химического вещества (глицерина)

4. Схема метро

5. Радиосхема простейшего радиоприемника

6.

ЧТО ОБЩЕЕ ВО ВСЕХ ЭТИХ СХЕМАХ?
ОНИ ПОКАЗЫВАЮТ СВЯЗИ МЕЖДУ
ОТДЕЛЬНЫМИ ЭЛЕМЕНТАМИ
Для изображения и изучения
связей между различными
объектами, предметами или
понятиями в математике
применяется граф.

7.

Леонард Эйлер
(1707г – 1783гг)
Швейцарский, прусский и российский математик
Теория графов зародилась в ходе
решения головоломок двести с
лишним лет назад.
Основы теории графов как математической
науки заложил в 1736 г. Леонард Эйлер,
рассматривая задачу о кенигсбергских мостах.
Сегодня эта задача стала классической.

8.

Графом называется конечное множество точек,
некоторые из которых соединены линиями.
При этом точки называются вершинами графа,
а линии — рёбрами.
Рёбра можно изобразить дугами или отрезками.
Каждое ребро соединяют две вершины. Вершина
не обязательно должна быть соединена с
другими вершинами.
Если из вершины не выходит ни одно ребро, то
её называют изолированной.
В графе неважно взаимное расположение
вершин, а только сами вершины и связи между
ними. Иногда при изображении графа рёбра на
рисунке могут пересечься, но эта точка не
является
вершиной
графа.

9.

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

10.

Нужно стараться изображать графы как можно проще и яснее. Если с
первого раза не получилось, то лучше перерисовать граф в удобном виде.

11. Задание 1

На рисунке изображены графы. Сколько у каждого из них ребер, вершин,
изолированных вершин?

12. Задание 2

Одинаковы ли графы, изображенные на рисунке?

13. Задание 3

На рисунке изображён граф. С
помощью
движения
вершин
изобразите этот граф так, чтобы рёбра
не пересекались во внутренних точках
(получатся два одинаковых графа).

14. Задание 4

15. Задание 5

16. Задание 6

Вершина Откуда?
Б
Кол-во
путей
А
А, Б, Г
А
1
3
1
Ж
Б+В
Г
В+Е
4
1
4
И
Д
4
К
И+Д+Ж+Е
13
В
Г
Д
Е

17. Задание 7

Ответ: 2

18. Задание 8

В первенстве класса по настольному теннису принимали участие 5 учеников:
Андрей, Борис, Галина, Олег, Елена.
Первенство проводилось по круговой системе – каждый участник играет с каждым из остальных один
раз.
К настоящему моменту некоторые игры уже проведены:
• Андрей сыграл с Борисом, Галиной и Еленой;
• Борис с Андреем и Галиной;
• Галина с Андреем и Олегом.
Сколько игр проведено к настоящему
моменту и сколько ещё осталось?

19. Решение

Андрей сыграл с Борисом, Галиной и Еленой;
Борис с Андреем и Галиной
Галина с Андреем и Олегом.
Андрей
Борис
Галина
Олег
Ответ: сыграно 5 партий,
Елена
осталось 5 партий.

20. Домашнее задание:

1. Реши задачу с помощью построения графа. Ребята, которые дружат,
могут помочь друг другу с подготовкой к контрольной работе. Известно,
что Сергей дружит с Димой и Дашей, Варвара — с Димой и Таней, Виктор —
с Евой и Василисой, Ксения — с Василисой. Может
ли Сергей помочь Василисе подготовиться к контрольной работе?

21. Использованные источники:

• https://www.yaklass.ru/p/veroyatnost-i-statistika/7-klass/teoriiagrafov-7271003/vvedenie-v-teoriiu-grafov-7270309/re-4bbdca77de80-4537-8aea-74d804fb4f69