Множество - вершина - граф
Cтраница 2
Естественно, что множество вершин графа G разбивается относительно вершины х, на два подмножества. [16]
В случае обхода множества вершин графа имеется только ряд достаточных условий существования цикла, проходящего по всем вершинам графа по одному разу. [17]
Порядок на всем множестве вершин графа, а также порядок вершин, смежных всякой его вершине, соответствует алфавитному порядку букв, помечающих вершины. [18]
Рассмотрим следующий пример: множество вершин графа представляет группу людей, дуга, направленная от вершины х к вершине X ], означает, что х является другом или родственником х тогда данный граф должен быть симметрическим. С другой стороны, если дуга, направленная от х к X ], означает, что вершина х подчинена вершине х (, то такой граф должен быть антисимметрическим. [19]
Рассмотрим следующий пример: множество вершин графа представляет группу людей, дуга, направленная от вершины xt к вершине х, означает, что xt является другом или родственником xf, тогда данный граф должен быть симметрическим. С другой стороны, если дуга, направленная от xt к Xj, означает, что вершина х подчинена вершине xh то такой граф должен быть антисимметрическим. [20]
Пусть Хр - подмножество множества вершин X графа О ( X, Г), и предположим, что Хр содержит р вершин. [21]
G-Я является декартово произведение множества вершин графов G и Я, и две различные вершины графа G-Я смежны, если и только если в обеих координатах элементы равны или смежны. [22]
Для нахождения минимальной раскраски множества вершин графа G А. А. Зыков [68] предлагает использовать вышеописанный метод X. [23]
Пусть Хр - подмножество множества вершин X графа G ( X, Г), и предположим, что Хр содержит р вершин. [24]
Логическая матрица отношения на множестве вершин графа, которое задается его ребрами, называется матрицей смежности. Симметричность отношения в терминах матрицы смежности М означает, что М симметрична относительно главной диагонали. [25]
Спрашивается, есть ли - элементное множество вершин графа, любые две вершины которого соединены ребром. [26]
На этом этапе легко определить разбиение множества вершин графа G на четыре класса, аналогичное разбиению Галлаи - Эдмондса. Однако оказывается, что несколько труднее вывести важные свойства этого разбиения. Впрочем, определение разбиения достаточно простое. В случае 1-паросочетания мы основываем нашу декомпозицию на том, покрывается или нет та или иная вершина всеми наибольшими паросочетаниями. [27]
Из сказанного следует также, что множеством вершины графа GO является множество S. Значит, для обоснования эквивалентности неравенства (7.3.1) неравенству, содержащемуся в пункте ( iii) доказываемой теоремы, нужно только установить справедливость следующего свойства. [28]
 |
Минимальный связный подграф графа, изображенного на, содержащий вершины t i, PZ, vz. [29] |
Множество вершин графа-отношений G2 совпадает с множеством вершин графа Glr и дуга ( В, С) принадлежит графу G2 тогда и только тогда, когда собственное подмножество основного ключа отношения С содержится в отношении В. [30]
Страницы: 1 2 3 4