Множество - вершина - граф
Cтраница 1
Множество вершин графа называется доминирующим, если каждая вершина вне этого множества соединена ребром хотя бы с одной вершиной, принадлежащей ему. Среди доминирующих множеств существует хотя бы одно минимально доминирующее, содержащее минимальное число вершин. Это число называется числом доминирования для данного графа ( или числом его внутренней устойчивости) зв. [1]
Множество вершин графа G называется независимым, если никакие две из них не смежны. Наибольшее число вершин в таких множествах называется вершинным числом независимости графа G и обозначается P0 ( G) или рс. G) p / 2 тогда и только тогда, когда G имеет 1-фактор. [2]
Множество вершин графа G называется независимым, если никакие две из них не являются смежными. [3]
Множество вершин графа S то же, что и у графа &; две вершины в S смежны, если и только если они несмежны в графе S. Более того, если S сильный, то S также сильный. [4]
Множество S вершин графа G называется несравнимым, если для любой пары вершин vt и Vj из S ни У. Вершины из множества S называются несравнимыми. [5]
Множеством вершин графа G ( D R0) является множество D информационных элементов, а каждая дуга ( de d) соответствует условию dR0dj, т.е. записи 1 в позиции ( if) матрицы В. [6]
Пусть множество вершин графа ( 0 разбито на взаимно дополнительные подмножества X и У. Через 1 ( Х, У) обозначим множество всех ребер графа С, у каждого из которых один конец лежит в X, а другой - в У. [7]
Если множество вершин графа G может быть разбито на два непересекающихся непустых множества, V ( G) A ( J В, таким образом, что все ребра графа G соединяют вершины из А только с вершинами из В, то мы называем граф G двудольным, а пару ( А, В) - 2-разбиением графа G. [8]
Если множество вершин X графа G ( X, U) расположено на воображаемой замкнутой самонепересекающейся кривой, то отрезки этой кривой, соединяющие соседние вершины графа, образуют псевдогамильтонов цикл, содержащий как ребра и ( U, так и фиктивные ребра щф. [9]
Для этого множество вершин стянутого графа с помощью алгоритма, описанного в [69], разбивается на бикомпоненты - максимальные множества взаимодостижимых вершин. Вершины в этих подмножествах взаимодостижимы, и, кроме того, при добавлении к каждому подмножеству любых не принадлежащих ему вершин полученное при этом подмножество не обладает свойством взаимодостижимости, в отличие от такого, например, подмножества, как a, d, Ъ, так как, хотя вершины a, d, Ъ взаимодостижимы, они не образуют бикомпоненты, поскольку добавление к ним вершины е или с или вместе е и с дает новые подмножества взаимодостижимых вершин. [11]
Назовем концевым классом множество вершин графа, каждые две вершины которого сообщающиеся и из вершин которого нельзя попасть ни в одну вершину, не принадлежащую этому множеству вершин. [12]
Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества У. [13]
Назовем концевым классом множество вершин графа, каждые две вершины которого сообщающиеся и из вершин которого нельзя попасть ни в одну вершину, не принадлежащую этому множеству вершин. [14]
Заметим, что множество S вершин графа ( помеченных звездочкой на рис. 6.26) обладает следующими свойствами. [15]
Страницы: 1 2 3 4