![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Алгоритм выбора минимальных сечений ⇐ ПредыдущаяСтр 3 из 3
Требуется выделить все минимальные сечения для рассмотренной структуры типа «мостик». Несложно показать, какие сечения являются минимальными. однако, если число элементов и их связей достаточно велико, то выбор минимальных сечений – трудоемкий процесс - число возможных сочетаний возрастает по степенной зависимости. Поэтому выбор минимальных сечений также следует переложить на плечи ПК. Рассмотрим один из методов выбора минимальных сечений, использующий элементы теории графов. Структура представляется в виде замкнутого графа, имеющего один вход А и один выход Е. В графе отсутствуют параллельные и последовательные элементы. Граф содержит: m = 7– число ребер; M=5– вершин. Разорвем ребра графа так, чтобы часть вершин (N; у нас N=3: A,B,C) была присоединена только ко входу графа, а остальные (M-N) – к выходу графа. Этим самым нарушится связь между входом и выходом графа и образованы две структуры, называемые (деревьями): подграфами. N=3 подграф – это совокупность 3-х вершин и ребер, связанных с этими 3-мя вершинами. N=K подграф – это совокупность вершин и ребер присоединенных ко входу и связанных с этими N вершинами. (M-N)=2 подграф, содержащий ребра, связанные с этими 2-мя вершинами, присоединенными ко выходу. При этом оборванные ребра 3,5,6 образуют минимальное сечение. Эти ребра, образующие минимальные сечения, можно выявить по следующему признаку: если для данного N=3 подграфа, связанного со входом, перечислить все ребра, непосредственно связанные со всеми его вершинами, то ребра, связывающие вершины данного N=3 подграфа встречаются дважды. Эти ребра исключаются, оставшиеся ребра и будут «висячими», оборванными, т.е. образовывать минимальное сечение. Т.о. задача поиска минимальных сечений сводится к задаче построения всех возможных подграфов графа. Для этого к одной из вершин графа (входу или выходу) последовательно присоединяются одна за другой вершины, непосредственно с ней связанные. В результате получаем Для построения N=3 подграфов к вершинам N=2 подграфов последовательно присоединяются по одной вершине, связанной с каждой вершиной данного N=2 подграфа и так далее. Т.о. для построения новых подграфов к каждому старому подграфу присоединяются одна за другой вершины, непосредственно связанные с каждой его вершиной.
(N=1) – подграф – вершина А (N=2) – подграфы – вершины А+В, А+С, А+Д (N=3) – подграфы – вершины АB+C, АB+D, АC+Д (N=4) – подграф – вершина АB+D · Для каждого
выписываются все ребра, непосредственно связанные с вершинами данного Ребра, входящие в совокупность ребер · Составляется массив N=1 подграф – это вход графа, вершина А.
Из множества полученных сечений выбираются минимальные сечения. Для этого все сечения представляются в порядке возрастания числа элементов и уточняется, не содержатся ли в сечениях с большим числом элементов сечения с меньшим числом элементов. Такие сечения не являются минимальными.
|
|||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2017-02-21; просмотров: 426; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.225.98.177 (0.005 с.) |