Презентация, доклад Информационные модели на графах

графическую форму при решении практических задач и задач из сборника подготовки к ЕГЭ.

из точек и линий.

При изображении графов на рисунках или схемах отрезки могут быть прямолинейными или криволинейными; длины отрезков и расположение точек произвольны.

4 этапов. Лена бежала от А до Б, Вася – от Б до В, Света – от В до Г и Миша – от Г до Д. Начертите маршрут эстафеты.

Задача 3 б) «Зарница»
Эстафета военно-спортивной игры «Зарница» включала в себя этапы:
Е – транспортировка раненого;
F – передвижение по минному полю;
G – разведение костра
Время прохождения эстафеты засекается по возвращению команды в исходную точку Е.

пара вершин.

Граф называется связным, если любая пара его вершин — связная.

станциями.

Укажите граф, соответствующий таблице.

1)

3)

2)

4)

D

E

Леонарду Эйлеру.

Его называют идеальным математиком 18 века.
Эйлер принадлежит к числу гениев, чьё творчество стало достоянием всего человечества.

Его работа о графах появилась в1736 году в публикациях Петербургской Академии Наук начиналась с рассмотрения задачи о кенигсбергских мостах.

на двух островах этой реки.

Берега реки и два острова соединены семью мостами.

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

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

Задача о Кёнигсбергских мостах.

Леонард Эйлер изобразил при построении графа берег реки и острова – точками(вершины графа), а мосты – его ребра.

Петербурга 13 марта 1736 года, он сформулировал следующее правило:
если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка.

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

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

практике при изображении различных иерархий.

Графы - деревья.

Адам

Сиф

Мафусаил

Авель

Каин

Енох

на три
Запишите порядок команд в программе получения из 11 числа 13, содержащей не более 5 команд, указывая лишь номера команд.
Например: 21222.

Задача

номера:
Вычти 1
Умножь на 3
Запишите порядок команд в программе получения из 3 числа 16, содержащей не более 5 команд, указывая лишь номера команд.
Например: 21112.

номера:
Прибавить 2
Умножь на 3
Запишите порядок команд в программе получения из 0 числа 28, содержащей не более 6 команд, указывая лишь номера команд.
Например: 211121.

кучки камней, в первой из которых 4, а во второй 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или прибавляет 2 камня в какую-то кучу. Выигрывает игрок после хода которого общее число камней в одной из куч становится не менее 21 одного камня. Кто выигрывает при безошибочной игре обоих игроков- игрок, делающий первый ход, или игрок делающий второй ход? Как должен ходить выигрывающий игрок?

почти в любой отрасли науки и техники встречаешься с графами:

в физике – электрические цепи;

в химии – кристаллические решетки молекул;

в математике при изучении логических задач;

в информатике - двоичные деревья позволяют перебрать все возможные варианты и никогда не повториться, а так же в топологии локальной сети.

Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера:
1. Вычти 3
2. Умножь на 2
Напишите программу, содержащую не более 5 команд, которая из числа 5 получает число 25. Укажите лишь номера команд.

2. Задача на поиск выигрышной стратегии.
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 4, а во второй – 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 24 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

3. Задача Эйлера о парижских мостах.
Можно ли прогуляться по Парижу, пройдя в точности один раз по каждому из 15 мостов? Возвращаться в начальную точку не обязательно. Если такой обход существует, найти его. Если нет, объясните, почему не может существовать такой маршрут. Изобразите план города в виде