Пошаговое объяснение:
Лекция 3
Графы
Чтобы решить какую-то задачу, часто бывает полезно нарисовать картинку, иллюстрирующую её условие. В этой главе мы рассмотрим один вид таких картинок:
«графы». Граф — это набор точек («вершин»), соединённых линиями («рёбрами»).
При этом важно, какие точки соединены, а как именно это ребро нарисовано, не
имеет значения.
Прежде чем давать точные определения соответствующих понятий, мы разберём
несколько задач, в которых подобные картинки .
3.1 Примеры
3.1.1 Граф авиарейсов
Задача. Представим себе страну, в которой есть пять городов A, B, C, D, E, между
которыми летают самолёты. Есть шесть рейсов: A–B, A–C, A–E, B–D, C–D, C–E
(каждый рейс в обе стороны). Можно ли долететь из города A в город D прямым
рейсом? с одной пересадкой? с двумя пересадками? Сколькими ?
A
B
C
D
E
Это совсем простая задача: чтобы её решить, достаточно нарисовать картинку.
Сразу видно, что прямого рейса нет, с одной пересадкой есть два A–B–D и
A–C–D, а с двумя пересадками есть единственный вариант A–E–C–D.
Ту же картинку можно использовать, чтобы ответить на более сложный вопрос
1) Положить на обе чаши весов по 4 монеты. В той чаше, которая будет легче по весу, среди нормальный монет будет фальшивая. В другой чаше все монеты будут нормальные и эта чаша перевесит чашу с фальшивкой.
2) Монеты из чаши, в которой были нормальные монеты, отложить. Они более не нужны. Монеты из чаши с фальшивой разложить по 2 штуки на каждую чашу.
Чаша, в которой будет фальшивая монета, будет легче чаши, которая содержит только настоящие монеты.
3) Две нормальные монеты отложить, они боле не нужны. Две монеты, среди которых одна фальшивая, разложить по одной на каждую чашу. Чаша с фальшивой монетой будет легче чаши с нормальной монетой.