Что такое deg в математике
Перейти к содержимому

Что такое deg в математике

  • автор:

Список математических аббревиатур

Статья содержит список общеупотребительных аббревиатур математических функций, операторов и др. математических терминов.

Аббревиатуры

Примечание. Обычно регистр буквы имеет значение.

Латиница

  • adj — союзная матрица;
  • Ai — функция Эйри;
  • arccos — функция арккосинуса;
  • arccosec — функция арккосеканса (в англоязычной традиции arccsc);
  • arcctg — функция арккотангенса (в англоязычной традиции arccot);
  • arcsch — функция гиперболического ареакосеканса (в англоязычной традиции arcosech);
  • arch — функция гиперболического ареакосинуса (в англоязычной традиции arcosh);
  • arcth — функция гиперболического ареакотангенса (в англоязычной традиции arcoth);
  • arcsec — функция арксеканса;
  • arcsin — функция арксинуса;
  • arctg — функция арктангенса (в англоязычной традиции arctan);
  • arg — аргумент комплексного числа;
  • arg max — аргумент максимизации;
  • arg min — аргумент минимизации;
  • arsch — функция гиперболического ареасеканса (в англоязычной традиции arsech);
  • arsh — функция гиперболического ареасинуса (в англоязычной традиции arsinh);
  • arth — функция гиперболического ареатагенса (в англоязычной традиции artanh);
  • Aut — группа автоморфизмов модели;
  • Bi — функция Эйри второго рода;
  • card — мощность множества;
  • ch — функция гиперболического косинуса (в англоязычной традиции cosh);
  • char — характеристика кольца;
  • Ci, ci, Cin — функции интегрального косинуса;
  • cl — топологическое замыкание;
  • cod — область значений функции;
  • const — константа;
  • cos — функция косинуса;
  • cosec — функция косеканса (в англоязычной традиции csc);
  • cov — ковариацияслучайных величин;
  • csch — функция гиперболического косеканса(в англоязычной традиции cosech);
  • ctg — функция котангенса (в англоязычной традиции cot);
  • cth — функция гиперболического котангенса (в англоязычной традиции coth);
  • D — дисперсия случайной величины (в англоязычной традиции var);
  • def — дефиниция;
  • deg — степень многочлена (также обозначается как ∂);
  • del — оператор набла (также обозначается как\nabla, однако обычно отдельно не употребляется);
  • det — определитель матрицы или линейного преобразования (также обозначается как|\cdot|);
  • diag — диагональная матрица;
  • dim — размерностьвекторного пространства;
  • div — дивергенция векторного поля (также обозначается как\nabla\cdot);
  • dom — область определения функции;
  • End — эндоморфизм модели;
  • Ei — интегральная показательная функция;
  • erf — функция ошибок;
  • erfc, Erf — дополнительная функция ошибок;
  • exp — экспоненциальная функция;
  • ext — внешность топологии;
  • Gal — группа Галуа (также обозначается как Γ);
  • НОД — наибольший общий делитель (в англоязычной традиции gcd, hcf);
  • grad — градиент поля (также обозначается как\nabla);
  • id — тождественное отображение;
  • Im — мнимая часть комплексного числа или образ (также обозначается как\Im);
  • inf — точная нижняя грань;
  • int — внутренняя точка множестваили внутренность множества;
  • Ker — ядро;
  • lb — двоичный логарифм (log2);
  • НОК — наименьшее общее кратное (в англоязычной традиции lcm);
  • lg — десятичный логарифм (log10) или двоичный логарифм (log2);
  • Li, li — функция интегрального логарифма;
  • lim — предел последовательности или функции;
  • ln — натуральный логарифм, loge;
  • log — логарифм;
  • logit — обратная к логистической функции;
  • max — максимум функции или множества;
  • min — минимум функции или множества;
  • QED — что и требовалось доказать или quod erat demonstrandum;
  • probit — нормальная квантильная функция;
  • Re — действительная часть комплексного числа (также обозначается как\Re);
  • Rk — ранг матрицы (также обозначается как Rg, Rang, Rank);
  • rot — ротор векторного поля (также обозначается как\nabla\times, только в англоязычной традиции curl);
  • sch — функция гиперболического секанса (в англоязычной традиции sech);
  • sec — функция секанса;
  • sgn — функция сигнум (также обозначается как sign);
  • Si, si — функция интегрального синуса;
  • sin — функция синуса;
  • sh — функция гиперболического синуса (в англоязычной традиции sinh);
  • Sp — см. Tr;
  • span — линейная оболочка;
  • sup — точная верхняя граница множества (в англоязычной традиции lub);
  • supp — носитель функции;
  • Sym — симметрическая группа;
  • tg — функция тангенса (в англоязычной традиции tan);
  • th — функция гиперболического тангенса (в англоязычной традиции tanh);
  • Tr — след поля или след матрицы или линейного преобразования (также обозначается как Sp);
  • WO — Вполне упорядоченное множество; [источник не указан 768 дней]
  • ZF — аксиомы Цермело — Френкеля теории множеств;
  • ZFC — аксиомы Цермело — Френкеля с аксиомой выбора теории множеств.

Греческий алфавит

Вы поможете проекту, исправив и дополнив его.

что обозначает в калькуляторе deg, grad, rad

Различные единицы измерения углов — градусы, грады и радианы. Используется, в основном, при вычислении тригонометрических функций.

Остальные ответы

Нормальный режим, градусы и радианы. ну вроде как.

Градусы
Если на дисплее отображается «D» или «DEG», значит выбран режим задания углов в градусах.
Градус – это 1/360 длины окружности. Один градус обозначается как 1゜.
Радианы
Если на дисплее отображается «R» или «RAD», значит выбран режим задания углов в радианах (Radian).
Радиан – это 1/2πr длины окружности. Измерение углов в радианах называется «радианной мерой угла».
1 рад = 360゜/(2π)
Грады
Если на дисплее отображается «G» или «GRA», значит выбран режим задания углов в градах (Grad).
Град – это 1/400 длины окружности.
Проще говоря, чтобы нормально считать нужно всегда ставить DEG

Похожие вопросы

Об одном классе неприводимых многочленов Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Галиева Л. И., Галяутдинов И. Г.

Работа посвящена нахождению неприводимых многочленов с рациональными коэффициентами, корнями которых являются числа вида coskn/π, где k,n взаимно простые натуральные числа.

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Галиева Л. И., Галяутдинов И. Г.

Об одном классе вещественных подполей круговых полей
Класс многочленов со свойствами круговых многочленов
Об одном классе абелевых многочленов

НАХОЖДЕНИЕ МИНИМАЛЬНЫХ МНОГОЧЛЕНОВ АЛГЕБРАИЧЕСКИХ ЧИСЕЛ ВИДА TG 2(π/ N) С ПОМОЩЬЮ ПРЕОБРАЗОВАНИЯ ЧИРНГАУЗЕНА

Многочлены, порождающие максимальные вещественные подполя круговых полей
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

ON ONE CLASS OF IRREDUCIBLE POLYNOMINALS

The article is devoted to finding irreducible polynominals with rational coefficients and roots coskn/π, where k,n are mutually prime natural numbers.

Текст научной работы на тему «Об одном классе неприводимых многочленов»

ОБ ОДНОМ КЛАССЕ НЕПРИВОДИМЫХ МНОГОЧЛЕНОВ

Работа посвящена нахождению неприводимых многочленов с рациональными коэффициентами,

корнями которых являются числа вида cos , где k, n — взаимно простые натуральные числа.

Приведем основные определения и факты, которые будут использованы ниже [1].

Число t называется алгебраическим, если оно является корнем некоторого многочлена f (x) с рациональными коэффициентами. Среди таких многочленов найдется единственный нормированный многочлен p (x) наименьшей степени, который называется минимальным многочленом алгебраического числа t. deg p (x) называется степенью алгебраичности числа t. Все корни минимального многочлена называются сопряженными числами к числу t.

Если для многочлена p(x)e □ [x] число п

cos— является корнем, то ему присвоим индекс n

n. По этому соглашению p1 (x) = x +1,

p2 (x) = x, p3 (x) = 2x -1.

Аналогично, qn (x) e □ [x] будет означать,

что qn ^cos—j = 0. В частности, q1 (x) = x -1,

Пусть Tn (x), n = 0,1,2. — многочлены Чебышева [2]. Как известно, они обладают свойством Tn (cosa) = cosna и вычисляются по рекуррентной формуле Tn+1 (x) = 2xTn (x) — Tn_1 ( x),

T0 (x) = 1, T1 (x) = x , n = 1,2,3. Приведем примеры нескольких таких многочленов:

T2 (x) = 2×2 -1, T3 (x) = 4×3 — 3x,

T4 (x) = 8×4 — 8×2 +1, T5 (x) = 16×5 — 20×3 + 5x,

T6 (x) = 32×6 — 48×4 + 18×2 -1,

T7 (x) = 64×7 -112×5 + 56×3 — 7x .

Для многочленов Чебышева, pn (x) и qn (x) справедливы соотношения

pk (Tn (x)) = pn (x), qk (Tn (x)) = qkn (x) (1)

Действительно, в силу свойств многочленов Tn (x) и pk (x) имеем

= pk I cos k I = 0 и в то же время

pn I cos— | = 0. Полученные равенства означа-

pk (Tn (x)) = pim (x) . Аналогично доказывается,

что q, (Tn (x)) = q,n (x) .

В силу формулы (1) многочлены pn (x) и qn (x) могут быть вычислены несколькими способами. Например, число cosiS является корнем

многочленов pi (Т18 (x)) , p2 (Т; (x)), p3 (тб (x)) с

различными степенями. Особый интерес среди них представляют многочлены наименьшей степени. Алгоритм нахождения таких многочленов следует из теорем 1, 2 и 3.

Теорема 1. Пусть n = 2k +1 — натуральное число и p — функция Эйлера. Тогда имеется многочлен pn (x) є □ [x] степени ip(n) с корнями sn

чения, взаимно простые с n.

Теорема 2. Пусть n = 2k +1 — натуральное число и p — функция Эйлера. Тогда имеется многочлен qn (x) є □ [x] степени ) с корнями

ния, взаимно простые с n.

Теорема 3. Пусть n = 2k — натуральное число и P — функция Эйлера. Тогда имеется многочлен

pn (x) є □ [x] степени p(n) с корнями cos — ,

Доказательство теорем 1 и 2 приведено в ра- Но в нашем случае НОД(2,к) = 1. Поэтому

боге [3]. Заметим, 1гго многочлены р(х) н р(„) = р(2к) = р(2)р(к) = р(к) . Тогда

д.(х), о которых говорися в зпта теорема, свя- р^ ^ (х)) = р( к ) = р( 2к) = р( п) = deg р, (х).

тт имеют одинаковые корни. Отсюда следует, что

Доказательство теоремы 3 проведем индук- ,-,ч

равенство (3) имеет место и в том случае, когда

цией по к . При к = 1 имеем р2 (х) = х, сое— — п = 2к и к — нечетное число.

2 Теорема 3 доказана.

его к°ренц deg р2 (х) = 1 = р(2). Если к = 2, то Справедлива также.

р4 (х) = 2х2 -1, deg р4 (х) = 2 = р(4). Корнями Теорема 4. Многочлены рп (х) и дп (х), поп 3п строенные в теоремах 1, 2 и 3, неприводимы над

р4(х) являются числа с08~ и со§_^. Предпо- полем □ рациональных чисел.

члены рт (х)є □ [х], deg рт (х) = р(т) и корня- п п

— первообразный корень п -ой степени из 1. Как

иґМТҐ \ 1 т а “ члена Ф„ (х) деления круга [2], степень которого

НОД ($, т ) = 1. Требуется найти многочлен п\ / « п 1 ^

/ \ ,, „ равна р(п), является алгебраическим числом

рп (х) с перечисленными в теореме 3 свойствами ґ п г

при п = 2к степени р(п) . Поэтому □ (ип) — расширение

индуктивному предположению имеется много- 2п ( 2п’\

член рк (х) такой, что аеврк (х) = р(к) и числа = 2со§— и расширение □ <Уп) = □ I со*— I •

Vn = un + un-1 п0лучаем un2 =Vnun — i, т.е. un — к0-

Построим многочлен рк (Т2 (х)) и покажем, что он является искомым многочленом. Действительно, аеврк (2 (х)) = 2аеврк (х) = 2р(к) = коэффициентами из расширения □ (уп) • Значит,

рень многочлена / (х) = х2 -Упх +1 степени 2, с

= р(2к) = р(п) = deg рп (х) . Здесь учтено, что ес-

тельно, поле и (ип) содержит комплексные числа, а в поле □ (уп ) нет комплексных чисел. Таким образом, ст (□ (ип): □ (уп)) = 2. Но

ст (□ (ип ) : 0 ) = р(п ) = ст (□ (ип ) (У ))Х

хст (□ (уп): □ ) = 2ст (□ (уп): □ ) . Значит,

, ч . /, ч т, Но эта степень не может быть меньше 2, так

ли к — четное число, то р(2к) = 2р(к). Кроме , ч , ч

как поля □ уп) и □ (ип) не совпадают. Действи-

того, многочлены рк (Т (х)) и рп (х) имеют од- _ / ч

^ ; тельно, поле и (ип) содержит

ни и те же корни. Это означает, что

рп (х) = рк (Т2 (х)) , п = 2к . (3)

Таким образом, в случае п = 2к, к — четное теорема 3 доказана. ст (□ (ип): □ ) = р( п) = ст (□ (ип): □ (уп))

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Пусть теперь п = 2к и к — нечетное число.

Тогда, в силу теоремы 1, имеется многочлен

рк (х) с корнями со8^, где нечетное $ < к и ст (□ (уп): □ ) = -^р(п) .

НОД ($, к) = 1, причем deg рк (х) = ~Р(к). По- Итак, установлено, что уп = 2со8— — алгеб-

строим многочлен рк (т2(х)) и убедимся, что он раическое число степени -р(п) .

является искомым многочленом. 2

Имеем Рассмотрим многочлены дп (х), рп (х) при-

deg р„ (Г, (х )) = 2deg р, (х ) = 2±р(к ) = р(к). ве®»»ые в теоРе“ах ‘• 2’ 3‘

1. По теореме 2 имеем, что при . = 2k +1

многочлен qn(x) имеет корень cos—, причем

deg qn (x) = ^p(n) . Как показано выше,

—V. = cos— — алгебраическое число степени

ip(n) = deg qn (x) . Это означает, что многочлен

qn (x) — неприводим над полем □ .

2. По теореме 1, при n = 2k +1 многочлен

pn (x) имеет корень cos— = cos— и

degpn (x) = 1-p(n). Из сказанного выше имеем,

что степень числа cos— равняется

-2p(2n) = -2p(n) = degpn (x) . Значит, многочлен

pn (x) — неприводим над полем □ .

3. В силу теоремы 3 при n = 2k имеем, что deg pn (x) = p(n), а корнем многочлена pn (x)

является число cos— = cos—. Степень этого n 2n

числа равняется -^(2.) = p(n) = deg pn (x). Значит, многочлен pn (x) — неприводим над полем

Замечание. Если n — нечетное простое число,

то неприводимость многочленов p2n (x) и pn (x)

можно доказать и другим способом. Покажем это.

Из равенства p2 (Tn (x)) = Tn (x) следует, что корнями многочлена Т. (x) являются числа

tk = cos——п, где k = 1,2, к, n. Поэтому

Tn (x) = P2 (x)DP2n (x) = xP2n (x). Но при пр0ст0м n все коэффициенты многочлена Tn (x), за исключением старшего, делятся на n. Отсюда следует, что к многочлену p2n (x) можно применить

критерий Эйзенштейна. Значит, p2n (x) неприводим над полем □ и cos — — алгебраическое

число степени p(2n). Тогда, изучая степени расширений в последовательности

□ с □ I cos— I с □ [ cos—

□ I cos— I:□ =—p(2n) = — cp(n). В силу то-

го что степень расширения совпадает со степенью алгебраичности примитивного элемента,

t = cos — алгебраическое число степени 1p(n). В тоже время t — корень многочлена pn (x), причем deg pn (x) = 1p(n), т.е. степень алгебраичности числа t совпадает со deg pn (x). Это означает, что pn (x) неприводим над полем □ .

1. Найти неприводимый многочлен p12 (x) , корнем которого является число t = cos-—. Степень искомого многочлена p12 (x) равна

p(12) = 4. По формуле (3) имеем

p12 (x) = p6 (T2 (x)) . Но в силу формулы (1) многочлен p12 (x) может быть вычислен и другими способами. В частности, p12 (x) = p3 (T4 (x)) = = 2T4(x)-1 = 2(8×4 -8×2 +1)-1 = 16×4 -16×2 +1.

По теореме 4 этот многочлен является неприво-

димым, а его корни — cos—, cos—, cos— и

2. Найти неприводимый многочлен p14 (x) ,

корнем которого является число t = cos 14. При

к = 7 формула (3) принимает вид p7 (T2 (x)) = p14 (x). Учитывая, что

p7 (x) = 8 x3 — 4×2 — 4x +1, получаем

p14 (x) = 64×6 -112×4 + 56x — 7. Имеем

deg p14 (x) = 6 = p(14) и многочлен p14 (x) — неприводим по теореме 4, а его корнями являются

числа cos к—, к = 1,3,5,9,11,13.

Заметим, что в неприводимости многочлена p14 (x) можно убедиться и по критерию Эйзенштейна (при p = 7).

1. Математическая энциклопедия. М., 1977. Т.1.

2. Прасолов В.В. Многочлены. МЦИМО, 2003. зование в техническом вузе в XXI веке. Вып.2.

3. Галиева Л.И., Галяутдинов И.Г. Нахождение сте- Набережные Челны, 2008. пени одного класса алгебраических чисел // Обра-

ON ONE CLASS OF IRREDUCIBLE POLYNOMINALS

The article is devoted to finding irreducible polynominals with rational coefficients and roots cos —,

where k, n are mutually prime natural numbers.

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

На этой странице будут появляться различные материалы и объявления, связанные с курсом «Дискретная математика», читаемого для студентов 1-го курса ОП Вычислительные социальные науки в 2022/2023 учебном году.

  • Лекции и семинары: Сысоева Любовь Николаевна lsysoeva@hse.ru, telegram @lsysoeva
  • Ассистент: Ластовецкий Дмитрий dalastovetsky@hse.ru, telegram @dalastovetskiy

Формула итоговой оценки: 0,3 * Активность + 0,3 * Домашние задания + 0,4 * Экзамен

Контрольная

Итоговая контрольная состоится 16го декабря!
Большая просьба не опаздывать!!
Если все пойдет по плану, последние 30-50 минут занятий мы потратим на разбор задач из контрольной, чтобы у вас сразу было понимание, как вы написали и какие темы стоит повторить к экзамену. Оценка за экзамен будет выставляться как максимум из оценок за КР и за Экзамен.

Лекции

дата лекции тема лекции дополнительные материалы
16.09.2022 Понятие множества, конечные множества, задание множества перечислением элементов, задание множества условием, пустое множество, пересечение множеств, объединение множеств, декартово произведение множеств, парадокс брадобрея.

Комбинаторика: правило суммы, правило произведения, факториал, число размещений с повторениями и без повторений, число сочетаний.

Сочетания с повторениями (метод шариков и перегородок), типы предметов.

Треугольник Паскаля (количество путей от вершины вниз), рекуррентная формула (нижний элемент = сумме двух верхних).

Бином Ньютона, связь с треугольником Паскаля (коэффициенты в разложении (a+b) n это числа в n строке треугольника).

Числа сочетаний в треугольнике Паскаля, формула C k n = C k n-1 + C k-1 n-1 и ее комбинаторный смысл.

Сумма элементов n строки в треугольнике Паскаля равна 2 n (через удвоение суммы предыдущей строки, через разложение (1+1) n и через все подмножества множества из n элементов).

Полиномиальные коэффициенты (определение и формула).

Сумма знакопеременных элементов n строки в треугольнике Паскаля равна нулю (через удвоение элементов предыдущей строки с противоположными знаками, через разложение (1-1) n ).

Формулы для 11 2 , 11 3 , 11 4 и связь со строками треугольника Паскаля (доказательство через разложение 11 k = (10+1) k по биному Ньютона).

Формула включений-исключений: через диаграммы Эйлера-Вена для 2 и 3 множеств, формулировка в общем случае.

Принцип Дирихле (pigeonhole principle): если кроликов больше, чем клеток, то при рассадке кроликов по клеткам по крайней мере в одну клетку попадут по крайней мере два кролика.

Индукция: принцип математической индукции, база и переход их согласованность, индуктивное предположение, доказательство равенств, неравенств, разбор текстовой задачи (машина на краю пустыни). Примеры неверных доказательств по индукции (резиновый автобус, куча манки, одномастные лошади).

Линейные рекуррентные соотношения в разных задачах. Рекурсия (программирование, литература) и ее связь с рекуррентными соотношениями. Основная теорема о рекуррентных соотношениях (Master theorem): оценка сложности рекурсивных алгоритмов.

Рекуррентные записи n! и геометрических прогрессий.

Индукция: повторение, связь с рекуррентными соотношениями, пример вложенной индукции (количество разломов прямоугольной шоколадки).

Системы счисления: позиционные, примеры, n-ичные дроби, переводы между системами счислений целых чисел и дробных частей, погрешность в случае прерывания бесконечных дробей.

Римская система счисления: способы записи чисел, сложность алгоритмов сложения и умножения чисел.

Признаки делимости в n-ичной системе счисления: схожесть признаков делимости на n-1 и n+1 с признаками делимости на 9 и 11 для десятичной системы, схожесть признаков делимости на делители n с признаками делимости на 5 и 10 для десятичной системы.

Троичная система: взвешивание путем уравновешивания весов с двумя чашами.

Остатки от деления и вычеты: сложение, вычитание, умножение, поиск обратного вычета. Запись вычетов через отрицательные числа для удобства вычислений. Примеры, когда обратного вычета не существует (элемент и модуль не взаимно просты).

Алгоритм Евклида (с использованием остатка от деления по модулю): сам алгоритм и оценка числа итераций через числа Фибоначчи.

Диофантовы уравнения: примеры, великая теорема Ферма, линейные Диофантовы уравнения с двумя неизвестными, критерий разрешимости. Расширенный алгоритм Евклида: решение линейных Диофантовых уравнений с двумя неизвестными. Сведение поиска обратного по умножению элемента по модулю к решению линейного Диофантова уравнения с двумя неизвестными. Единственность обратного по умножению элемента по модулю (если существует, то единственный).

Малая теорема Ферма: формулировка, четыре доказательства (мультиномиальное разложение, индукция и бином Ньютона, раскраска бус, перемножение чисел специального вида), поиск обратного по умножению элемента через малую теорему Ферма в случае простого модуля.

1) проверка делимости на простые до корня из числа;
2) проверка взаимной простоты с числами от 2 до n-1;
3) (тест Ферма) проверка справедливости малой теоремы Ферма для чисел от 2 до n-1 (и числа Кармайкла);
4) (тест Рабина) проверка справедливости малой теоремы Ферма плюс корней из 1.

Китайская теорема об остатках: система сравнений по взаимнопростым модулям имеет единственное решение по произведению модулей. Доказательство и решения систем сравнений с помощью расширенного алгоритма Евклида.

Функция Эйлера: определение и вычисление для простых чисел, степеней простых чисел, составных чисел.
Теорема Эйлера: формулировка, малая теорема Ферма как частный случай, доказательство (аналогично 4 доказательству малой теоремы Ферма, через обратимые остатки и их перемножение).
Алгоритм кодирования с открытым ключом RSA: определение, корректность кодирования и декодирования, устойчивость к атакам.

Лекции по криптографии (тут довольно хорошо объяснен алгоритм RSA и еще много что)

Формула 2|E|=Σ deg(vi).
Маршрут, путь, простой путь, расстояние между вершинами (длина кратчайшего пути), диаметр графа (самое большое расстояние между вершинами).
Цикл, простой цикл.
Связный граф, компонента связности.
Оценка: количество компонент связности ≥ |V|-|E|.
Следствие: для поиска самого тяжелого камня среди n камней необходимо n-1 взвешивание.

Дополнительно: бинарное дерево поиска: поиск элемента, добавление элемента, удаление элемента, поиск следующего и предшествующего элементов.
Существование у произвольного дерева по крайней мере двух листьев (два доказательства: через формулу 2|E|=Σ deg(vi) и через максимально удаленные вершины).
Остовное дерево связного графа, возможность удаления из связного графа вершины вместе с ребрами без потери связности.
Правильная раскраска: определение, примеры, критерий 2-раскрашиваемости графа (отсутствие циклов нечетной длины).
Дополнительно: алгоритмы поиска в ширину (BFS) и глубину (DFS).

Эйлеровы циклы и пути: цикл (путь) проходящий по каждому ребру графа ровно один раз, критерии наличия Эйлерова цикла (пути) в неориентированном и ориентированном графах.
Гамильтоновы циклы и пути: цикл (путь) проходящий через каждую вершину графа ровно один раз, отсутствие критерия, NP-полнота задачи о поиске Гамильтонова цикла в графе, теорема Оре.
Чуть-чуть логики: формализация метода доказательства с помощью правила контрапозиции и метода доказательства от противного.

Сеть: ориентированный граф с истоком и стоком, с заданными пропускными способностями на ребрах.
Поток: неотрицательная функция, заданная на ребрах сети, на каждом ребре не превосходящая пропускной способности ребра и суммарно равная нулю в каждой вершине сети, кроме стока и истока.
Разрез: разбиение вершин сети на два множества S и T, содержащих соответственно исток и сток.
Пропускная способность разреза: сумма пропускных способностей ребер, ведущих из множества вершин S в множество вершин T.
Теорема Форда-Фалкерсона: величина максимального потока равна пропускной способности минимального разреза.
Алгоритм нахождения максимального потока в сети: начинаем с нулевого потока, ищем увеличивающий путь (лучше минимальной длины), увеличиваем поток, ищем следующий увеличивающий путь, увеличиваем поток и т.д.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *