Определение
Неориентированный граф — это граф, рёбра которого не имеют направления и рисуются простыми линиями без стрелок. По каждому ребру можно пройти в обе стороны: если есть ребро между А и Б, то из А можно попасть в Б и из Б в А, как по дороге с двусторонним движением. Схемы дорог между пунктами, заданные таблицей расстояний, обычно устроены именно так.
Ключевые признаки
- Ребро без стрелки — ребро А–Б и ребро Б–А — одно и то же ребро: его рисуют одной линией и считают один раз
- Путь в обе стороны — любой путь можно пройти в обратном порядке, и его длина не изменится: маршрут К–Л–М такой же длины, как М–Л–К
- Симметричная таблица — каждое ребро записано в таблице дважды: число в строке А и столбце Б равно числу в строке Б и столбце А, поэтому таблица зеркальна относительно диагонали
- Степень вершины — у вершины считают одно число: сколько рёбер к ней подходит; сумма степеней всех вершин вдвое больше числа рёбер, ведь каждое ребро соединяет две вершины
Пример
Дороги между пунктами: К–Л 3 км, Л–М 4 км, М–Н 2 км, К–Н 10 км. Кратчайший путь из К в Н идёт через Л и М: 3 + 4 + 2 = 9 км, это меньше прямой дороги в 10 км. Обратный путь Н–М–Л–К тоже 9 км, ведь по каждой дороге можно ехать в обе стороны. В таблице расстояний четыре дороги займут 8 клеток: например, число 3 стоит и в клетке К–Л, и в клетке Л–К.
Тема целиком: Граф — теория, разобранные задания и тренажёр.
Не путай: Неориентированный граф и ориентированный граф
В ориентированном графе ребро — стрелка, и идти по нему можно только от начала стрелки к концу: ребро А→Б не даёт дороги из Б в А, поэтому таблица такого графа может быть несимметричной. В неориентированном графе одна линия служит сразу для обоих направлений, и любой путь можно пройти обратно.
Частые вопросы
Что такое неориентированный граф простыми словами (для 7–9 класса)?
Неориентированный граф — это граф, рёбра которого не имеют направления и рисуются простыми линиями без стрелок. По каждому ребру можно пройти в обе стороны: если есть ребро между А и Б, то из А можно попасть в Б и из Б в А, как по дороге с двусторонним движением. Схемы дорог между пунктами, заданные таблицей расстояний, обычно устроены именно так.
Как неориентированный граф выглядит на практике?
Дороги между пунктами: К–Л 3 км, Л–М 4 км, М–Н 2 км, К–Н 10 км. Кратчайший путь из К в Н идёт через Л и М: 3 + 4 + 2 = 9 км, это меньше прямой дороги в 10 км. Обратный путь Н–М–Л–К тоже 9 км, ведь по каждой дороге можно ехать в обе стороны. В таблице расстояний четыре дороги займут 8 клеток: например, число 3 стоит и в клетке К–Л, и в клетке Л–К.
В каких заданиях ОГЭ встречается «неориентированный граф»?
В заданиях на знание понятий информатики — потренируйся в тренажёре Совелия.