Графические информационные модели. Использование графов при решении задач. Моделирование и формализация

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

Необходимо знать!
Граф — это совокупность объектов со связями между ними. Вершины — это объекты, а рёбра — связи.
Взвешенный граф — это граф, в котором вершины или рёбра характеризуются некоторой дополнительной информацией — весами вершин или рёбер.
Цепь — это путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза.
Цикл — это цепь, в которой начальная и конечная вершины совпадают.
Сеть — это граф с циклом.
Семантическая сеть — это информационная модель, имеющая вид графа, вершинам которого соответствуют определённые объекты, а рёбра задают отношения между ними.
Дерево — это граф, в котором нет циклов, то есть в нём нельзя из некоторой вершины пройти по различным рёбрам и вернуться в ту же вершину.

Задача 1
У Маши есть 2 конверта: обычный и экспресс
чтобы отправить письмо?
— и 3 марки: круглая, прямоугольная
и треугольная.
Сколькими способами Маша может выбрать конверт и марку,
П
О
Э
К
П
Т
К
П
Т
Ответ: Маша может выбрать конверт и марку шестью разными способами.

Задача 2
На дополнительное занятие по физической культуре пришло восемь учащихся:
Саша, Маша, Таня, Артём, Женя, Лёша, Настя и Юра.
Давайте поможем ребятам выстроиться по росту.
Владимирович попросил их построиться по росту.
Известно, что Саша выше Маши,
Таня выше Артёма,
Учитель Николай
Женя ниже Лёши, но выше Насти,
Настя выше Саши,
Лёша ниже
Юры,
а Маша выше Тани.
С
Ю
Н
Л
Ж
А
Т
М
1.
2.
3.
4.
5.
6.
7.
8.

Задача 3
Крестьянин купил на базаре козу, кочан капусты и волка.
По дороге домой нужно
было переправиться через реку.
У крестьянина была очень маленькая лодка,
в которую кроме него могла поместиться только одна из его покупок.
Как ему переправить все товары через реку, если нельзя оставлять козу наедине
с капустой и волка наедине с козой?

Задача 3
Крестьянин, волк, коза, капуста.
Волк, коза, капуста.
Крестьянин.
Коза, капуста.
Крестьянин, волк.
Волк, капуста.
Крестьянин, коза.
Волк, коза.
Крестьянин, капуста.
Волк, капуста,
крестьянин.
Коза.

Задача 3
Волк, капуста,
крестьянин.
Коза.
Капуста.
Крестьянин, волк, коза.
Капуста, крестьянин. Волк, коза.
Крестьянин, капуста, коза. Волк.
Капуста, коза. Волк, крестьянин.
Коза. Крестьянин, капуста, волк.
Волк.
Крестьянин, капуста, коза.
Волк, крестьянин. Капуста, коза.
Крестьянин, волк, коза. Капуста.
Волк, коза. Крестьянин, капуста.
Крестьянин, коза.
Капуста, волк.
Крестьянин, коза, капуста, волк.

Задача 3

Задача 4
Сколько трёхзначных чисел можно составить из четырёх цифр: 1, 2, 3, 4?
1
2
3
4
1
2
3
4
1
2
3
4
1
2
3
4
1
2
3
4
1
2
3
4

Задача 4
Сколько трёхзначных чисел можно составить из четырёх цифр: 1, 2, 3, 4?

Задача 4
Комбинаторное правило умножения
…
Сколько трёхзначных чисел можно составить из четырёх цифр: 1, 2, 3, 4?