Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Математические модели электрических схем
Содержание
- 1. Математические модели электрических схем
- 2. 2. Модель схемы в виде гиперграфа H(E, U)
- 3. Матрица комплексов Q=qijnk
- 4. 3. Модель схемы в виде мультиграфа G(E, U)4. Модель схемы в виде взвешенного графа G(E, U)
- 5. Матрица соединений R=rijnn. Матрицу соединений легко получить из матрицы комплексов
- 6. Алгоритмы раскраски графаНеобходимо раскрасить вершины графа таким
- 7. 5. Если R , то переход
- 8. 10. Составляется конъюнкция П’ = ti. Раскрываются
- 9. В матрице R подсчитываем число ненулевых элементов
- 10. 5. R , max ri =
- 11. 12. Составляем конъюнкцию Ci и выполняем минимизацию
- 12. 1 = {x3, x6}, 2 = {x3,
- 13. Недостатком точных алгоритмов является низкое быстродействие. Поэтому
- 14. 1. Положим j = 1;2. Упорядочим вершины
- 15. 5. Упорядочим вершины графа в порядке не
- 16. Достоинство алгоритма – быстродействие. Недостаток – не
- 17. Математическая модель задачи размещенияПусть заданы множество элементов
- 18. Алгоритм обратного размещенияАлгоритм обратного размещения принадлежит группе
- 19. Учитывая условия минимальности скалярного произведения r×d, получим
- 20. Составим матрицы соединений R и расстояний D.Упорядочим
- 21. Значение целевой функции для полученного размещения F(р)=36Можно
- 22. Кратчайшие путиПусть дан граф G(X, Γ), ребрам
- 23. 1. Положить l(s)=0+ и считать эту пометку
- 24. Заданы взвешенный граф G(X,Г) и матрица весов
- 25. 2. Гp ={x2, x6, x7} – все
- 26. 6. l(xi*) = min[l(xi)] = l(x3) =
- 27. 12. l(xi*) = min[l(xi)] = l(x7) =
- 28. Кратчайшие расстояния от вершины x1 до всех
- 29. Далее, l(x2) = 2, Гx2 ={x1, x3,
- 30. 2. Самый длинный (критический) путь.Задача сетевого планирования,
- 31. Теорема Форда – Фалкерсона. Пропускная способность пути
- 32. Найти (s-t) путь с наибольшей пропускной способностью в графе G(X,U) 1818
- 33. 1. Проводим разрез К1 = ({s}, X
- 34. 5. Проводим разрез К2, находим6. Закорачиваем все
- 35. 8. Закорачиваем все ребра графа (xi, xj) с qij ≥ Q3. Получаем граф G3.
- 36. 9. Вершины s-t объединены. Пропускная способность искомого
- 37. Слайд 37
- 38. Скачать презентанцию
2. Модель схемы в виде гиперграфа H(E, U)
Слайды и текст этой презентации
Слайд 6Алгоритмы раскраски графа
Необходимо раскрасить вершины графа таким образом, чтобы смежные
вершины были окрашены в разные цвета. Минимальное число красок, в
которые можно раскрасить граф называется хроматическим числом графа.Задача раскраски вершин графа относится к NP-полным задачам. Различают точные и приближенные алгоритмы раскраски.
Примером точных алгоритмов служит алгоритм Вейссмана.
Алгоритм состоит из двух частей:
1. Построение семейства максимальных внутренне устойчивых множеств (МВУМ) (метод Магу);
2. Выбор минимального числа МВУМ, покрывающих все вершины графа (метод Петрика).
Множество вершин Хs графа G(X,U) называется внутренне устойчи-вым (независимым), если никакие две вершины из этого множества не смежны, XsX [ГXsXs=]. Внутренне устойчивое множество называется максимальным, если оно не является собственным подмножеством некоторого другого независимого множества.
Слайд 75. Если R , то переход к п. 2,
иначе к п. 6;
1. В матрице соединений R для каждой
вершины подсчитывается число ненулевых элементов ri;2. Находится вершина xi с max ri, если таких вершин несколько, то выбирается любая;
3. Для выбранной вершины xi записывается выражение
Ci = (xi xa xb...xq), где Гxi = {xa, xb, ..., xq};
4. Из матрицы R удаляются строка и столбец, соответствующие вершине xi;
6. Составляется конъюнкция П = Ci. Раскрываются скобки. В полученной дизъюнкции на основе законов булевой алгебры выполняется минимизация.
7. Результат минимизации записывается в виде П = Kj;
9. Для каждой вершины xiХ определяются подмножества j, в которые входит вершина xij. Составляется дизъюнкция ti = j;
8. Для каждого Kj ищутся вершины графа, не вошедшие в него. Получено j и семейство МВУМ = {1, 2, ..., l};
Слайд 810. Составляется конъюнкция П’ = ti. Раскрываются скобки. В полученной
дизъюнкции на основе законов булевой алгебры выполняется минимизация;
11. Получена дизъюнкция
конъюнктивных термов П’ = (j). Выбирается конъюнктивный терм j с минимальным числом сомножителей. Количество сомножителей в этом терме и есть хроматическое число графа. Число минимальных термов – число вариантов раскраски графа. А каждое j – множество вершин, которые можно окрасить в один цвет.
Заметим, что п.п. 1-8 составляют метод Магу, а п.п. 9-11 – метод Петрика.
Слайд 9В матрице R подсчитываем число ненулевых элементов ri;
3. Гx1 =
{x2, x3, x5, x6}, записываем выражение
C1 = (x1 x2 x3 x5 x6);2. max ri = r1 = r4 = 4, выбираем x1;
4. Из матрицы R удаляем строку и столбец, соответствующие вершине x1;
Слайд 105. R , max ri = r4 = 4;
Гx4
= {x2, x3, x5, x6},
C4 = (x4 x2
x3 x5 x6);6. Из матрицы R удаляем строку и столбец, соответствующие вершине x4;
7. R , max ri = r2 = r3 = r5 = r6 = 1, выбираем x2;
Гx2 = {x3}, C2 = (x2 x3);
8. Из матрицы R удаляем строку и столбец, соответствующие вершине x2;
9. R , max ri = r5 = r6 = 1, выбираем x5;
Гx5 = {x6}, C5 = (x5 x6);
10 . Из матрицы R удаляем строку и столбец, соответствующие вершине x5;
11. R = ;
Слайд 1112. Составляем конъюнкцию Ci и выполняем минимизацию
П =
Ci = C1 C2 C4 C5 = (x1 x2
x3 x5 x6)(x2 x3)(x4 x2 x3 x5 x6)(x5 x6) == x1 x2 x4 x5 x1 x2 x4 x6 x1 x3 x4 x5 x1 x3 x4 x6 x2 x3 x5 x6 = Kj =
= K1 K2 K3 K4 K5;
13. Для каждого Kj ищем j:
1 = {x3, x6}, 2 = {x3, x5}, 3 = {x2, x6}, 4 = {x2, x5}, 5 = {x1, x4}. Получено семейство МВУМ ;
14. Для каждой вершины определим подмножества j, в которые она входит. Строим дизъюнкцию ti = j;
t1 = 5; t2 = 3 4; t3 = 1 2; t4 = 5; t5 = 2 4; t6 = 1 3;
15. Составляем конъюнкцию и выполняем минимизацию булевой функции
П’ = ti = t1 t2 t3 t4 t5 t6 = 5(3 4)(1 2) 5(2 4)(1 3) = =145 235
Хроматическое число графа (G) = 3. Существует два варианта раскраски графа.
Слайд 121 = {x3, x6}, 2 = {x3, x5}, 3 =
{x2, x6}, 4 = {x2, x5}, 5 = {x1, x4}.
145
235с,с
с,с
к,к
к,з
з,з
з,к
Слайд 13Недостатком точных алгоритмов является низкое быстродействие. Поэтому на практике используют
приближенные алгоритмы, примером которых может служить
Алгоритм, использующий упорядочивание вершин
4.
Просматривая последовательность слева направо, красить в цвет j каждую неокрашенную вершину, не смежную с уже окрашенными в этот цвет;1. Положить j = 1;
2. В матрице R подсчитываем число ненулевых элементов ri;
3. Упорядочим вершины графа в порядке не возрастания ri.;
5. Если остались неокрашенные вершины, то удалить из матрицы R строки и столбцы, соответствующие окрашенным вершинам. Положить j = j + 1 и перейти к п. 2, иначе, задача решена.
Слайд 141. Положим j = 1;
2. Упорядочим вершины графа в порядке
не возрастания ri.
x1, x2, x3, x4, x5, x6, x7,
x8;3. Красим в первый цвет вершины x1 и x3. Вершины x4, и x8 смежны вершине x3, остальные – смежны вершине x1;
4. Остались неокрашенные вершины, поэтому удалим из матрицы R строки и столбцы, соответствующие вершинам x1 и x3. Положим
j = j + 1 = 2.
Слайд 155. Упорядочим вершины графа в порядке не возрастания ri:
x2,
x4, x5, x6, x7, x8;
6. Красим во второй цвет вершины
x2, x4 и x8. Вершины x5 и x7, смежны вершине x4, вершина x6 смежна вершине x2;7. Остались неокрашенные вершины, удалим из матрицы R строки и столбцы, соответствующие вершинам x2, x4 и x8. Положим j = j + 1 = 3.
8. Упорядочим вершины графа в ri : x5, x6, x7.
9. Красим в третий цвет вершины x5 и x7. Вершины x6 и x5 смежны;
10. Осталась неокрашенная вершина, удалим из матрицы R строки и столбцы, соответствующие вершинам x5 и x7. Положим j = j + 1 = 4.
11. В четвертый цвет окрашиваем вершину x6.
Все вершины окрашены.
Слайд 16Достоинство алгоритма – быстродействие. Недостаток – не оптимальность.
Для раскраски вершин
графа приближенным алгоритмом потребовалось четыре цвета. А хроматическое число графа
(G) = 3.Действительно, если в первый цвет окрасить вершины x1, x4 и x8, во второй – x2 и x5, то в третий можно окрасить оставшиеся вершины x3, x6 и x7.
Алгоритмы размещения элементов
Постановка задачи
Задано множество конструктивных элементов, связанных между собой в соответствии с принципиальной электрической схемой узла. Требуется разместить элементы на некотором плоском коммутационном поле таким образом, чтобы некоторый функционал достигал экстремального значения.
Классическим критерием задачи размещения является критерий суммарной длины соединений, который интегральным образом учитывает многочисленные требования, предъявляемые к расположению элементов и трасс их соединений.
Слайд 17Математическая модель задачи размещения
Пусть заданы множество элементов E={e1, e2, …,
em} и множество фиксированных позиций для размещения элементов P{ p1,
p2, …, pl} (l ≥ m, будем считать, что l = m). Схема задана матрицей соединений R=rijmm, а расстояние между позициями матрицей расстояний D=dijll. Для вычисления элементов матрицы D будем пользоваться ортогональной метрикой, координаты позиций.
Учитывая симметричность матриц R и D, запишем выражение для суммарной длины соединений
Таким образом, задача размещения по критерию СДС состоит в минимизации функционала F(P) на множестве перестановок Р. Данная задача называется задачей квадратичного назначения.
Слайд 18Алгоритм обратного размещения
Алгоритм обратного размещения принадлежит группе алгоритмов параллельно-последовательного размещения.
В
методе обратного размещения осуществляются предварительные оценки каждого из размещаемых элементов
и каждой свободной позиции, после чего все элементы размещаются одновременно.Заданы: матрица соединений R и матрица расстояний D.
Для каждого элемента ei найдем суммарное число соединений с другими элементами
Для каждой позиции pi найдем суммарное расстояние до остальных позиций
Очевидно, что позиции в центральной части коммутационного поля имеют меньшую характеристику di, чем позиции на периферии. Естественно, что центральные позиции наиболее благоприятны для размещения сильно связанных элементов.
Слайд 19Учитывая условия минимальности скалярного произведения r×d, получим следующий алгоритм:
1. Упорядочить
элементы ei в порядке не убывания ri;
2. Упорядочить позиции pi
в порядке не возрастания di;3. i-ый элемент из упорядоченного списка элементов помещается в i-ую позицию из упорядоченного списка позиций.
Разместить элементы, заданные взвешенным графом G на множестве позиций Р.
Слайд 20Составим матрицы соединений R и расстояний D.
Упорядочим элементы ei в
порядке не убывания ri
{e5, e4, e3, e6, e2, e1}.
2.
Упорядочим позиции pi в порядке не возрастания di {p1, p3, p4, p6, p2, p5}.
3. Размещаем элементы в соответствии с упорядоченными списками
Слайд 21Значение целевой функции для полученного размещения F(р)=36
Можно поменять позиции вершин,
размещенных в равноценные позиции. Так, можно переставить вершины e4 и
e6.Целевая функция размещения F(р)=24.
У оптимального размещения значение целевой функции F(р)=22.
Слайд 22Кратчайшие пути
Пусть дан граф G(X, Γ), ребрам которого приписаны веса,
заданные матрицей C=cijm×m. Задача о кратчайшем пути состоит в нахождении
пути с минимальным суммарным весом от начальной вершины sX до конечной tX или от начальной вершины sX до всех остальных, при условии, что такие пути существуют.Рассмотрим алгоритм Дейкстры. Он основан на приписывании вер-шинам временных пометок, дающих верхнюю границу длины пути от s к этой вершине. Эти пометки постепенно уточняются, и на каж-дом шаге итерации точно одна из временных пометок становится постоянной. Это указывает на то, что пометка уже не является верхней границей, а дает точную длину кратчайшего пути от s к рассматриваемой вершине.
Алгоритм работает только для графов без ребер отрицательного веса.
Пусть l(xi) пометка вершины xi, а l(xi)+ - постоянная пометка вершины.
Слайд 231. Положить l(s)=0+ и считать эту пометку постоянной. Положить l(xi)=∞
для всех xi ≠ s и считать их временными. Положить
p=s.2. Для всех xi Гр, пометки которых временные, изменить пометки в соответствии со следующим выражением
l(xi) = min[l(xi), l(p) + c(p,xi)].
3. Среди всех вершин с временными пометками найти такую, для которой l(xi*) = min[l(xi)].
4. Считать пометку вершины xi* постоянной l(xi*)+ и положить p= xi*.
5. (Если надо найти лишь путь от s до t).
Если p=t, то l(p) – длина кратчайшего пути, конец. Если p ≠ t, перейти к п.2.
6. (Если надо найти путь от s до всех остальных вершин).
Если все вершины имеют постоянные пометки, то конец, если есть временные пометки, то перейти к п.2.
Сами пути можно получить при помощи рекурсивной процедуры с использованием соотношения: l(xi’) + c(xi’, xi)= l(xi), где xi’ – вершина, непосредственно предшествующая вершине xi в кратчайшем пути от s к xi.
Слайд 24Заданы взвешенный граф G(X,Г) и матрица весов C=׀׀cij׀׀7×7. Необходимо найти
кратчайшие пути от начальной вершины x1 ко всем остальным вершинам.
1.
l(x1)=0+; l(xi)= ∞, для всех i ≠ 1, p = x1. Результаты итерации запишем в таблицу.
Слайд 252. Гp ={x2, x6, x7} – все пометки временные, уточним
их:
l(x2)=min[∞ ,0++2]=2;
l(x6)=min[∞, 0++10]=10;
l(x7)=min[∞, 0++17]=17.3. l(xi*) = min[l(xi)] = l(x2) = 2.
4. x2 получает постоянную пометку l(x2) = 2+, p=x2.
5. Не все вершины имеют постоянные пометки, Гp ={x1, x3, x7} – временные пометки имеют вершины x3, x7, уточняем их:
l(x3)=min[∞, 2++3]=5; l(x7)=min[17, 2++10]=12.
![2. Гp ={x2, x6, x7} – все пометки временные, уточним их: l(x2)=min[∞ ,0++2]=2;](/img/tmb/6/509720/6a523a8f17a4f9dbfbd8d5fc60e4efe6-800x.jpg "Математические модели электрических схем 2. Гp ={x2, x6, x7} – все пометки временные, уточним их:")
Слайд 266. l(xi*) = min[l(xi)] = l(x3) = 5.
7. l(x3) =
5+, p=x3.
8. Не все вершины имеют постоянные пометки, Гp ={x2,
x4, x6} – временные пометки имеют вершины x4, x6, уточняем их: l(x4)=min[∞ , 5++15]=20; l(x6)=min[10, 5++3]=8.
9. l(xi*) = min[l(xi)] = l(x6) = 8.
10. l(x6) = 8+, p=x6.
11. Гp ={x1, x5, x7} – временные пометки имеют вершины x5, x7, уточняем их: l(x5)=min[∞ , 8++15]=23; l(x7)=min[12, 8++3]=11.
![6. l(xi*) = min[l(xi)] = l(x3) = 5.7. l(x3) = 5+, p=x3.8. Не все вершины имеют постоянные](/img/tmb/6/509720/78c69095a948f92384f192ef4681cffd-800x.jpg "Математические модели электрических схем 6. l(xi*) = min[l(xi)] = l(x3) = 5.7. l(x3) = 5+,")
Слайд 2712. l(xi*) = min[l(xi)] = l(x7) = 11.
13. l(x7) =
11+, p=x7.
14. Не все пометки постоянные, Гp ={x1, x2, x4,
x6} – временную пометку имеет вершина x4, уточняем ее: l(x4)=min[20, 11++5]=16.15. l(xi*) = min[l(xi)] = l(x4) = 16.
16. l(x4) = 16+, p=x4.
17. Не все пометки постоянные, Гp ={x3, x5, x7} – временную пометку имеет вершина x5, уточняем ее: l(x5)=min[23, 16++5]=21.
18. l(xi*) = l(x5) = 21.
19. l(x5) = 21+, p=x5.
20. Все пометки постоянные.
![12. l(xi*) = min[l(xi)] = l(x7) = 11.13. l(x7) = 11+, p=x7.14. Не все пометки постоянные, Гp](/img/tmb/6/509720/6be7dd7e8a500739ddc0c7b5b423371d-800x.jpg "Математические модели электрических схем 12. l(xi*) = min[l(xi)] = l(x7) = 11.13. l(x7) = 11+,")
Слайд 28Кратчайшие расстояния от вершины x1 до всех вершин найдены.
Как
найти кратчайший путь до конкретной вершины, покажем на примере вершины
x5.l(x5) = 21, Гx5 ={x4, x6},
21 = l(x4)+ c(x4, x5)=16+5, 21 ≠ l(x6)+ c(x6, x5)=8+15.
Это означает, что в вершину x5 мы попали из вершины x4.
Далее, l(x4) = 16, Гx4 ={x3, x5, x7}, 16 ≠ l(x3)+ c(x3, x4)=5+15,
16 ≠ l(x5)+ c(x5, x4)=21+15, 16 = l(x7)+ c(x7, x4)=11+5.
Это означает, что в вершину x4 мы попали из вершины x7.
Далее, l(x7) = 11, Гx7 ={x1, x4, x6}, 11 ≠ l(x1)+ c(x1, x7)=0+17,
11 ≠ l(x4)+ c(x4, x7)=16+5, 11 = l(x6)+ c(x6, x7)=8+3.
Это означает, что в вершину x7 мы попали из вершины x6.
Далее, l(x6) = 8, Гx6 ={x1, x3, x5, x7}, 8 ≠ l(x1)+ c(x1, x6)=0+10,
8 = l(x3)+ c(x3, x6)=5+3, 8 ≠ l(x5)+ c(x5, x6)=21+15, 8 ≠ l(x7)+ c(x7, x6)=11+3.
Это означает, что в вершину x6 мы попали из вершины x3.
Далее, l(x3) = 5, Гx3 ={x2, x4, x6}, 5 = l(x2)+ c(x2, x3)=2+3,
5 ≠ l(x4)+ c(x4, x3)=16+15, 5 ≠ l(x6)+ c(x6, x3)=8+3.
Это означает, что в вершину x3 мы попали из вершины x2.
Слайд 29Далее, l(x2) = 2, Гx2 ={x1, x3, x7}, 2 =
l(x1)+ c(x1, x2)=0+2,
2 ≠ l(x3)+ c(x3, x2)=5+3, 2 ≠ l(x7)+
c(x7, x2)=11+10.Это означает, что в вершину x2 мы попали из вершины x1.
Кратчайший путь от вершины x1 до вершины x5 найден .
Задачи, близкие к задаче о кратчайшем пути
1. Наиболее надежный путь.
В этом случае вес ребра представляет его надежность. Надежность пути от s к t, составленного из ребер, взятых из множества P, задается формулой где ρij – надежность ребра (xi, xj).
Слайд 302. Самый длинный (критический) путь.
Задача сетевого планирования, заключающаяся в нахождении
самого длинного по временной протяженности пути в сетевом графике, определяющего
продолжительность работ по выполнению проекта.3. Путь с наибольшей пропускной способностью.
В этом случае каждое ребро графа имеет пропускную способность qij и требуется найти путь от s к t с наибольшей пропускной способностью. Пропускная способность пути P определяется ребром из P с наименьшей пропускной способностью, т.е.
Определение. Если множество вершин графа G(X,U) разбить на два подмножества Х1 и Х2 (где Х=Х1 Х2), то множество ребер графа, одни концевые вершины которых лежат в Х1, а другие в Х2, называется разрезом графа G.
Слайд 31Теорема Форда – Фалкерсона. Пропускная способность пути с наибольшей пропускной
способностью от s к t равна
где К – любой (s-t) разрез.
Алгоритм Франка – Фриша
1. Взять (s-t) разрез К1 = ({s}, X\{s}) и найти
2. Закоротить все ребра графа (xi, xj) с qij≥Q1, т.е. заменить вершины xi и xj на вершину х, удалив ребро (xi, xj), положить Гх=Гxi Гxj.
3. Для полученного графа G1 выбрать другой (s-t) разрез К2 и найти
4. Закоротить все ребра графа (xi, xj) с qij≥Q2. Получить граф G2 … и т.д., пока не будут объединены вершины s-t.
5. Теперь каждый (s-t) путь в графе G', образованный вершинами из G и теми ребрами, которые оказались закороченными, будет иметь максимальную пропускную способность.
Слайд 331. Проводим разрез К1 = ({s}, X \{s})
18
2. Находим
3. Закорачиваем все ребра графа (xi, xj) с qij≥Q1.
4. Это ребра (s, x4), (x3, x6), (x5, x8), (x6, x9) и (x7, x12). Получаем граф G1.
18
Слайд 345. Проводим разрез К2, находим
6. Закорачиваем все ребра графа (xi,
xj) с qij≥Q2. Это ребра (s, x4, х3, х6, х9),
(х1, х2, x5, x8, t). Получаем граф G2.7. Проводим разрез К3, находим
Слайд 369. Вершины s-t объединены. Пропускная способность искомого пути Q(P)=13.
10.
Строим граф, вершины которого – вершины исходного графа G, а
ребра – ребра с пропускной способностью qij ≥ Q(P)=13.18
Путь с наибольшей пропускной способностью.
