Cтраница 1
Мультиграф отличается от обыкновенного тем, что между вершинами его может быть бесконечно много одинаковых ребер - кратные ребра. [1]
Мультиграф, изображенный на рис. 4.30, не содержит эйле - ров цикл, поскольку в нем есть вершины, имеющие нечетную степень; более того, все вершины имеют нечетную степень. [2]
Мультиграф называется эйлеровым, если существует замкнутый путь, проходящий через каждое ребро ровно один раз. [3]
Мультиграф G ( У, Е), где V - множество вер-глин, Е - множество ребер, называется эйлеровым, если он содержит замкнутый маршрут ( эйлеров маршрут), в котором каждая вершина появляется по крайней мере один раз и каждое ребро ровно один раз. [4]
Мультиграф G ( M U R, в котором выделено k вершин ( полюсов ], называется k - полюсной сетью. Сеть G, задаваемая неориентированным мультиграфом с k полюсами, в которой каждое ребро помечено буквой из алфавита X xi x 2, хп х Х2, жп, называется k - полюсной контактной схемой. [5]
Бесконтурным ориентированным мультиграфом называется мультиграф, не содержащий контуров. Доказать, что в бесконтурном ориентированном мультиграфе существует вершина с нулевой полустепенью исхода. [6]
Ребро мультиграфа, соответствующее выделенному элементу, переносится во внешнюю область гамильтонова или псевдогамильтонова цикла. [7]
Однако этот мультиграф не является универсальным. Графы, имеющие такую конфигурацию, называют разделимыми, так как удаление одной вершины или ребра ( дуги) разделяет его на две несвязные части. [8]
Граф ( мультиграф без петель) называется псевдорегулярным степени т, если степень каждой его вершины равна либо т, либо 1; ребро, инцидентное вершине степени 1, называется висячим. Достаточность доказывается путем построения требуемых графов. [9]
Под термином мультиграф в дальнейшем понимается конечный граф, имеющий более одного ребра между, по крайней мере-одной парой смежных вершин, а под термином граф, когда это не вызывает недоразумений - конечный неориентированный граф ( или мультиграф), а также конечный направленный графг у которых отсутствуют петли. Химическую структуру, соответствующую такому графу, называют молекулярным графом, или химическим графом. [10]
Теорема 4.1.2. Мультиграфы G и G изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга некоторыми перестановками строк и столбцов. [11]
Важным качеством мультиграфа на рис. 1 - 25, в является универсальность, которая при замене одного из элементов индуктивным или резистивным элементом позволяет перейти от цепи RC к RL и LC или к безреактивным схемам любого порядка ( п может начинаться с нуля) при сохранении общей структуры. Изменение степени п изменяет лишь число контуров с весом g - sC l i. Для п, равного двум и трем, на рис. 1 - 25, г и д приведены мультиграфы, обобщенные графы и соответствующие им схемы, образованные из мультиграфа на рис. 1 - 25, в. Заметим, что при п - 2 и г 4 существует всего один неразделимый мультиграф, составленный из элементов RC ( RL), определитель которого образует полином A ( s) второго порядка со структурой, совпадающей с предлагаемой структурой. Вышеизложенное дает нам основание выбрать граф, изображенный на рис. 1 - 25, в, в качестве исходного для синтеза пассивных и активных схем с одним зависимым источником. [12]
Для каждого мультиграфа М определим реберный граф L ( M) как граф с множеством вершин V ( L ( М)) X ( М), в котором х adj у тогда и только тогда, когда х и у - различные ребра, встречающиеся в одной или двух вершинах. [13]
Алгоритм представления мультиграфа G произведением двух мультиграфов GI и G2 подобен алгоритму разложения графов. [14]
Две дуги ориентированного мультиграфа, обе выходящие из одной вершины и и входящие в одну вершину v, называются параллельными. Две дуги, инцидентные с вершиной, для которой полустепень захода и полустепень исхода равны единице, называются последовательными. В отличие от параллельных дуг пару дуг, соединяющих две вершины во встречных направлениях ( одна направлена из и в v, другая - из у в и), называют звеном. [15]