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