КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Матрицы и графы. Нахождение путей и сечений с помощью структурной матрицыТрудно переоценить роль матриц в теории графов (в частности, матрицы полезны, чтобы данный граф более “легко” воспринимался компьютером). Перечислим наиболее известные матрицы.
Легко видеть, что матрица В =А 2 = АА составлена из целых чисел bij,которые равны числу путей длины 2, соединяющих вершины i и j. Понятно, что А 3составлена из чисел, равных числу путей длины 3 (т. е. путей из 3-х ребер) из вершины i ввершину j и т. д.
Отметим, что в учебных целях, когда действия с матрицами осуществляются студентами “вручную” (число вершин в графе невелико), можно обозначать ребра латинскими буквами без индексов a, b, c и т. д., но при использовании компьютера гораздо удобнее обозначать ребра а (i,j), если это ребро соединяет вершины i и j при i<j и с чертой сверху, если i>j. Теорема. Для того чтобы найти все пути (простые) из вершины i в вершину j достаточно раскрыть минор M (j, i) структурной матрицы методами булевой алгебры. При этом раскрытие минора производится обычными действиями с определителями, но при этом сложение заменяется дизъюнкцией, умножение – конъюнкцией, знаки умножения на числа не используются. Подробно доказывать эту теорему не будем, но отметим, что определитель равен сумме (в данном случае дизъюнкции) элементов, взятых по одному из каждой строчки и каждого столбца с определенным знаком. В нашем случае знаки не присутствуют, а значит, любой член раскрытия определителя всей структурной матрицы S соответствует циклу в графе. Если же брать минор M (j,i),то его раскрытие соответствует тем членам определителя, в которых имелся элемент s (j,i),но безсамого этого элемента (таким образом, индексы i и j встречаютсявместо двух только один раз). Это и означает, что получаем маршрут от вершины с номером i к вершине с номером j. Понятно, что раскрытие минора методами булевой алгебры предусматривает, что верны следующие соотношения: 1Ú a = 1, (это свойство нужно, для того чтобы не проходить по одному ребру дважды в противоположных направлениях), а также используется правило простого поглощения (х Ú ху = х). Видно, что если не использовать правило поглощения, то получим все маршруты (без повторения ребер), связывающие вершины i и j. Примечание. 1. Если граф не ориентирован, то миноры M (j,i)и M(i,j) совпадают. 2. После получения ответа, черточки над обозначениями ребер (т. е. отрицания) можно убрать (на самом деле “черта” над ребром означает, что ребро проходится от вершины с большим номером к вершине с меньшим номером). Затем рекомендуется записать каждый путь по порядку прохождения ребер (в этом случае удобны обозначения ребер с индексами вершин). Сечением (разрезом) междувершинами i и j называется неизбыточный набор ребер, при удалении которых из графа теряется связь между данными вершинами (не существует пути из вершины i в вершину j). Заметим, что сечений между данными вершинами может быть много, и они могут содержать разное количество ребер. Слово “неизбыточный” означает, что если любое ребро из сечения снова возвратить в граф, то связь восстановится. Естественно, что если известны все пути из вершины i в вершину j, причем эти пути заданы в виде ДНФ, т. е. дизъюнктивной нормальной формы (а именно такой вид получается после раскрытия соответствующего минора структурной матрицы), то все сечения между этими вершинами можно получить отрицанием этих путей (по правилу де Моргана конъюнкцию заменить на дизъюнкцию и наоборот), затем полученное выражение снова привести к ДНФ, используя раскрытие скобок по обычным правилам, при этом правило поглощения обеспечит неизбыточность набора ребер в каждом сечении. Ясно, что знаки отрицания (черточки над символами ребер) можно опустить. Пример на эту тему приведен в разд. 15 (примеры решения типовых задач).
Дата добавления: 2015-05-09; Просмотров: 765; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |