Cтраница 1
Ребро мультиграфа, соответствующее выделенному элементу, переносится во внешнюю область гамильтонова или псевдогамильтонова цикла. [1]
Отсоединяют от выходной вершины ИНУН ребра мультиграфа, не совпавшие с дугами орграфа и образовавшие дополнительные контуры, и подсоединяют их к вновь введенной вершине. [2]
Циклический маршрут, проходящий через все ребра мультиграфа, будем называть обходом мультиграфа. Обход минимальной длины называется кратчайшим. Задача состоит в отыскании кратчайшего обхода. [3]
Вершина г, от которой отсоединяются ребра мультиграфа, будет общей для входного и выходного сигналов. [4]
Раскраска ребер нагруженного мультиграфа G, совпадающая с правильной раскраской ребер ненагруженного мультиграфа Н9 описанного в лемме 2, является правильной. [5]
Эйлером сформулирован и доказан критерий того, что связный неориентированный мультиграф имеет цикл, содержащий все ребра данного мультиграфа. Цикл, содержащий все ребра мультиграфа, на -, зывается эйлеровым, и мулътиграф, в котором имеется эйлеров цикл, также называется эйлеровым. [6]
Неориентированный мультиграф G, представляющий задачу, показан на рис. 4.30. Вершины х, х соответствуют берегам реки, Х2, хз - островам, ребра мультиграфа - мостам. [7]
Эйлером сформулирован и доказан критерий того, что связный неориентированный мультиграф имеет цикл, содержащий все ребра данного мультиграфа. Цикл, содержащий все ребра мультиграфа, на -, зывается эйлеровым, и мулътиграф, в котором имеется эйлеров цикл, также называется эйлеровым. [8]
Такая геометрическая фигура, являющаяся изображением планарного мультиграфа, называется плоским мулътиграфом. Внутренней гранью плоского мультиграфа называется конечная область плоскости, ограниченная простым циклом и не содержащая внутри себя никаких вершин и ребер мультиграфа, принадлежащих другим простым циклам. Простой цикл, ограничивающий грань, называется ее границей. Часть плоскости, состоящая из точек, не принадлежащих мультиграфу и никакой из его внутренних граней, называется внешней гранью. [9]
На первой итерации совмещают мультиграф гп / и контур элементарного графа г а, принадлежащий графу га1 -, объединяя их вершины так, чтобы добиться совпадения наибольшего числа одноименных ребер и дуг и образования наименьшего числа дополнительных контуров, отсутствующих в других графах sia, учитывая, что часть таких контуров может быть разомкнута [ см. описание отображения ( 11 - 22) 1 с сохранением полинома Ап ( s) неизменным. Ребро и дуга одного типа ( g или sC), соединяющие смежные вершины, заменяются одной дугой, которой присваивается номер ребра мультиграфа. [10]