Обычно несколько ребер, соединяющих одну и ту же пару вершин, различаются метками - именами соответствующих бинарных отношений. В лекциях 4-6 мультиграфы будут использоваться для представления диаграмм конечных автоматов.
Во многих случаях естественно не различать графы, отличающиеся лишь именами (порядком) вершин.
Определение 1.8. Изоморфизм графов. Два графа
Для изоморфизма размеченных графов требуется также совпадение меток соответствующих вершин :
Многие приложения графов связаны с изучением путей между их вершинами.
Определение 1.9.
Путь в (мульти)графе - это последовательность ребер вида
Путь назывется простым, если все ребра и все вершины на нем, кроме, быть может, первой и последней, различны.
Циклом в графе называется путь, в котором начальная вершина совпадает с конечной и который содержит хотя бы одно ребро. Цикл
Если в графе нет циклов, то он называется ациклическим.
Следующее утверждение непосредственно следует из определений.
Лемма 1.1.Если в графе