определения доминирующего
определения
доминирующего множества графа G эквивалентна задаче нахождения такого наименьшего множества столбцов в
матрице А*, что каждая строка матрицы содержит единицу хотя бы в одном из выбранных столбцов. Задачу о поиске наименьшего множества столбцов, “покрывающего” все строки матрицы, называют задачей о наименьшем покрытии. В общем случае матрица не обязательно является квадратной, кроме того, вершинам графа (столбцам) может быть приписан вес, в этом случае необходимо найти покрытие с наименьшей общей стоимостью. Если введено дополнительное ограничение, суть которого в том, чтобы любая пара столбцов не имела общих единиц в одних и тех же строках, то задачу называют задачей о наименьшем разбиении.
Замечание. 1. Если некоторая строка матрицы А* имеет единицу в единственном столбце, то есть больше нет столбцов, содержащих единицу в этой строке, то данный столбец следует включать в любое решение. 2. Рассмотрим множество столбцов матрицы А*, имеющих единицы в конкретной строке. Для
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
