Cтраница 2
Чтобы D0 - du не было доминирующим множеством, необходимо и достаточно, чтобы выполнялось хотя бы одно из этих условий. [16]
Приведите пример, показывающий, что наименьшее доминирующее множество может не быть независимым. [17]
Любой неориентированный граф без изолированных вершин имеет такое доминирующее множество D, что его дополнение D также является доминирующим множеством. [18]
Доминирующее множество называется минимальным, если нет другого доминирующего множества, содержащегося в нем. [19]
Мы видели, что максимальное независимое множество обязательно является доминирующим множеством. Покажите на примере, что это не обязательно так. [20]
Тогда дополнение Г) минимального доминирующего множества D является доминирующим множеством. [21]
Теорема 13.1.1. Если граф G локально конечен, то любое доминирующее множество содержит минимальное. [22]
Теорема 13.1.3. Любой неориентированный граф без изолированных вершин имеет такое доминирующее множество D, что его дополнение D также является доминирующим множеством. [23]
Для конечных графов теорема 13.1.2 может быть использована для сведения доминирующего множества к минимальному. Заметим, что любая вершина v, в которой нет входящих ребер, должна принадлежать каждому доминирующему множеству. [24]
Для конечных графов теорема 13.1.2 может быть использована для сведения доминирующего множества к минимальному. Заметим, что любая вершина и, в которой нет входящих ребер, должна принадлежать каждому доминирующему множеству. [25]
Для доминирующих множеств, однако, требуется обычно найти просто наименьшее доминирующее множество, и поэтому мы ограничимся здесь описанием алгоритма построения такого множества. В следующем разделе мы рассмотрим задачу о нахождении наименьшего доминирующего множества с несколько более общих позиций; это поможет нам глубже разобраться в взаимосвязях между понятиями, рассматриваемыми в других частях книги. [26]
Привести несколько графов, для которых наибольшее независимое множество совпадает с наименьшим доминирующим множеством. Существуют ли классы графов, которые обладают этим свойством. [27]
Показать, что в любом регулярном степени 5 графе на 16 вершинах можно выбрать доминирующее множество, состоящее из 5 вершин. [28]
Число доминирования 6 ( G) графа G есть наименьшее число вершин, составляющих минимальное доминирующее множество. Это число появляется в различных задачах-головоломках. Примером может служить так называемая задача о пяти ферзях на шахматной доске. [29]
Число доминирования 6 ( G) графа G есть наименьшее число вершин, составляющих минимальное доминирующее множество. Это число появляется в различных задачах-головоломках. Примером может служить так называемая задача о пяти ферзях на шахматной доске. Требуется разместить на доске пять ферзей так, чтобы они держали под боем каждую клетку. [30]