ГДЗ по информатике, 10 класс, Поляков, номер 3.9: Структура информации
Информатика (в 2 частях); углубленное обучение — Поляков К.Ю., Еремин Е.А.
Светлана Крылова, методист по информатике Шпаргача обновлено 12 сентября 2026
Условие
Опишите метод подсчета количества ребер (для неориентированного графа) или дуг (для ориентированного графа) по весовой матрице.
Номер как в учебнике. Условие — полный пересказ редакции: те же пункты, числа и факты, не цитата из книги.
Пошаговое решение
Для решения задачи необходимо проанализировать структуру весовой матрицы смежности графа. Матрица смежности отражает связи между вершинами: элемент aij показывает наличие ребра или дуги из вершины i в вершину j. Количество таких ненулевых элементов (или единиц, если веса не учитываются) напрямую связано с количеством связей в графе.
Шаг 1. Анализ для неориентированного графа
В неориентированном графе каждое ребро соединяет две вершины симметрично. Если есть ребро между вершинами i и j, то в матрице смежности будут заполнены два элемента: aij=1 и aji=1. Это означает, что матрица является симметричной относительно главной диагонали.
Следовательно, если мы просто посчитаем все единицы в матрице, мы учтем каждое ребро дважды. Чтобы получить истинное количество ребер E, нужно разделить общее число единиц на два.
E=∑ni=1∑nj=1aij/2Примечание: Если в графе допускаются петли (ребра из вершины в саму себя), то элемент aii также считается как одно ребро, но при подсчете суммы он входит один раз. В стандартных задачах школьного курса обычно рассматриваются простые графы без петель, либо метод предполагает учет всех ненулевых элементов выше диагонали.
Шаг 2. Анализ для ориентированного графа (орграфа)
В ориентированном графе дуга имеет направление: из вершины i в вершину j. Наличие дуги фиксируется только одним элементом матрицы: aij=1. Элемент aji может быть равен нулю, если обратной дуги нет.
Матрица смежности орграфа не обязательно симметрична. Каждая единица в матрице соответствует ровно одной дуге. Поэтому количество дуг D равно общему числу единиц в матрице.
D=∑ni=1∑nj=1aijШаг 3. Итоговый алгоритм подсчета
Чтобы описать метод универсально, можно использовать следующий алгоритм действий:
- Получить весовую матрицу смежности графа размером n×n.
- Подсчитать количество ненулевых элементов (единиц) во всей матрице. Обозначим это число за S.
- Определить тип графа:
- Если граф неориентированный , то количество ребер равно S/2.
- Если граф ориентированный , то количество дуг равно S.
Проверка метода на примере треугольника (3 вершины, 3 ребра):
| V1 | V2 | V3 | |
|---|---|---|---|
| V1 | 0 | 1 | 1 |
| V2 | 1 | 0 | 1 |
| V3 | 1 | 1 | 0 |
Сумма единиц S=6. Для неориентированного графа: 6/2=3 ребра. Верно.
Неориентированный граф: количество ребер равно половине суммы всех единиц в матрице смежности.
Ориентированный граф: количество дуг равно сумме всех единиц в матрице смежности.
В условии упоминается 'весовая матрица', но в контексте подсчета количества ребер/дуг обычно подразумевается бинарная матрица смежности (где 1 - есть связь, 0 - нет). Если веса отличны от 1, то нужно считать количество ненулевых элементов. Решение дано для классического случая подсчета связей.
Как решение?
Двойная оценка: понятность и подробность. Можно выбрать одно или оба.
У вас другое условие?
Загрузите фото — учтём ваши числа и редакцию.
Частые вопросы
Это точный номер 3.9 из моего учебника?
Номер совпадает с учебником «Информатика (в 2 частях); углубленное обучение», Поляков К.Ю., Еремин Е.А.. Формулировка — пересказ редакции, не дословная цитата. Если в вашей редакции другие числа — загрузите фото.
Какой ответ в задании 3.9?
Краткий ответ: Неориентированный граф: количество ребер равно половине суммы всех единиц в матрице смежности. Ориентированный граф: количество дуг равно сумме всех единиц в матрице смежности.
Как пользоваться этим разбором?
Сначала прочитайте условие и чертёж, затем шаги решения по порядку и сверьте свой ход с кратким ответом внизу.
Какой учебник имеется в виду?
«Информатика (в 2 частях); углубленное обучение», Поляков К.Ю., Еремин Е.А.. Проверьте часть, год и автора на обложке. Тема в учебнике: § 3. Структура информации.
Можно ли списать ответ без решения?
Лучше сначала решить самостоятельно, а разбор использовать для проверки хода и поиска ошибки.