Информатика · Пробное ЕНТ

Графы: тест ЕНТ

Проверьте знания по теме «Графы» для подготовки к ЕНТ. Формулы, логические выражения и математические обозначения отображаются через MathML.

20 вопросов4 варианта ответаПроверка сразуОбъясненияБез регистрации

Вопрос 1 из 20Правильных ответов: 0

✓

Тест завершён

Ваш результат по теме «Графы»

0 / 20

Другие тесты по информатике

Подготовка к ЕНТ: Графы

Тематический тест помогает проверить не весь курс, а конкретный раздел «Графы». Такой формат удобен для повторения после урока, самостоятельной подготовки и поиска слабых мест.

Как работать с результатом

Не ограничивайтесь итоговым числом правильных ответов. Обратите внимание, какие понятия были перепутаны и почему выбранный вариант показался верным. После объяснения попробуйте своими словами сформулировать правило или алгоритм, логическое правило или вычислительную закономерность.

Повторное прохождение имеет смысл после короткого повторения темы. Цель — понимать связь между данными, алгоритмом, кодом и результатом выполнения, а не запоминать расположение ответов.

Вершины · рёбра · степень · матрица смежности · путь

Переводите рисунок или описание графа в список связей, а затем решайте задачу по этой модели

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

01 Определите тип графа Сначала установите, ориентированы ли рёбра и есть ли у них веса.

02 Выпишите связи Список рёбер снижает риск пропустить соседнюю вершину.

03 Считайте степень правильно В неориентированном графе учитываются все инцидентные рёбра.

04 Для пути складывайте веса Во взвешенном графе кратчайший путь определяется суммой весов, а не только числом рёбер.

Ключевые понятия

ВершинаОбъект графа, обозначаемый точкой или именем.

РеброСвязь между двумя вершинами.

Неориентированный графРебро A–B задаёт симметричную связь между A и B.

Ориентированный графДуга A→B имеет направление; входящие и исходящие связи различаются.

Степень вершиныВ неориентированном графе — число рёбер, инцидентных вершине.

Изолированная вершинаВершина степени 0.

A — B
|   |
C — D

Рёбра: A-B, A-C, B-D, C-D

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

Что важно для заданий ЕНТ

Матрица смежностиПоказывает наличие связей между парами вершин; у простого неориентированного графа она симметрична.

ПутьПоследовательность вершин, в которой соседние вершины соединены рёбрами.

Вес ребраЧисловая характеристика связи: расстояние, стоимость, время и т. п.

ДеревоСвязный неориентированный граф без циклов.

Обход в ширинуПоследовательно рассматривает вершины по уровням от начальной; в невзвешенном графе позволяет получить кратчайшие расстояния по числу рёбер.

Сумма степенейВ неориентированном графе сумма степеней всех вершин равна удвоенному числу рёбер.

Матрица смежности:
0 1 1
1 0 0
1 0 0

Степень A = 2

Для взвешенного графа маршрут с меньшим количеством рёбер не обязательно является кратчайшим: сравнивайте сумму весов.

Алгоритм

Как решать задания по теме «Графы»

Определите вершины и рёбра

Перепишите структуру графа в удобной форме.

Установите направление и веса

Это влияет на степень и допустимые маршруты.

Для степени рассмотрите одну вершину

Посчитайте только рёбра, которые ей инцидентны.

Для матрицы сверьте порядок вершин

Каждая единица или вес относится к конкретной паре.

Для обхода используйте очередь состояний

Фиксируйте порядок обнаружения вершин и не добавляйте уже обнаруженные повторно.

Для кратчайшего пути сравните кандидатов

Сложите веса всех рёбер каждого допустимого маршрута.

Частые ошибки

Что особенно важно не перепутать

Считают ребро дважды

В неориентированном списке A–B и B–A — одна и та же связь.

Путают степень и число соседей

В типичных школьных простых графах они совпадают, но нужно читать условие.

Игнорируют направление дуги

В ориентированном графе A→B не означает B→A.

Считают число рёбер вместо суммы весов

Это неверно для взвешенной задачи.

Нарушают порядок обхода

Если задан алфавитный порядок соседей, он влияет на последовательность BFS.

Не обновляют граф после удаления ребра

После изменения структуры нужно заново проверять допустимые пути и степени.