Дискретная математика

135 для орграфа: И, если вершины v,- и vj соединены ребром, Л, если вершины v, и vj не соединены HI- ] И, ®^ли из вершины Vj идет дуга в вершину Vj, Л, если из вершины v,- нет дуги в вершину vj. Например, для графа, изображенного на рис. 5.13, в), и для орграфа, представленного на рис. 5.12, матрицы смежностей имеют соответственно вид: L;- (Л И И Л И Л л и и л л и Л'^ и И л L2 = 'л л л л и л л л и и л и и л л л При перемножении таких матриц смежностей умножение элементов матрицы понимается как конъюнкция, а сложение - как дизъюнкция. По введенной матрице смежности или её степеням, как и в предыдущем параграфе, можно определять наличие или отсутствие цепей (пугеЙ) заданной длины. Например, по матрице i * = LxLx...xL (здесь содержится к множителей X) можно определить налитее или отсутствие цепей (путей) длины к. Матрица L*^LvL^ vL' V ...VL" орграфа G e n вершинами содержит все сведения о путях любой длины между вершина.^.'и заданного орх-рафа G. Матрица L* считается матрицей достыжшюсти орграфа G. Вычислим матрицу дocтижи^юcтн орграфа, представленного на рис. 5.14 (пример взят из [17]). Матрица смежности L и матрицы L' и i J L = Рис. 5.14 'Л я л л\ (Л и л л ] /'Л и л л л и и , л л и и 1 i л и и ' • L' = л — л л л л л л л л л л [л л и л. U л и л) и л и л. ' л л и и\ (л л и \П л л Г[\ " 1 л л и л , л • 1' = л л . f _ л л л л 1 л л л л л л л л г л л л л U л л л. U л л л ] [л л л Л]