Cтраница 2
Как указывалось выше, сечение есть множество ребер графа, определяющих разделение его вершин. Сечения ориентируют, задавая им направления относительно одного из ребер каждого сечения, и помечают это направление стрелкой при линии, обозначающей сечение. [16]
Через fi7), EU соответственно обозначим множество ребер графа G, входящих в вершину и и исходящих из нее. [17]
Эти 12 хорд вместе с 24 сторонами многоугольника исчерпывают множество ребер искомого экстремального графа. [18]
Отметим, что 1) эти операции определены лишь для множества ребер графов, 2) все объединения и пересечения множеств ребер являются подмножествами множества, содержащего все множества ребер, и 3) обе операции рефлексивны. [19]
Теорема 2.2. Если граф вложить в гиперкуб, то все множество ребер графа можно разбить на непересекающиеся подмножества A / l5 M2, -, М такие, что для каждого /: М ( - паросочетательный разрез. [20]
Хорды, соединяющие эти пары точек, вместе с 30 сторонами многоугольника исчерпывают множество ребер искомого экстремального графа. [21]
Как мы видели в предыдущем параграфе, матроид M ( G) можно определить на множестве ребер графа G, взяв в качестве циклов матроида циклы графа G; при этом M ( G) называется циклическим матроидом графа О, и его ранговая функция равна коциклическому рангу х ( см. упр. Такие матроиды называются графическими матроидами; мы охарактеризуем их в следующем параграфе. [22]
Известен ряд - реберных стягиваемых подграфов графа G; это число способов выбора К ребер из множества ребер графа G. И число несвязных подграфов оказывается реконструируемым с помощью расширенной нами леммы Кэли. Существует аналогичная теория, рассматривающая вместо несвязных сепарабельные ( но связные) графы. [23]
Легко проверить, что множество всех простых циклов или множество всех простых разрезов связного графа образует матроид на множестве ребер графа. Обозначим через R кольцо целых чисел или кольцо вычетов по модулю простого числа. [24]
Наиболее естественным является способ интерпретации схемы графом, при котором множеству - М модулей схемы взаимно однозначно ставится в соответствие множество X вершин графа G ( X, U), а множеству 5 соединений схемы - множество U ребер графа. Однако этот метод, при своей простоте, не свободен от ряда недостатков: не учитываются геометрические размеры модулей, за счет развязки узлов схемы в графе G появляются полные подграфы, т.е. вводится большое число избыточных ребер в графе, затрудняющих решение задач проектирования. Кроме того, граф часто получается неплаыар-ным, хотя соответствующая ему схема планарна. [25]
Аналогично, 2 ( Г0 1 ( H)) Z ( Sp n) есть цикловой индекс группы, которая индуцируется группой Г ( Я) 5 Р П, действующей на множестве вершин графа Кр и множестве ребер графа Я. [26]
Множество ребер графа разбито иа три непересекающихся подмножества: R, Klt Кг. Ребрам каждого из этих подмножеств приписаны символы из Y, х, у следующим образом. Каждому ребру из R приписан символ пз Y, всем ребрам из Я приписаны различные символы, п все символы из Y приписаны ребрам из R. Если множество Y пусто, то пусто и множество Kz. Ребра, к-рым приписаны символы из х, наз. [27]
Множество ребер графа разбито на три непересекающиеся подмножества: R, Klt Ka. Ребрам каждого из этих подмножеств приписаны символы из У, х, у следующим образом. Каждому ребру из R приписан символ из У, всем ребрам из R приписаны различные символы, и все символы из У приписаны ребрам из R. Каждому ребру множества KI ( соответственно К2) приписаны символы из х ( соответственно у) так, что каждый символ может быть приписан нескольким ребрам, нек-рые символы могут быть не приписаны никаким ребрам. Если множество У пусто, то пусто и множество Кг. [28]
Паросочетательнъш разрезом назовем множество ребер графа, которое одновременно является разрезом и паросочетанием. [29]
Обе границы могут трактоваться единым образом. С другой стороны, если множество ребер графа G является объединением классов симметрической ассоциативной схемы, то величина 9 ( G) может быть вычислена с помощью методов линейного программирования. [30]