Национальный цифровой ресурс Руконт - межотраслевая электронная библиотека (ЭБС) на базе технологии Контекстум (всего произведений: 634655)
Контекстум
.
Вестник Московского университета. Серия 1. Математика. Механика  / №3 2010

О СТЯГИВАНИИ ЦИКЛОВ В ОРИЕНТИРОВАННЫХ ГРАФАХ (60,00 руб.)

0   0
Первый авторНаливайко
Страниц3
ID360052
АннотацияДля решения задачи об отыскании в ориентированном графе ветвления минимального веса среди всех ветвлений максимальной мощности существует эффективный алгоритм, разработанный Тарьяном, основанный на технике стягивания циклов. В данной работе показывается, что эта техника применима и к более общей задаче, в которой на ветвление наложено дополнительное условие о том, что множество покрытых им вершин должно быть независимо относительно заданного матроида.
УДК519.1
Наливайко, П.В. О СТЯГИВАНИИ ЦИКЛОВ В ОРИЕНТИРОВАННЫХ ГРАФАХ / П.В. Наливайко // Вестник Московского университета. Серия 1. Математика. Механика .— 2010 .— №3 .— С. 39-41 .— URL: https://rucont.ru/efd/360052 (дата обращения: 23.04.2024)

Предпросмотр (выдержки из произведения)

40 L2(Ω),таких,что Ω qdx =0; напомним также, что символом L2 обозначается пространство функций f, таких, что Ω f2dΩ < ∞,а H1 теоретические оценки для непрерывного аналога неравенств (1). <...> Непрерывный аналог дополнения по Шуру S — оператор ˜ 0νminν−1 S := −div[divν(x)D]−1 0 в L2 понимаемая в обобщенном смысле, принадлежит L2 и которые принимают на ∂Ω нулевое значение), и нижняя оценка эквивалентна следующему неравенству: 0 — пространство интегрируемых функций, первая производная которых, cνν−1 2 ˜ для всех q из L ∈ L2 Если d =2,то q2  sup v∈H1 0(Ω) (q, divv)2 ν 1 2Dv2 (2) на случай весовых норм. <...> Пусть ν — достаточно гладкая функция и все нормы определены. <...> Заметим, что (2) можно рассматривать как обобщение неравенства Нечаса [5] (2) будет выполнено для всех q ∈ L2(Ω),таких,что (q, ν−1 2 cν =˜ ˜ для любых k> 2, s> 0 и r = 2k t = t(s, k),а ˜ для любых k> 3 и r = 3k Строго говоря, эта оценка доказана только для непрерывных пространств. <...> Зачастую оценки из теоремы 1 можно существенно улучшить, рассматривая область как объединение ν является гладкой на каждой из подобластей. <...> Тогда (2) выполняется для всех q ∈ L2(Ω),таких, что (q, ν−1 подобластей и проводя вычисления на каждой подобласти, а не во всей области сразу. <...> Ценой такого обобщения будут дополнительные условия ортогональности. <...> На практике это означает, что если у нас область разбита, например, на две подобласти, то мы имеем оценку на собственные значения начиная с 5-го в порядке возрастания. <...> Каждое собственное значение, не учтенное оценкой, увеличивает число итераций линейного метода не более чем на одну. <...> Применение полученных оценок к численному моделированию конвекции мантии. <...> Рассмотрим применение предобусловливателя ˆ Sν и оценки его эффективности к одной задаче моделирования тепловой конвекции в мантии Земли. <...> В качестве модельной задачи мы взяли подъем раскаленного пузыря из [6]. <...> Расчет ведется в единичном квадрате, вязкость зависит от температуры, которая является функцией от координат: ν =exp(−αT),T <...>