Определение
Граф — это набор вершин и рёбер, которые соединяют некоторые пары вершин. Вершины изображают точками или кружками, рёбра — линиями между ними. Граф показывает, что с чем связано: пункты и дороги между ними, станции и перегоны, компьютеры и линии связи.
Ключевые признаки
- Важны только связи — расположение вершин на рисунке и длина нарисованных линий значения не имеют; один и тот же граф можно нарисовать по-разному
- Вес ребра — у ребра может стоять число: длина дороги, время или стоимость проезда; такой граф называют взвешенным
- Путь — цепочка вершин, в которой каждые две соседние соединены ребром; если у рёбер есть стрелки (ориентированный граф, дороги односторонние), идти можно только по стрелке. Во взвешенном графе длина пути равна сумме весов его рёбер, а в графе без весов — числу рёбер
- Запись таблицей — граф можно задать таблицей: на пересечении строки и столбца стоит длина дороги между двумя пунктами, а пустая клетка значит, что прямой дороги между ними нет
Пример
Пункты A, B, C, D соединены дорогами: A–B 2 км, B–D 3 км, A–C 1 км, C–D 5 км. Это граф с четырьмя вершинами и четырьмя рёбрами. Из A в D ведут два пути: A–B–D длиной 2 + 3 = 5 км и A–C–D длиной 1 + 5 = 6 км. Кратчайший — 5 км, хотя он начинается с более длинной дороги: A–B длиннее, чем A–C.
Тема целиком: Граф — теория, разобранные задания и тренажёр.
Не путай: Граф и матрица смежности
Граф — сами вершины и связи между ними, а матрица смежности — способ записать граф таблицей. Клетка таблицы говорит только о прямой дороге между двумя пунктами: если в таблице расстояний клетка A–D пуста, прямой дороги нет, но путь из A в D через другие пункты может быть — его длину находят, складывая длины рёбер.
Частые вопросы
Что такое граф простыми словами (для 7–9 класса)?
Граф — это набор вершин и рёбер, которые соединяют некоторые пары вершин. Вершины изображают точками или кружками, рёбра — линиями между ними. Граф показывает, что с чем связано: пункты и дороги между ними, станции и перегоны, компьютеры и линии связи.
Как граф выглядит на практике?
Пункты A, B, C, D соединены дорогами: A–B 2 км, B–D 3 км, A–C 1 км, C–D 5 км. Это граф с четырьмя вершинами и четырьмя рёбрами. Из A в D ведут два пути: A–B–D длиной 2 + 3 = 5 км и A–C–D длиной 1 + 5 = 6 км. Кратчайший — 5 км, хотя он начинается с более длинной дороги: A–B длиннее, чем A–C.
В каких заданиях ОГЭ встречается «граф»?
В заданиях на знание понятий информатики — потренируйся в тренажёре Совелия.