Смешанный граф

Cтраница 2

В случае квазимаршрутов по гиперсети S можно построить смешанный граф G ( теорема 9) и тогда любым непересекающимся по ребрам ( s, t) - цепям в G взаимно однозначно соответствуют внешне независимые ( s, - маршруты в гиперсети S. [16]

Подразбиение вершины на инцидентную и слабо инцидентную. [17]

Гиперсети S ( X, V, R) сопоставим смешанный граф G - ( X U У, Е), полученный из данной гиперсети по следующему правилу. Легко показать, что любому квазимаршруту в гиперсети S ( X, V, R) взаимно однозначно соответствует ориентированный маршрут в смешанном графе G ( X U У, Е) между вершинами из множества X. Но в смешанном графе задача поиска - независимых по ребрам и дугам маршрутов между парами вершин полиномиально вычислима. [18]

Полный орграф пятого порядка.| Полные орграфы третьего порядка. [19]

Перечислительная формула для ср ( х, у) легко получается путем модификации формулы для смешанных графов. Число 1 в каждом из двух перечисляющих рядов для фигур - ( 1 2х г /) 1 / 2 и 1 У1 2 - отражает возможность отсутствия ребра, соединяющего пару вершин. [20]

Полный орграф пятого порядка.| Полные орграфы третьего порядка. [21]

Перечислительная формула для ср ( х, у) легко получается путем модификации формулы для смешанных графов. Число 1; в каждом из двух перечисляющих рядов для фигур - ( 1 2х y) l / z и 1 у1 / 2 - Отражает возможность отсутствия ребра, соединяющего пару вершин. [22]

Шаги 13 и 14 составляют сущность отображения ( 11 - 24) и завершают синтез смешанного графа г к, определитель которого удовлетворяет ТЭТ, реализуемым на уровне структуры. [23]

Наш подход можно также приспособить к перечислению направленных графов ( см. Харари [6]), но этот результат будет представлен как частный случай перечисления смешанных графов, которое рассматривается в следующем параграфе. [24]

Так как каждая такая функция / представляет орграф, скажем, с q ориентированными ребрами и г симметричными парами дуг, то / можно также трактовать как смешанный граф с q ориентированными и г неориентированными ребрами. Очевидно, что любые две функции из множества Fz 21 принадлежат одной и той же орбите степенной группы тогда и только тогда, когда соответствующие им смешанные графы изоморфны. [25]

Так как каждая такая функция / представляет орграф, скажем, с q ориентированными ребрами и г симметричными парами дуг, то / можно также трактовать как смешанный граф с q ориентированными и г неориентированными ребрами. Очевидно, что любые две функции из множества Yxl2 принадлежат одной и той же орбите степенной группы тогда и только тогда, когда соответствующие им смешанные графы изоморфны. [26]

Сначала совмещаем г с г1а ( рис. 11 - 2, г), а затем размыкаем дополнительно образовавшийся контур Ku8i ( рис. 11 - 2, 3), отсоединив ребро gj от вершины в, вес которой равен единице. Определитель смешанного графа равен A ( s) gi - f - g2 Ь Sa u - Как видим, он не отличается от желаемого, что обусловлено сохранением весов вершин и и в при размыкании лишнего контура. [27]

Мы довольно часто применяли для записи цикловых индексов два множества переменных. Кроме того, при перечислении смешанных графов в § 5.4 переменные sft и tk появились в цикловом индексе редуцированной упорядоченной парной группы ( см. соотношение 5.4.5)); переменные sk соответствовали парам взаимно обратных циклов, а переменные tk - самообратным циклам. [28]

Мы довольно часто применяли для записи цикловых индексов два множества переменных. Кроме того, при перечислении смешанных графов в § 5.4 переменные s и появились в цикловом индексе редуцированной упорядоченной парной группы ( см. соотношение 5.4.5)); переменные sk соответствовали парам взаимно обратных циклов, а переменные tk - самообратным циклам. [29]

Введенные выше понятия и определения можно обобщить на смешанные графы. В качестве примера определим понятие подграфа и отношение включения для смешанных графов. [30]

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