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