Cтраница 4
На рисунке, в качестве примера, приведена часть графа технологического процесса изготовления корпуса аппарата. Граф показывает, что параметры разовой детали изменяются не только от операции к операции, но и в некоторых случаях оказывают ллкяние на другие параметры. В основе графа лежит ориентированное ребро, условно снабженное стрелкой. Оно указывает на передачу свойств в процессе обработки заготовки. Ребра графа могут быть и неориентированные, показывающие, что свойства обьекта не передаются. На графе неориентированные ребра изображаются в виде ребра без стрелки. [46]
Пусть G ( A) содержит цикл С, в котором имеется нечетное число / неориентированных ребер. Вычислим определитель матрицы В. Для этого прибавляем к строке i, содержащей элемент aie - 1, строку р с элементом аре 1, в результате получим столбец с единственным ненулевым элементом аре, и, разлагая определитель по элементам этого столбца, получим detfi detfi, где В - ( k - I) x X ( k - 1) - матрица, отвечающая циклу С, который получен из С после стягивания орребра е и выбрасывания вершины i. Продолжая эту процедуру, в конце концов получим ( / х /) - матрицу инциденций цикла, составленного из / неориентированных ребер. [47]
Минимальным доминирующим множеством называется такое доминирующее множество, что никакое его подмножество не обладает этим свойством. Числом доминирования 5 ( 7) графа называется наименьшее число вершин, составляющих минимальное доминирующее множество. Число 5 ( 7) появляется в различных задачах. Например, требуется разместить на шахматной доске минимальное число ферзей так, чтобы они держали под боем каждую клетку доски. Для решения задачи достаточно 5 ферзей; меньшего числа недостаточно. Тогда для графа этой игры число доминирования 5 ( 7) 5, где клетки доски - это вершины графа; две клетки связаны неориентированным ребром, если ферзь, поставленный на одну из клеток, угрожает другой. [48]