Реферат: Дискретная математика 3

§8. Деревья.29

§9. Двудольные графы.31

§10. Укладка графов.33

§11. Планарные и плоские графы. Теорема Эйлера о плоских графах.33

§12. Раскрашивание графов.35

Литература_ 36

Введение

Слово «дискретный» происходит от латинского discretus, что означает разделенность, прерывистость и противопоставляется непрерывности. Например, дискретное изменение какой-либо величины во времени – это изменение, происходящее через определенные промежутки времени (скачками); система целых чисел (в противоположность системе действительных чисел) является дискретной.

Дискретная математика – область математики, занимающаяся изучением свойств дискретных структур, которые возникают как внутри математики, так и в ее приложениях (в частности, в вычислительной технике и программировании). Традиционно к дискретной математике относят такие области математического значения, как комбинаторика, теория чисел, математическая логика, теория алгебраических систем, теория графов и т.д.

Комбинаторика

Простейшие понятия комбинаторики появились еще в доньютоновский период (П.Ферма, Б.Паскаль, Франция XVIII в.). Комбинаторика возникла как основа дискретной теории вероятностей в связи с исследованиями в области азартных игр.

Напомним некоторые важные обозначения. Множества будем обозначать заглавными буквами, а элементы множеств – малыми буквами.

а∈А – элемент а принадлежит множеству А.

{a, b, x, y} – в фигурных скобках изображаются множества заданные перечислением элементов.

|A| - мощность множества, количество множества.

А´В={(a,b) | a∈A, b∈B} – прямое произведение множеств.

АÈВ={x| x∈A или x∈B} – объединение множеств.

АÇВ={x| x∈A и x∈B} – пересечение множеств.

А\В={x| x∈A и xÏB} – разность множеств.

Æ – пустое множество.

U – универсальное множество.

=U\А={x| xÏA} – дополнение множества.

§1. Правила суммы и прямого произведения.

Правило суммы . Пусть А и В конечные множества такие что АÇВ=Æ, |A|=m, |B|=n. Тогда |AÈB|=m+n.

В общем случае: Пусть X₁ , X₂ , …, X_n – попарно не пересекающиеся множества, X_i ÇX_j =Æ, где i¹j. Тогда выполняется равенство: .

Правило прямого произведения. Пусть А, В – конечные множества, |A|=m, |B|=n. Тогда |A´B|=m∙n.

В общем случае: Пусть X₁ , X₂ , …, X_k – произвольные множества, |X_i |=n_i , i=. Тогда |X₁ , X₂ , …, X_k |=|{(x₁ , x₂ , …, x_k )| x_i ∈X_i , i=}|=n₁ ∙n₂ ∙…n_k .

Пример. Сколько четырехзначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, если: а) ни одна из цифр не повторяется более одного раза; б) цифры могут повторяться; в) числа должны быть нечетными (цифры могут повторяться)?

Решение.

а) Первой цифрой числа может быть одна из пяти цифр: 1, 2, 3, 4, 5. Когда первая цифра выбрана, то вторая может быть выбрана пятью способами, третья цифра уже может быть выбрана четырьмя способами, четвертая – тремя способами. Согласно правилу умножения общее число способов равно: 5∙5∙4∙3=300.