Пусть G = G(V,E) – неориентированный граф с вершинами v0, v1, v2, v3, …, vk множества V и ребрами e1, e2, e3, …, ek множества Е. Определение. Путем (маршрутом) длины k из v0 в vk (или между v0 и vk) называется последовательность v0e1v1e2v2e3v3…v(k-1)ekvk такая, что eі = {ѵі-1, vі}. Таким образом, путь длины k имеет k ребер. Определение. Если нет рёбер, предшествующих e1, то вершина v0 называется начальной, если нет рёбер, следующих после ek, то вершина vk называется конечной, вершины пути, не являющиеся начальной или конечной, называются внутренними...

Задачи на графы встречаются в ЕГЭ по информатике в разных форматах: в заданиях на маршруты, таблицы, схемы и анализ связей. Многие ученики их боятся, потому что слово «граф» звучит страшно и ассоциируется с чем-то из университетской математики. На деле большинство задач ЕГЭ на графы решаются одним методом — и когда он освоен, задача становится почти механической. Граф — это набор вершин (точек) и рёбер (связей между точками). Всё. Никакой магии. Когда вы рисуете схему городов с дорогами между ними, или рисуете связи между людьми в социальной сети — вы рисуете граф...