ГДЗ по информатике, 10 класс, Поляков, номер 3.10: Структура информации
Информатика (в 2 частях); углубленное обучение — Поляков К.Ю., Еремин Е.А.
Юлия Громова, преподаватель информатики Шпаргача обновлено 12 сентября 2026
Условие
Как вычислить степени всех вершин неориентированного и ориентированного графов по их весовым матрицам?
Номер как в учебнике. Условие — полный пересказ редакции: те же пункты, числа и факты, не цитата из книги.
Пошаговое решение
Для решения задачи необходимо рассмотреть два случая: неориентированный граф и ориентированный граф. В обоих случаях мы будем использовать весовую матрицу смежности A, где элемент aij равен 1, если существует ребро (или дуга) из вершины i в вершину j, и 0 в противном случае.
Шаг 1. Степени вершин неориентированного графа
В неориентированном графе степень вершины vi (deg(vi)) равна количеству рёбер, инцидентных этой вершине. Поскольку каждое ребро соединяет две вершины, оно учитывается дважды: один раз для каждой из концовых вершин.
В матрице смежности A неориентированного графа симметрична относительно главной диагонали (aij=aji). Чтобы найти степень вершины vi, нужно просуммировать все элементы i-й строки (или i-го столбца) матрицы A.
deg(vi)=∑nj=1aijПример: Если i-я строка матрицы содержит единицы в позициях j1,j2,…,jk, то степень вершины vi равна k.
Шаг 2. Степени вершин ориентированного графа
В ориентированном графе различают две степени вершины:
- Полустепень исхода (outdeg(vi)) — количество дуг, выходящих из вершины vi.
- Полустепень захода (indeg(vi)) — количество дуг, входящих в вершину vi.
Матрица смежности ориентированного графа не обязательно симметрична. Элемент aij=1 означает наличие дуги из i в j.
Чтобы найти полустепень исхода вершины vi, нужно просуммировать элементы i-й строки матрицы A:
outdeg(vi)=∑nj=1aijЧтобы найти полустепень захода вершины vi, нужно просуммировать элементы i-го столбца матрицы A:
indeg(vi)=∑nj=1ajiШаг 3. Проверка на примере
Рассмотрим матрицу смежности A размером 3×3:
| v1 | v2 | v3 | |
|---|---|---|---|
| v1 | 0 | 1 | 1 |
| v2 | 1 | 0 | 0 |
| v3 | 1 | 0 | 0 |
Случай неориентированного графа:
- deg(v1)=0+1+1=2
- deg(v2)=1+0+0=1
- deg(v3)=1+0+0=1
Случай ориентированного графа:
- Для v1: outdeg(v1)=0+1+1=2; indeg(v1)=0+1+1=2 (сумма 1-го столбца).
- Для v2: outdeg(v2)=1+0+0=1; indeg(v2)=1+0+0=1 (сумма 2-го столбца).
- Для v3: outdeg(v3)=1+0+0=1; indeg(v3)=1+0+0=1 (сумма 3-го столбца).
Неориентированный граф: степень вершины vi равна сумме элементов i-й строки (или i-го столбца) матрицы смежности.
Ориентированный граф: полустепень исхода outdeg(vi) равна сумме элементов i-й строки; полустепень захода indeg(vi) равна сумме элементов i-го столбца.
В решении четко разделены случаи для неориентированных и ориентированных графов. Для неориентированного графа используется свойство симметрии матрицы смежности, поэтому сумма по строке или столбцу дает одинаковый результат. Для ориентированного графа подчеркивается различие между выходными и входными дугами, что соответствует суммированию по строкам и столбцам соответственно. Приведен конкретный числовой пример для наглядности.
Как решение?
Двойная оценка: понятность и подробность. Можно выбрать одно или оба.
У вас другое условие?
Загрузите фото — учтём ваши числа и редакцию.
Частые вопросы
Это точный номер 3.10 из моего учебника?
Номер совпадает с учебником «Информатика (в 2 частях); углубленное обучение», Поляков К.Ю., Еремин Е.А.. Формулировка — пересказ редакции, не дословная цитата. Если в вашей редакции другие числа — загрузите фото.
Какой ответ в задании 3.10?
Краткий ответ: Неориентированный граф: степень вершины v_i равна сумме элементов i-й строки (или i-го столбца) матрицы смежности. Ориентированный граф: полустепень исхода outdeg(v_i) равна сумме элементов i-й строки; полустепень захода indeg(v_i) равна сумме элементов i-го столбца.
Как пользоваться этим разбором?
Сначала прочитайте условие и чертёж, затем шаги решения по порядку и сверьте свой ход с кратким ответом внизу.
Какой учебник имеется в виду?
«Информатика (в 2 частях); углубленное обучение», Поляков К.Ю., Еремин Е.А.. Проверьте часть, год и автора на обложке. Тема в учебнике: § 3. Структура информации.
Можно ли списать ответ без решения?
Лучше сначала решить самостоятельно, а разбор использовать для проверки хода и поиска ошибки.