Вообще, тут уже явно начинается очередная терминологическая война. gogoshik, Вы не могли бы сформулировать определение графа из той книги, которой Вы пользуетесь?
Цитата:
Графом без петель и кратных ребер называется конечное множество

вместе с набором

двухэлементных подмножеств (т.е. неупорядоченных пар) множества

. Элементы данного множества

называются вершинами. Элементы набора

называются ребрами. Вершина

является концом ребра

если

.
Далее автор отмечает:
Цитата:
В большей части данного текста можно пользоваться понятием графа без петель и кратных ребер. Однако все написанное справедливо для следующего обобщения, которое кое-где даже необходимо.
Графом (с петлями и кратными ребрами) (или
мультиграфом) называется квадратная таблица

размера

из целых неотрицательных чисел, симметричная относительно главной диагонали. Элемент

таблицы называется
ребром (или
петлей)
кратности 
, если соответствует паре различных (или совпадающих) вершин.
Думаю, что мне в задаче как раз и необходимо использовать понятие мультиграфа. Задача (в моей интерпретации) предполагает, что её решение будет эквивалентно решению задачи, поставленной автором в её "чистом" виде.