"Информатика", Горячев А.В., Суворова Н.И.
Объекты окружающего мира связаны друг с другом, и эти связи можно представить с помощью графа. Вершины графа обозначают объекты, а рёбра или стрелки — отношения между ними. Такая модель помогает увидеть, кто или что связано напрямую, а где нужен путь через другие вершины. Чтобы граф отвечал на вопрос задачи, в него включают только нужные объекты и связи, а не все подробности ситуации.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Объект — это предмет, явление или понятие, которое рассматривают как целое. Объектом может быть реальная вещь, например книга или город, а может быть абстрактное понятие, например число или правило. Мы выделяем объект, чтобы обсуждать его отдельно от остальных деталей ситуации. В задаче важно учитывать только те объекты, которые помогают найти ответ.
Свойство объекта — признак, по которому объект описывают или отличают от других. У книги такими свойствами могут быть название, автор и цвет обложки, а у города — название и число жителей. Значения свойств помогают уточнить, о каком объекте идёт речь. Их выбирают в зависимости от того, что требуется узнать.
Отношение между объектами — связь, которая показывает, как объекты связаны друг с другом. Например, отношение «учится в одной школе» связывает людей, а отношение «соединён дорогой» — населённые пункты. Само по себе перечисление объектов не показывает, как они взаимодействуют. Поэтому при описании ситуации отдельно отмечают важные отношения.
Граф — модель объектов и связей между ними: объекты изображают вершинами, а связи — рёбрами. Вершины обычно обозначают точками или кружками, а ребро проводят между теми вершинами, объекты которых связаны. Такая запись помогает увидеть структуру ситуации без лишних подробностей. Если связь направлена, вместо обычного ребра используют стрелку.
Чтобы описать сложную ситуацию, сначала выделяют важные объекты и связи между ними, а не все подробности реального мира. Причина в том, что задача обычно задаёт конкретный вопрос, а лишние сведения отвлекают и затрудняют поиск ответа. Например, для схемы дорог важны населённые пункты и то, какие дороги их соединяют, но не цвет домов. Если включать каждую мелочь, модель станет перегруженной и перестанет помогать.
В графе каждому выбранному объекту соответствует вершина, а наличие связи между двумя объектами обозначается ребром. Это позволяет заменить длинное описание на простую схему, где отношения заметны сразу. Ребро проводят только тогда, когда нужная связь действительно есть по условию задачи. Так можно быстро увидеть, какие объекты соседствуют или связаны непосредственно.
Иногда связь неравноправна: она задана от одного объекта к другому, но не обязательно обратно. Тогда её показывают стрелкой, а такую связь называют дугой. Например, если одна страница сайта содержит ссылку на другую, переход по ссылке ведёт в указанную сторону. Направление важно учитывать, потому что наличие дуги из A в B само по себе не означает наличие дуги из B в A.
Граф помогает увидеть не только прямые связи, но и возможность добраться от одной вершины до другой через промежуточные. Последовательность вершин, соединённых рёбрами или дугами, называется путём. Это удобно для поиска маршрута между городами или перехода между страницами сайта. В ориентированном графе каждая часть пути должна проходить по направлению стрелки.
Модель строят под задачу, поэтому в неё включают только необходимые объекты и отношения. Если выясняют, можно ли попасть из одного пункта в другой, достаточно обозначить пункты и дороги между ними. Если вопрос касается переходов по сайту, нужны страницы и ссылки с их направлениями. Один и тот же набор объектов можно представить разными графами, если рассматриваются разные отношения.
| Элемент | Как изображается | Что обозначает | Пример |
|---|---|---|---|
| Вершина | Точкой или кружком | Объект модели | Населённый пункт на карте маршрутов |
| Ребро | Линией между вершинами | Связь без указанного направления | Дорога между двумя пунктами |
| Дуга | Стрелкой между вершинами | Направленную связь | Ссылка с одной страницы сайта на другую |
| Путь | Цепочкой соединённых вершин | Способ перейти от одной вершины к другой | Маршрут через несколько городов |
Пользуясь таблицей, сначала определите, что именно обозначает каждый знак на схеме: объект, обычную связь или направленную связь. Затем проследите цепочку рёбер или дуг, если нужно проверить путь. Не считайте стрелку двусторонней связью, если обратное направление отдельно не показано.
Условие. Аня дружит с Борей, Боря — с Викой. Нужно изобразить граф и определить, связаны ли Аня и Вика напрямую. Считаем, что дружба в этой задаче изображается обычным ребром, поскольку направление отношений не задано.
Ответ. Аня и Вика не связаны напрямую. Между ними есть путь Аня — Боря — Вика, то есть связь через промежуточную вершину. Нельзя заменять этот путь дополнительным ребром: оно означало бы отдельную прямую связь.
Условие. Требуется составить граф маршрутов между четырьмя населёнными пунктами, если дороги соединяют только указанные в условии пары. Конкретные пары нужно взять из условия задачи: без них нельзя решить, какие рёбра присутствуют. Нужно также проверить, можно ли соединить выбранные пункты путём.
Ответ. Граф составлен из четырёх вершин и рёбер, соответствующих только перечисленным дорогам. Наличие пути между двумя пунктами устанавливают по схеме, прослеживая соединённые вершины. Без списка пар дорог нельзя назвать конкретный маршрут или утверждать, что все пункты достижимы.
Условие. По схеме переходов нужно определить, можно ли перейти с первой страницы на последнюю и каким маршрутом. Ссылки могут вести только в одном направлении, поэтому граф должен быть ориентированным. Для ответа нужно учитывать каждую стрелку на схеме.
Ответ. Возможность перехода и маршрут определяются по направленным дугам схемы. Нельзя пройти по стрелке в обратную сторону, если обратная дуга отдельно не нарисована. Без самой схемы конкретную последовательность страниц указать невозможно.
Ошибка — считать, что вершины обозначают только реальные предметы. Так думают, потому что слово «объект» часто связывают с вещью, которую можно увидеть и потрогать. Но вершиной может быть понятие или событие, если оно участвует в задаче. Проверьте себя: помогает ли выбранная вершина ответить на вопрос, а не является ли она материальной.
Ошибка — добавлять ребро между объектами, которые не связаны в условии. Иногда ученик дорисовывает связь, потому что она кажется вероятной или привычной. Но граф должен показывать заданные отношения, а не предположения. Перед проведением каждого ребра найдите подтверждение этой связи в условии.
Ошибка — игнорировать стрелки в ориентированном графе. Тогда дуги ошибочно принимают за обычные двусторонние рёбра и считают доступными невозможные переходы. Проверяйте направление каждой стрелки на каждом шаге пути. Если движение идёт против стрелки, такой переход учитывать нельзя.
Ошибка — принимать путь через промежуточные вершины за прямую связь. Её допускают, потому что по цепочке действительно можно добраться от начальной вершины до конечной. Однако прямую связь показывает только отдельное ребро или дуга между ними. Чтобы проверить себя, посмотрите, соединены ли именно эти две вершины одним элементом графа.
Для работы с графами полезно уметь выделять объекты и их признаки в описании окружающего мира. Это помогает решить, какие вершины нужны и какие сведения можно не переносить в модель. Умение отделять главное от подробностей делает схему понятной и подходящей для задачи. Если неверно выбрать объекты или отношения, граф не даст нужного ответа.
Графы пригодятся при изучении алгоритмов, маршрутов и сетей. В задаче о маршруте они помогают искать путь, а в сети показывают, какие элементы соединены и в каком направлении возможен переход. Алгоритм может последовательно проверять вершины и рёбра, чтобы найти нужный маршрут. Поэтому граф служит способом представить связи, с которыми работают разные информатические задачи.
Чем граф отличается от рисунка?
Обычный рисунок может передавать внешний вид предметов, их размер и множество деталей. Граф — это модель: его вершины и рёбра показывают объекты и только выбранные связи между ними. Поэтому вершины можно рисовать кружками, точками или другими условными знаками.
Может ли вершина обозначать не предмет, а понятие?
Да. Вершиной может быть любое важное для задачи понятие, событие или явление, а не только материальная вещь. Например, вершинами можно обозначить города, страницы сайта или школьные предметы.
Когда связь изображают стрелкой?
Стрелку используют, когда связь имеет направление и переход или указание возможно в одну сторону. Например, на схеме сайта стрелка может показывать, с какой страницы можно перейти на другую. В обратную сторону переход не считается возможным, если отдельной стрелки нет.
Что такое путь в графе?
Путь — это последовательность вершин, в которой соседние вершины соединены рёбрами или дугами. Он показывает, как добраться от одной вершины до другой через связи. В ориентированном графе при этом нужно соблюдать направления стрелок.
Можно ли по графу определить, связаны ли две вершины?
Да. Если между вершинами есть ребро, они связаны напрямую. Если ребра нет, нужно проверить, существует ли путь через промежуточные вершины; такой путь означает связь не напрямую, а через цепочку.
§ 12. Объекты и графы
