"Информатика (в 2 частях)", Павлов Д.И., Полежаева О.А., Коробкова Л.Н. и др./ Под ред. Горячева А.В.
Граф помогает представить пункты и дороги между ними в виде понятной схемы. Пункты изображают вершинами, дороги — рёбрами, а длины дорог записывают рядом с рёбрами. Последовательность соединённых вершин образует путь, его длина равна сумме длин всех пройденных дорог. Сравнивая длины разных путей, можно найти кратчайший маршрут.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Граф — модель, состоящая из вершин и соединяющих их рёбер. С его помощью можно изобразить пункты и дороги между ними. Такая схема заменяет подробную карту и оставляет только сведения, нужные для поиска маршрута.
Вершина графа — объект или пункт, который изображают точкой. В задаче о маршрутах вершинами могут быть города, станции или перекрёстки. По вершинам определяют, откуда начинается путь и куда он заканчивается.
Ребро графа — связь между двумя вершинами. В дорожной задаче оно соответствует дороге, по которой можно перейти или проехать из одного пункта в другой. Набор рёбер показывает, какие пункты непосредственно связаны.
Длина пути — сумма длин рёбер, по которым проходят от начальной вершины к конечной. Она показывает, сколько всего составляет выбранный маршрут. Поэтому для её вычисления нужно учитывать каждую дорогу, входящую в путь.
Чтобы перевести задачу о передвижении в граф, сначала выделяют все пункты и изображают их вершинами. Затем каждую дорогу заменяют ребром, соединяющим соответствующие точки. Так схема сохраняет главное: из какого пункта в какой можно попасть напрямую.
На рёбрах указывают длины дорог, потому что одних сведений о соединении недостаточно для сравнения маршрутов. Две дороги могут вести между одинаковыми пунктами, но иметь разную протяжённость. Граф, у рёбер которого есть числовые значения, называют взвешенным графом, а число возле ребра — его весом.
Путь в графе — это последовательность смежных вершин от начала до конца. Смежными называют вершины, соединённые одним ребром, поэтому переходы в записи пути должны идти по существующим дорогам. Например, A–B–D означает движение из A в B, а затем из B в D.
Длину пути находят сложением весов всех рёбер, которые пришлось пройти. Сначала удобно выписать маршрут по порядку, затем отметить каждую использованную дорогу и только после этого выполнить сложение. Такой порядок помогает не пропустить ребро и не учесть его повторно.
Если между двумя вершинами есть несколько путей, для каждого вычисляют отдельную длину. Затем результаты сравнивают, не ориентируясь только на количество дорог. Путь с наименьшей суммой весов называют кратчайшим путём.
| Понятие | Что обозначает | Как используется при поиске пути |
|---|---|---|
| Вершина | Пункт или объект | Задаёт начало, конец или промежуточный пункт маршрута |
| Ребро | Связь между двумя вершинами | Показывает, по какой дороге можно перейти между пунктами |
| Вес ребра | Числовое значение характеристики связи | Обычно показывает длину соответствующей дороги |
| Путь | Последовательность соединённых вершин | Описывает конкретный маршрут от начала до конца |
| Длина пути | Сумма весов его рёбер | Позволяет измерить и сравнить маршруты |
| Кратчайший путь | Путь с наименьшей длиной | Выбирается как лучший среди найденных вариантов |
Пользуйтесь таблицей как памяткой: сначала определите пункты и связи, затем найдите веса дорог. После этого запишите путь и сложите веса его рёбер. Для выбора маршрута сравните полученные длины, а не только количество переходов.
Условие. На схеме три дороги соединяют пункты A и B, а один из возможных маршрутов проходит через C. Длины дорог A–C и C–B указаны на схеме: 7 км и 5 км. Найдите длину маршрута A–C–B.
Ответ: длина маршрута A–C–B равна 12 км. Дорога между A и B, которая не входит в записанный путь, в вычислении не участвует. Мы считаем только рёбра выбранного маршрута.
Условие. Между пунктами A и D можно проехать по маршрутам A–B–D и A–C–D. Пусть длины дорог A–B, B–D, A–C и C–D равны соответственно 4 км, 9 км, 6 км и 5 км. Определите, какой маршрут короче.
Ответ: короче маршрут A–C–D, его длина равна 11 км. Хотя оба варианта содержат по две дороги, их общие длины различаются. Поэтому одного подсчёта рёбер недостаточно.
Условие. В графе нужно добраться из A в E. Возможные маршруты имеют длины: A–B–E — 14 км, A–C–E — 10 км, A–B–D–E — 12 км. Найдите кратчайший путь и его длину.
Ответ: кратчайший путь — A–C–E, его длина составляет 10 км. Он выбран потому, что его суммарный вес меньше длин двух остальных маршрутов. Число рёбер здесь также не является главным критерием.
Ошибка — считать длиной пути число рёбер. Так поступают, когда забывают, что дороги имеют разные длины; проверьте себя, сложив все записанные веса.
Ошибка — пропустить ребро или учесть его дважды. Это происходит при сложном маршруте; выпишите вершины по порядку и отметьте каждую пару соседних вершин ровно один раз.
Ошибка — путать вершину и ребро. Пункт изображается точкой и является вершиной, а дорога между пунктами является ребром; полезно назвать отдельно все точки и соединяющие их линии.
Ошибка — выбрать путь с меньшим числом дорог без сравнения длины. Короткая запись маршрута может содержать длинное ребро, поэтому сначала вычислите сумму для каждого варианта.
Для работы с маршрутами нужно уметь читать схемы и складывать натуральные числа с единицами длины. Следите, чтобы все слагаемые были выражены в одинаковых единицах, например только в километрах.
Графы применяются при изучении сетей, маршрутов и задач на поиск оптимального решения. Та же идея помогает описывать компьютерные соединения, транспортные схемы и выбирать наиболее выгодный вариант.
Чем вершина графа отличается от ребра?
Вершина обозначает объект или пункт, например город или станцию. Ребро показывает связь между двумя вершинами, например дорогу между городами.
Что означает число, записанное возле ребра?
Это вес ребра — числовое значение характеристики связи. В задаче о дорогах он обычно обозначает длину дороги.
Как посчитать длину пути, если он проходит через несколько рёбер?
Нужно выписать все рёбра выбранного пути и сложить их веса. Полученная сумма и будет длиной маршрута.
Может ли маршрут с меньшим числом дорог быть длиннее другого?
Да, может. Одна длинная дорога иногда оказывается длиннее нескольких коротких, поэтому сравнивать нужно общую длину, а не только число рёбер.
Как найти кратчайший путь, если возможных маршрутов несколько?
Нужно перечислить подходящие пути, вычислить длину каждого сложением весов рёбер и сравнить результаты. Кратчайшим будет путь с наименьшей суммой.
9. Долог ли путь
