Мультиграф

Cтраница 3

На рис. 2.3 приведены мультиграф и псевдограф, в основе которых лежит один и тот же граф - треугольник. Ясно, что граф в задаче о кенигсбергских мостах ( рис. 1.2) является на самом деле муль-тиграфом. [31]

На первой итерации совмещают мультиграф гп / и контур элементарного графа г а, принадлежащий графу га1 -, объединяя их вершины так, чтобы добиться совпадения наибольшего числа одноименных ребер и дуг и образования наименьшего числа дополнительных контуров, отсутствующих в других графах sia, учитывая, что часть таких контуров может быть разомкнута [ см. описание отображения ( 11 - 22) 1 с сохранением полинома Ап ( s) неизменным. Ребро и дуга одного типа ( g или sC), соединяющие смежные вершины, заменяются одной дугой, которой присваивается номер ребра мультиграфа. [32]

Порядок обхода вершин двоичного дерева при П - обходе, О-обходе и В-обходе. [33]

Система дорог - это размеченный мультиграф ( без петель), который отличается от графа тем, что в нем одна и та же пара ( различных) вершин может быть связана более чем одним ребром. При этом вершины соответствуют городам, а ребра - дорогам. Односторонним дорогам соответствуют дуги, а двусторонним дорогам - ребра. Каждая дорога имеет некоторую длину - положительное вещественное число. [34]

ХТК будем рассматривать как ориентированный мультиграф, дуги которого соответствуют межблочным переменным, а вершины - блокам ХТК. [35]

Двухполюсная сеть - это связный мультиграф, в котором отмечены две вершины и и и; эти точки называются первым полюсом и вторым полюсом. Сумма или параллельное соединение NMi N2 получается отождествлением 1 с г и У. [36]

Говорят, что задан ориентированный мультиграф G ( XF), если задано множество X и отображение F множества X в множество слов над X. Наибольшая из кратностей всех слов над X называется мультичислом m данного мультиграфа G. Очевидно, что все понятия и определения, введенные для графов, естественно обобщаются на мультиграфы. [37]

Рассмотрим теперь метод разложения мультиграфов по операции умножения. [38]

Если рассмотрено все множество мультиграфов Гп, а схема цепи с заданными свойствами не получена, то сначала увеличивают число ребер, а потом - вершин. [39]

При любом расщеплении вершин двудольного мультиграфа получается двудольный мультиграф. [40]

Остановимся теперь на понятии ориентированного мультиграфа, которое обобщает понятие ориентированного графа. [41]

Графы сети Петри являются мультиграфами, так как позиция может быть кратным входом или выходом перехода. В графе это показывается несколькими дугами между позицией и переходом. В то время как такой способ удовлетворителен для дуг с малой кратностью ( не более трех), он неудобен для дуг очень большой кратности. Таким образом, в качестве альтернативного представления структур с большой кратностью используется пучок дуг. Пучок - это специальная дуга, которая рисуется жирной линией и помечается кратностью. [42]

Доказать, что в мультиграфе всякий замкнутый маршрут нечетной длины / 3 содержит простой цикл. Справедливо ли аналогичное утверждение для маршрутов четной длины. [43]

Преобразованию nh поставим в соответствие мультиграф с петлями Г ( А, Д) обработки данных, обеспечивающий получение вектора выходных переменных Yh. Вершинами А аг, г 1, Я, мультиграфа Г являются процедуры обработки данных, а ребрами - переменные, являющиеся общими для соответствующих процедур. Петля в графе Г соответствует независимой обработке соответствующей переменной. [44]

Теорема 4.4. Для того чтобы мультиграф G ( Z, U) разлагался в произведение двух мультиграфов, необходимо и достаточно существование подстановки t e Т множества Z, которая переводит матрицу смежности R мультиграфа G в мультиправильную клеточную матрицу. [45]

Страницы: 1 2 3 4