В некоторых задачах возникает необходимость рассматривать мультиграфы, в которых одна и та же пара вершин может соединяться более чем одним ребром, и псевдографы, в которых наряду с кратными ребрами допускаются петли - ребра, соединяющие вершину саму с собой