💡 Что это такое?

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

Для наглядного отображения объектов используются условные графические изображения (образные элементы), зачастую дополняемые числами, символами и текстами (знаковыми элементами).

💡 Важно понимать

Часто бывает так, что одну и ту же вещь можно показать по-разному. Например, устройство твоего смартфона можно нарисовать как схему блоков, а можно — как детальный чертёж.

🎯 Ключевые особенности схемы

Схема — это представление некоторого объекта в общих, главных чертах с помощью условных обозначений. Схемами может быть представлен и внешний вид объекта, и его структура.

Схема как информационная модель не претендует на полноту предоставления информации об объекте. С помощью особых приёмов и графических обозначений на ней более рельефно выделяется один или несколько признаков рассматриваемого объекта.

🌐 Граф в соцсетях

Представь соцсеть: каждый человек — это вершина, а дружба между людьми — это ребро. Вот тебе и граф!

📖 Условие задачи

Река Преголя в центре старинного Кёнигсберга (ныне Калининград) разделяется на два рукава. В некоторых местах эти рукава соединены протоками. Благодаря одной такой протоке центр города оказался разбит на четыре части, которые со временем соединили мостами.

Известна старинная математическая задача: можно ли пройти по всем семи мостам центра Кёнигсберга, не проходя ни по одному из них дважды?

✅ Решение Эйлера (1736 год)

Впервые эта задача была решена в 1736 году математиком Леонардом Эйлером, обозначившим части города точками, а соединяющие их мосты — линиями. Благодаря этому исходная задача свелась к следующей: можно ли обойти данный граф, не отрывая карандаш от бумаги, так, чтобы каждое его ребро было пройдено ровно один раз?

🔬 Правила Эйлера

Исследовав множество аналогичных графов, Эйлер установил:

• Если у графа все вершины чётные (т.е. из каждой вершины выходит чётное число рёбер), то такой граф можно обойти, не отрывая карандаш от бумаги; начинать можно в любой вершине
• Если у графа две нечётные вершины, то его можно обойти, не отрывая карандаш от бумаги; начинать надо в одной из нечётных вершин, а закончить — в другой
• Граф с более чем двумя нечётными вершинами обойти, не отрывая карандаш от бумаги, невозможно

🎓 Исторический факт

1736 год считается годом рождения теории графов, а Леонард Эйлер — её основоположником.

Определив чётность вершин A, B, C и D (все они нечётные!), ты можешь самостоятельно завершить решение задачи о мостах Кёнигсберга. Подсказка: это невозможно!

🎯 Анализ графа

Граф на рисунке — направленный ациклический граф. Обратите внимание на вершину A: это единственная вершина графа, в которую не входит ни одна дуга, а все дуги из неё выходят. A — начальная вершина (источник) рассматриваемого графа.

Что касается вершины E, то есть входящие в неё дуги, но нет ни одной дуги, выходящей из неё. E — конечная вершина (сток) рассматриваемого графа.

💡 Решение

Шаг 1: В вершину E можно попасть только из вершин C и D. Если мы будем знать число путей из вершины A в вершину C и из вершины A в вершину D, то, сложив их, получим искомое число путей из A в E.

Шаг 2: В вершину C можно попасть непосредственно из вершины A и из вершины B. В свою очередь, существует единственный путь из вершины A в вершину B. Таким образом, из вершины A в вершину C можно попасть двумя путями:

1 (напрямую из A) + 1 (через B) = 2

Шаг 3: Что касается вершины D, она является конечной вершиной для трёх дуг: BD, AD и CD. Следовательно, в неё можно попасть из вершин A, B и C:

1 (напрямую из A) + 1 (через B) + 2 (через C) = 4

Шаг 4: Теперь выполним подсчёт путей из A в E:

2 (через C) + 4 (через D) = 6

Ответ: 6 различных путей.

⚡ Лайфхак

Решение задачи будет гораздо проще, если двигаться от вершины A (начало маршрута) к вершине E и проставлять веса вершин — число путей из A в текущую вершину. При этом вес вершины A можно принять за 1. Действительно, существует единственный способ попасть из A в A — оставаться на месте.

📖 Условие задачи

На берегу реки стоит крестьянин (К) с лодкой, а рядом с ним — собака (С), лиса (Л) и гусь (Г). Крестьянин должен переправиться сам и перевезти собаку, лису и гуся на другой берег.

Однако в лодку, кроме крестьянина, помещается либо только собака, либо только лиса, либо только гусь. Оставлять же собаку с лисой или лису с гусём без присмотра крестьянина нельзя: собака представляет опасность для лисы, а лиса — для гуся.

Как крестьянин должен организовать переправу?

💡 Решение

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

Каждую вершину-состояние переправы обозначим овалом и свяжем рёбрами с состояниями, образованными из неё.

• Непустимые по условию задачи состояния выделены пунктирной линией
• Начальное и конечное состояния переправы выделены жирной линией

✅ План переправы (одно из решений)

1. Крестьянин перевозит лису
2. Крестьянин возвращается
3. Крестьянин перевозит собаку
4. Крестьянин возвращается с лисой
5. Крестьянин перевозит гуся
6. Крестьянин возвращается
7. Крестьянин перевозит лису

На графе видно, что существуют два решения этой задачи!

💡 Вывод

С помощью графов можно решать и разные занимательные задачи!

🎯 Ключевое свойство дерева

Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь.

🔍 Проверь себя

Внимательно рассмотри дерево на рисунке выше и ответь на вопросы:

• Сколько у этого дерева вершин?
• Какова высота этого дерева?
• Приведи пример поддерева в этом дереве
• Приведи примеры вершин 1-го, 2-го, 3-го и 4-го уровня

🏛️ Применение деревьев

Всякая иерархическая система может быть представлена с помощью дерева.

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

💡 Решение без построения дерева

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

• В разряде сотен может быть любая из цифр 1 и 2
• В разряде десятков — те же два варианта
• В разряде единиц — те же два варианта

Число различных вариантов: 2 · 2 · 2 = 8

📐 Правило перемножения

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

🎯 Анализ игры

Ход игрока I: Может убрать одну спичку (останется 4) или сразу 2 (останется 3).

Если останется 4 спички: Игрок II может своим ходом оставить 3 или 2 спички.

Если останется 3 спички: Игрок II может выиграть, взяв две спички и оставив одну.

Если после хода игрока II осталось 3 или 2 спички: Игрок I в каждой из этих ситуаций имеет шанс на выигрыш.

✅ Вывод

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

🎲 Что такое дерево игры?

На рисунке представлен граф, называемый деревом игры; на нём отражены все возможные варианты, в том числе ошибочные (проигрышные) ходы игроков.

Дерево игры — один из вариантов игровых моделей, используемых при моделировании действий противоборствующих сторон в ходе соревнований, конкуренции в бизнесе и даже военных действий.

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