§ 14. Графы и высказывания

Определения и обозначения

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

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

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

Высказывание — повествовательное предложение, которому можно приписать истинность или ложность. «Между городами есть дорога» — высказывание, потому что его можно проверить. Вопрос «Есть ли дорога?» и команда «Нарисуй дорогу!» высказываниями не являются: они не утверждают факт.

Как это устроено

Чтобы построить граф для ситуации, сначала реши, какие объекты важно учитывать: именно они станут вершинами. Например, если исследуются дороги между городами, вершина соответствует каждому городу, а не каждой дороге. Затем определи, какие связи нужно показать, и проведи ребро между каждой парой объектов, связанных по выбранному правилу. Такой порядок помогает не перепутать сами объекты с отношениями между ними.

Читать граф нужно, двигаясь от обозначений к линиям: подписи сообщают, какие объекты представлены, а рёбра показывают связи. Чтобы проверить связь двух объектов, найди их вершины и посмотри, соединены ли они линией. Если линия есть, связь отражена в графе; если её нет, граф такую связь не показывает. После этого граф можно пересказать словами, например: «Город А соединён дорогой с городом Б».

По графу можно сформулировать высказывание о вершинах или рёбрах. Сначала назови объекты, о которых идёт речь, а затем точно укажи, что утверждается об их связи: например, «Аня знакома с Борисом» или «между городами В и Г нет дороги». Точная формулировка нужна, чтобы было понятно, какие именно вершины и какое ребро следует проверить. Если в высказывании говорится о конкретной паре, не подменяй её другой парой.

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

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

Элементы графа и высказывания о нём

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

Разбор задач

Города и дороги

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

1. Найди на схеме все точки, обозначающие города. Каждая такая точка — вершина, поэтому вершинами будут А, Б, В и остальные подписанные города. Подписи позволяют не перепутать объекты при проверке.

2. Рассмотри линии, соединяющие точки. Каждая линия между двумя городами является ребром и показывает дорогу между ними. Линии, которые не соединяют городские точки, в этой модели не учитываются.

3. Найди вершины А и В и проверь, соединены ли они линией. Если линия непосредственно соединяет эти две вершины, дорога между А и В показана графом. Если такой линии нет, граф не показывает прямую дорогу между ними.

Ответ. Вершины — точки, подписанные названиями городов, а рёбра — линии-дороги между ними. Наличие дороги между А и В определяется по линии, соединяющей именно эти две вершины. Само по себе близкое расположение точек ответа не даёт.

Знакомства учеников

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

1. Найди вершины Ани и Бориса. Проверь, соединены ли они ребром: если да, первое высказывание истинно, если нет — ложно. Другие рёбра графа на этот вывод не влияют.

2. Найди вершину Веры и определи, с кем именно нужно проверить её связи. Сравни её с каждой вершиной остальных учеников, поскольку слово «со всеми» требует проверки каждой пары. Пропущенное ребро хотя бы к одному ученику означает, что утверждение не подтверждается.

3. Запиши результат отдельно для каждого предложения. Первое проверяется по одной паре вершин, а второе — по всем парам, в которых участвует Вера. Такой разбор не позволяет принять наличие нескольких знакомств за доказательство знакомства со всеми.

Ответ. «Аня знакома с Борисом» истинно, если между их вершинами есть ребро, и ложно, если его нет. «Вера знакома со всеми» истинно, только если её вершина соединена ребром с вершиной каждого другого ученика. Для конкретного графа результат устанавливают, проверив изображённые линии.

Построение графа и проверка утверждений

Условие. Пусть в описании сказано: Лена общается с Мишей и Олей, а Миша общается с Олей. Построй граф, в котором ученики представлены вершинами, а общение — рёбрами. Затем составь два высказывания о графе и проверь их.

1. Нарисуй три вершины и подпиши их «Лена», «Миша» и «Оля». Это все объекты, названные в описании, поэтому добавлять вершины для связей не нужно. Выбранные подписи помогут прочитать готовую схему.

2. Проведи ребро между Леной и Мишей, между Леной и Олей, а также между Мишей и Олей. Каждая линия появляется потому, что соответствующая пара названа в описании как общающаяся. Другие рёбра добавлять нельзя: описание их не задаёт.

3. Сформулируй, например, высказывания «Лена общается с Олей» и «Миша не общается с Олей». Первое проверь по наличию ребра между Леной и Олей, второе — по наличию ребра между Мишей и Олей. Сравнивая утверждения с линиями, получишь значения их истинности.

Ответ. В графе три вершины и три ребра, соответствующие всем трём указанным парам. Высказывание «Лена общается с Олей» истинно, потому что такое ребро проведено. Высказывание «Миша не общается с Олей» ложно, поскольку между их вершинами есть ребро.

Типичные ошибки

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

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

Ошибка — называть вопрос или приказ высказыванием. Вопрос может показаться утверждением о ситуации, но он лишь просит сообщить информацию; команда требует действия. Спроси себя, можно ли решить, истинно предложение или ложно: если нет, перед тобой не высказывание.

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

Связь с другими темами

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

Что запомнить

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