- Граф называется ориентированным, если некоторым его вершинам присвоено направление. Вершины с направлениями называются дугами.
- Обход графа – это процесс систематического просмотра всех рёбер и вершин графа.
- Эйлеров путь – это способ обхода графа, при котором каждое ребро проходится ровно один раз.
- Эйлеров путь существует не во всех графах (пример – кёнигсбергские мосты). Алгоритмы обхода графов – одна из основ теории графов.
- В виде графов можно представлять многие ситуации из реальной жизни.
Примеры:
- У Маши было 5 конфет, у Кати – 4 конфеты, а у Тани – 7 конфет. Таня отдала Кате 3 конфеты, Маше отдала Тане 2 конфеты, а Катя отдала Маше одну конфету. Эту ситуацию можно представить в виде графа, изображённого на рисунке А.
- В корзине лежат яблоки и груши. Паша наугад берёт по одному фрукту три раза подряд. Все возможные исходы такого эксперимента отображены с помощью графа на рисунке Б. Красными вершинами обозначены яблоки, жёлтыми – груши, а бесцветная вершина – начальная ситуация, когда Паша ещё ничего не брал.
