1. Множества Лекция 1

Тема 1. Огромного количества
Лекция 1.
Цель – познакомить студентов с общими понятиями теории множеств и с разбиением огромного количества на классы.
    1. Общие понятия теории множеств

Язык теории множеств. Совокупа частей, объединённых неким признаком, свойством, составляет 1. Множества Лекция 1 понятие огромное количество. К примеру, огромное количество книжек в библиотеке, огромное количество студентов в группе, огромное количество натуральных чисел N и т. д.

Запись значит: элемент a принадлежит огромному количеству М, т. е 1. Множества Лекция 1. элемент a обладает неким признаком. Аналогично читается: элемент a не принадлежит огромному количеству М.
Огромное количество считается данным, если либо перечислены все его элементы, либо обозначено свойство, которым владеют те и только 1. Множества Лекция 1 те элементы, которые принадлежат данному огромному количеству. Само свойство именуется характеристическим. В качестве характеристического характеристики может выступать обозначенная для этого характеристики порождающая процедура, которая обрисовывает метод получения частей нового огромного количества из уже приобретенных 1. Множества Лекция 1 частей либо из других объектов. К примеру, огромное количество всех чисел, являющихся неотрицательными степенями числа 2 , можно задать при помощи порождающей функции по индуктивным правилам:
Если огромное количество не содержит частей 1. Множества Лекция 1, владеющих характеристическим признаком, то оно именуется пустым и обозначается .
^ Изображение множеств. Огромного количества комфортно изображать при помощи кругов Эйлера.
Огромное количество K на рис. 1.1 именуют подмножеством огромного количества М и обозначают 1. Множества Лекция 1 . Таким макаром, огромное количество K именуется подмножеством огромного количества M , если для хоть какого производится (т. е. влечёт ).
Нужно учесть различие в употреблении символов включения и принадлежности для огромного количества множеств 1. Множества Лекция 1.
Универсальным именуется огромное количество ^ U, состоящее из всех вероятных частей, владеющих данным признаком.
Равными именуют два огромного количества A и B, состоящие из схожих частей: .
Число частей огромного количества A именуется мощностью 1. Множества Лекция 1 огромного количества и обозначается либо .
Огромное количество A можно разбить на классы непересекающихся подмножеств Ai, если:

    1. Соответствия меж огромными количествами. Отображения
Главные понятия. Пары задают соответствие меж огромными количествами A и B, если обозначено правило R, по которому для элемента огромного количества A выбирается элемент из огромного 1. Множества Лекция 1 количества B.
Пусть для некого элемента a огромного количества A поставлен в соответствие некий элемент b из огромного количества B, который именуется образом элемента a и записывается . Тогда - прототип элемента , который обладает 1. Множества Лекция 1 качествами единственности и полноты:
Образ огромного количества A при согласовании R именуется обилием значений этого соответствия и 1. Множества Лекция 1 обозначается , если состоит из образов всех частей огромного количества A.
Прототип огромного количества B при неком согласовании R именуют областью определения этого соответствия и обозначают , т.е. ; является оборотным соответствием для R 1. Множества Лекция 1.
Задание отображений. Для описания соответствий меж огромными количествами употребляют понятие отображения (функции) 1-го огромного количества на другое.
Для задания отображения нужно указать:

При записи предполагается, что отображение f определено везде на A, т.е. A – полный прототип отображения f, хотя для B такое свойство полноты не предполагается. Конкретным 1. Множества Лекция 1 именуется отображение, где каждому аргументу поставлено в соответствие менее 1-го вида.

Метод задания отображений в виде формул именуется аналитическим.

Для задания отображения множеств табличным методом принято строить таблицу, в какой первую строчку составляют 1. Множества Лекция 1 элементы области определения, а вторую строчку – их образы, т.е. элементы вида при отображении , где (табл. 1.1).
Таблица 1.1
Табличное задание отображения
x a1 a2 an
(x) (a1) (a2) (an)
^ Графическое представление отображения 1. Множества Лекция 1 связано со стрелочными схемами (диаграммами либо графами).
Отображения и именуются равными, если .
Виды отображений. По мощности конкретные отображения делятся на сюръективные и инъективные (рис. 1.2).

Отображения





На огромное количество
«сюръекция»
Соответствие. при котором каждому элементу огромного количества ^ А 1. Множества Лекция 1 указан единственный элемент огромного количества В, а каждому элементу огромного количества В можно указать хотя бы один элемент огромного количества А, именуется отображением огромного количества А на огромное количество В

Во 1. Множества Лекция 1 огромное количество
«инъекция»
Соответствие. при котором каждому элементу огромного количества ^ А указан единственный элемент огромного количества В, а каждому элементу В соответствует менее 1-го прообраза из А, именуется отображением огромного количества А во 1. Множества Лекция 1 огромное количество В





^







Рис. 1.2. Систематизация отображений по мощности




Отображение огромного количества А на огромное количество В, при котором каждому элементу огромного количества В соответствует единственный элемент огромного количества А, именуется взаимно-однозначным соответствием меж 2-мя огромными 1. Множества Лекция 1 количествами, либо биекцией.
Пусть огромное количество А отображается взаимно-однозначно на огромное количество В, т.е. . Тогда отображение , при котором каждому элементу огромного количества В ставится в соответствие его прототип 1. Множества Лекция 1 из огромного количества А, именуется оборотным отображением для f и записывается либо .
Если меж элементами множеств установлено взаимнооднозначное соответствие, то эти огромного количества равносильны, равномощны, либо эквивалентны.
Композиция функций. Отображение , при котором 1. Множества Лекция 1 каждому элементу соответствует определённый элемент , таковой, что , где , именуется произведением, композицией, либо суперпозицией отображений и . Распространённая ошибка: запись вида , где символ «» - умножение в R, не является композицией либо суперпозицией этих функций. Дело в 1. Множества Лекция 1 том, что произведение функций определено на огромном количестве функций, а выражение обозначает произведение значений каждой из функций в каждой определенной точке.
Отображение именуется тождественным (единичным), если каждому аргументу оно ставит в соответствие 1. Множества Лекция 1 себя.
^ Равенство функций определяется действием их на всех элементах.
1.3. Систематизация множеств. Мощность огромного количества
Основной чертой множеств является количество частей, содержащихся в этом огромном количестве.
Число частей огромного количества ^ М именуется 1. Множества Лекция 1 его мощностью и обозначается |M|. Огромного количества А и В именуются эквивалентными, либо равномощными, А  В, если меж их элементами можно установить взаимно-однозначное соответствие.
Огромное количество, содержащее конечное число частей, именуется конечным 1. Множества Лекция 1. Пустое огромное количество является конечным и имеет мощность, равную нулю, т.е. . Огромное количество, не являющееся конечным, именуется нескончаемым.
Нескончаемое огромное количество, эквивалентное огромному количеству натуральных чисел N, именуется счётным. В неприятном случае 1. Множества Лекция 1 нескончаемое огромное количество будет несчётным. Огромное количество именуется нескончаемым, если оно равномощно одному из собственных собственных подмножеств.
Булеаном огромного количества М именуется огромное количество всех его подмножеств, которое обозначается 2М, т 1. Множества Лекция 1.е. .
Для конечных множеств справедливо утверждение, которое именуется основной аксиомой о конечных огромных количествах.
^ Аксиома. Хоть какое конечное огромное количество не эквивалентно никакому его собственному подмножеству, не считая себя самого.
Следствие. Всякое 1. Множества Лекция 1 непустое конечное огромное количество эквивалентно одному и только одному отрезку натурального ряда чисел .
^ Счётными являются огромное количество Z целых чисел и Q оптимальных чисел. Огромное количество R реальных чисел несчётно.
Всякое нескончаемое огромное количество 1. Множества Лекция 1, равносильное огромному количеству реальных чисел, именуется обилием мощности континуума (от лат. continuum – непрерывный).
^ 1.4. Кортежи. Декартовы произведения
Слово кортеж переводится с французского cortege как праздничная процессия.
Пару назовём упорядоченным обилием, либо перестановкой 1. Множества Лекция 1, из п частей, если А – конечное огромное количество, состоящее из п частей, - функция, задающая порядок на А. Кортежем длины п из частей огромного количества А именуется упорядоченная последовательность частей этого 1. Множества Лекция 1 огромного количества, причём на первом месте стоит прототип единицы: .
Кортежи и именуются равными, если они имеют схожую длину и их элементы с схожими номерами совпадают, т. е. = , если и для .
Операция, при помощи 1. Множества Лекция 1 которой из 2-ух кортежей длиной k и m можно составить новый кортеж длиной k + m, в каком поначалу идут попорядку элементы первого кортежа, а потом – элементы второго кортежа, именуется соединением кортежей.
Конечное огромное количество 1. Множества Лекция 1 А, элементами которого являются некие знаки, именуют алфавитом над данным обилием знаков. Алфавит есть кортеж попарно различимых знаков, именуемых знаками алфавита. Элементы огромного количества Ап принято именовать словами длины п в 1. Множества Лекция 1 алфавите А.

Кортежи, элементы которых являются только нулями либо единицами, именуются упорядоченными наборами либо векторами.

Каждый таковой п-мерный вектор единственным образом определяет верхушку куба, построенного на единичных векторах (рис. 1.3).
^ Вектор из 1. Множества Лекция 1 нулей и единиц можно рассматривать как двоичное представление натурального числа. Вектор, состоящий из единиц и нулей, обрисовывает состояние памяти вычислительных машин, причём память может содержать числа, тексты, команды и т.д.
Практический прикладной 1. Множества Лекция 1 нрав кортежей проявляется в использовании штриховых кодов, которые обширно используются в разных информационных системах для сообщения определённой инфы о характеристике объекта. К примеру, штрих-кодом снабжены продукты на базе 1. Множества Лекция 1 либо в магазине.
^ Декартово произведение
Декартовым (прямым) произведением множеств именуется огромное количество , состоящее из всех кортежей длины п, в каких , где .
Если , то пишут и именуют п-й декартовой степенью огромного количества А.
В прямоугольной 1. Множества Лекция 1 декартовой системе координат координаты точек являются кортежами.
Изоморфизм
Функция именуется бинарной операцией на М. Огромного количества и , где - бинарные операции, соответственно, на огромных количествах М и N, именуются изоморфными 1. Множества Лекция 1, если существует биекция , такая, что для всех частей выполнено условие . В таком случае взаимно-однозначное соответствие s именуется представлением огромного количества М во огромном количестве N.

1.5. Дела. Бинарные дела и их характеристики
Главные 1. Множества Лекция 1 понятия. Соответствие меж равными огромными количествами А = В именуется отношением на данном огромном количестве (А).
Подмножество именуется п-местным отношением R на непустом огромном количестве М. При п = 2 отношение R именуется бинарным 1. Множества Лекция 1. Другими словами бинарным отношением меж элементами множеств А и В именуют хоть какое подмножество R огромного количества и записывают .
^ Характеристики бинарных отношений.

  1. Рефлективность: aRa.
  2. Антирефлективность.

  3. Симметричность всех 2-ух частей. Отношение R на 1. Множества Лекция 1 огромном количестве М именуется симметричным, если для всех сразу справедливо aRb и bRa.
  4. ^ Антисимметричность.

  5. Транзитивность.
  6. Антитранзитивность.

  7. Связность.
Отношение эквивалентности. Бинарное отношение R именуется отношением эквивалентности, если оно сразу обладает 3-мя качествами: рефлективностью 1. Множества Лекция 1, симметричностью и транзитивностью, т.е если для всех х, у, z производится:
Непересекающиеся подмножества, на которые разбивается огромное количество М 1. Множества Лекция 1 отношением эквивалентности, именуются классами эквивалентности. Огромное количество классов эквивалентности огромного количества А относительно дела эквивалентности Q именуется фактор-множеством и обозначается A \ Q.
Отношение толерантности. Отношение А на огромном количестве М именуется отношением 1. Множества Лекция 1 толерантности, если оно рефлективно и симметрично.
Отношение порядка. Отношение R именуется отношением порядка на огромном количестве М, если оно обладает качествами качествами антисимметричности и транзитивности. Для случайного дела порядка принято обозначение , значащее 1. Множества Лекция 1 предшествование.
Огромное количество М, которое обладает отношением порядка, именуется упорядоченным.
Рефлективное (антирефлективное) отношение порядка именуют отношением нестрогого (серьезного) порядка и обозначают знаком (<).
На огромном количестве М задано отношение полного (частичного) порядка 1. Множества Лекция 1, если сравнимы все (не все) элементы этого огромного количества.
Отношение порядка даёт возможность ассоциировать меж собой разные элементы огромного количества М. Об упорядоченной паре молвят, что элемент х предшествует элементу у. Если 1. Множества Лекция 1 для элемента х не нашлось предыдущего, то он именуется наименьшим: т. е. не существует частей у, «меньших», чем х.
Если понятно, что А и В – упорядоченные огромного количества с отношениями порядка, подобными 1. Множества Лекция 1 < и , и , то функция именуется однотонной (строго однотонной), если из следует, что ().
Многофункциональные дела. Многофункциональными отношениями, либо функцией, именуется бинарное отношение , для которого каждому элементу х из области определения ставится в 1. Множества Лекция 1 соответствие единственный элемент у из области значений. Если отношение и ему оборотное являются многофункциональными, то функция определяет взаимно-однозначное соответствие, либо биекцию.
Проверочная работа № 3 по теме «Отношения»
В – 1
1. Даны огромного количества и . Понятно, что 1. Множества Лекция 1 .
^ Составьте отношение и постройте график обозначенного дела: . 2. Растолкуйте, будут ли выполнимы характеристики отношений на данном огромном количестве людей и почему: «быть знакомым»?
3. Существует ли взаимно-однозначное соответствие меж обилием букв 1. Множества Лекция 1 и обилием звуков российского языка?


Проверочная работа № 3 по теме «Отношения»
В – 2
1. Даны огромного количества и . Понятно, что .
Составьте отношение и постройте график обозначенного дела: . ^ 2. Растолкуйте, будут ли выполнимы характеристики отношений на данном огромном 1. Множества Лекция 1 количестве людей и почему: «быть отцом»?
3. Существует ли взаимно-однозначное соответствие меж обилием чисел, записанных в арабской и двоичной системах счисления?


Проверочная работа № 3 по теме «Отношения»
В – 3
1. Даны огромного количества 1. Множества Лекция 1 и . Понятно, что .
Составьте отношение и постройте график обозначенного дела: . ^ 2. Растолкуйте, будут ли выполнимы характеристики отношений на данном огромном количестве людей и почему: «поздравлять с праздником»?
3. Существует ли взаимно-однозначное соответствие меж 1. Множества Лекция 1 обилием чисел и обилием студентов вашей группы?


Проверочная работа № 3 по теме «Отношения»
В – 4
1. Даны огромного количества и . Понятно, что .
Составьте отношение и постройте график обозначенного дела: . ^ 2. Растолкуйте, будут ли выполнимы характеристики отношений 1. Множества Лекция 1 на данном огромном количестве людей и почему: «встречаться»?
3. Существует ли взаимно-однозначное соответствие меж словом на российском языке и его значением?


Проверочная работа № 3 по теме «Отношения»
В – 5
1. Даны огромного количества и . Понятно, что 1. Множества Лекция 1 .
Составьте отношение и постройте график обозначенного дела: . ^ 2. Растолкуйте, будут ли выполнимы характеристики отношений на данном огромном количестве людей и почему: «быть другом»?
3. Существует ли взаимно-однозначное соответствие меж создателем и музыкальным произведением?


Проверочная работа 1. Множества Лекция 1 № 3 по теме «Отношения»
В – 6
1. Даны огромного количества и . Понятно, что .
^ Составьте отношение и постройте график обозначенного дела: . 2. Растолкуйте, будут ли выполнимы характеристики отношений на данном огромном количестве людей и почему: «быть 1. Множества Лекция 1 ровесником»?
3. Существует ли взаимно-однозначное соответствие меж заглавием и музыкальным произведением?
^ 1.7. Элементы комбинаторики
Раздел арифметики, занимающийся подсчётами количества разных композиций меж объектами, именуется комбинаторикой.
^ Правило суммы.
Задачка 1. Сколько человек в группе занимается 1. Множества Лекция 1 спортом, если 9 человек занимаются лыжами и плаванием, а 12 человек – плаванием и волейболом, причём в секцию по плаванию прогуливаются 4 человека из группы (рис. 1.4)?
^ Решение. Имеем: Ключевое слово для внедрения правила суммы – слово либо 1. Множества Лекция 1.
^ Правило произведения. Это правило позволяет отыскать, к примеру, количество всех пар из декартова произведения 2-ух множеств, а потому что в декартово произведение входят и элементы первого, и элементы второго огромного количества, то 1. Множества Лекция 1 при решении задач принципиально держать в голове ключевое слово и.
Пример 2. В институте есть три варианта занятий по интересам: творческие объединения (ТО), спортивные секции (СС) и научное студенческое общество (НСО). Каждое 1. Множества Лекция 1 направление содержит по четыре вида обществ: ТО – театральный, музыкальный, танцевальный и КВН; СС – лёгкая атлетика, лыжи, спортивные игры и плавание. В состав НСО входят естественно-математическое, гуманитарное, техническое и информационное направления 1. Множества Лекция 1. Сколькими методами студенты могут варьировать собственный досуг в институте после занятий, выбрав коллектив по интересам?
Решение. Потому что нужно учитывать и три главных направления, и то, что в каждом из их по четыре 1. Множества Лекция 1 коллектива, то для подсч1та общего числа вариантов их необходимо перемножить: .
Личным случаем правила произведения является число размещений с повторениями для подсчёта кортежей длины k, составленных из частей огромного количества Х, мощность которого т 1. Множества Лекция 1.
Перестановки. Для того, чтоб решить задачку о том, сколькими методами можно переставлять элементы огромного количества мощности п, чтоб получить разные кортежи длины п, нужно отыскать число перестановок длины п 1. Множества Лекция 1.
Упорядоченные огромного количества (кортежи), состоящие из п разных частей, именуются перестановками (без повторений).
Формула именуется рекуррентной и даёт возможность подсчитать число перестановок во огромном количестве из п частей через подстановки во огромном количестве из 1. Множества Лекция 1 частей.
Размещения (без повторений). Упорядоченное подмножество т частей (кортеж), составленное из всего огромного количества, содержащего п частей, именуется размещением (без повторений). Число таких размещений обозначается (от фр. arrangement – размещение).
Задачка 3. Сколькими методами 1. Множества Лекция 1 из разных нечётных цифр можно составить разные трёхзначные числа?
Решение. Нечётных цифр 5: 1, 3, 5, 7, 9. Тогда количество разных трёхзначных чисел найдём по формуле
^ Сочетания без повторений.
Сочетаниями из п частей по т именуется неупорядоченное подмножество 1. Множества Лекция 1 (подборка), состоящая из т частей, взятых из огромного количества, состоящего из п частей. Число сочетаний обозначается (от фр. combinaison – сочетание).
Задачка 4. Сколькими методами могут взойти 3 зерна пшеницы, если посажено 7 зёрен?
Решение 1. Множества Лекция 1. По условию задачки порядок в подмножестве из 3 зёрен не важен, потому по формуле сочетания имеем:
Перестановки с повторениями. Кортеж, имеющий повторяющиеся элементы, именуется перестановкой с повторениями.
^ Личные случаи

  1. Если , то .
  2. Если , то .

3. Если 1. Множества Лекция 1 а , то
^ Задачка 5. Сколькими методами можно расставить белоснежные фигуры на первой полосы шахматной доски?
Решение. На первой полосы могут находиться повелитель, ферзь, 2 ладьи, 2 жеребца и 2 слона. Без учёта принятых шахматных правил 1. Множества Лекция 1 составим кортежи длины 8, имеющие обозначенный состав (1, 1, 2, 2, 2). Тогда число перестановок с повторениями найдём по формуле
Задачка 6. Отыскать число точек скрещения диагоналей выпуклого п-угольника, если никакие три из их не пересекаются в одной 1. Множества Лекция 1 точке.
Решение. Малый многоугольник с диагоналями имеет четыре верхушки. Если взять любые четыре верхушки многоугольника, то через их можно провести две диагонали, пересекающиеся снутри этого четырёхугольника. Другие четыре верхушки дадут новейшую точку скрещения 1. Множества Лекция 1 диагоналей. Потому число точек скрещения диагоналей многоугольника, а означает и число четвёрок-вершин, можно отыскать при помощи сочетаний .
Задачка 7. Разложить п разных деталей в т ящиков. Сколько разных вариантов таких размещений можно 1. Множества Лекция 1 перебрать?
Решение. Такое число подсчётов вариантов именуют размещением с повторением и обозначают . Потому что каждую из п деталей можно расположить в т ящиков, то нужно п раз множить число т, т.е. .
^ Задачка 1. Множества Лекция 1 8. Сколько разных двоичных чисел длиной 6 можно записать при помощи цифр 0 и 1?
Решение. Размещаем две числа (0, 1) на 6 мест, т.е. на каждом из 6 мест (т = 6) может быть одна из 2-ух двоичных цифр. Всего 1. Множества Лекция 1 таких вариантов будет двоичных чисел: на каждом из 6 мест по два варианта цифр.
^ Задачка 9. Сколько проводится матчей в Чемпионате РФ по футболу в премьер-лиге за сезон?
Решение. Так 1. Множества Лекция 1 как один матч проводится меж 2-мя командами, каждый матч выделяет упорядоченное подмножество (потому что одна команда играет дома, 2-ая – на выезде) из 2-ух частей. По формуле размещений
1.8. Подстановки
Взаимнооднозначное отображение огромного количества 1. Множества Лекция 1 на себя именуется подстановкой степени п.
Если прототипы (аргументы) размещены в порядке возрастания (при ), то запись подстановки именуют канонической.
Подстановку вида именуют тождественной, потому что .
Произведение отображений также является подстановкой и именуется произведением подстановок и 1. Множества Лекция 1 и записывается .
Задачка 10. Даны две подстановки: . Привести подстановки к канонической записи и отыскать их произведение.
Решение. 2-ая постановка записана в каноническом виде, 1-ая – нет. Потому в верхней строке запишем 1. Множества Лекция 1 числа от 1 до 5, а в нижней Т. о., Найдём . Поначалу производится 1-ая подстановка , а потом 2-ая , т.е. . Потому можно сходу записывать в матрицу: . Аналогично найдём другие образы: . Сейчас найдём а т.е 1. Множества Лекция 1.
В конечном итоге получим .
Натуральной степенью подстановки именуется подстановка , т.е. произведение п функций, любая из которых есть .
Задачка 11. Дана подстановка Отыскать её степени.
Решение.
Тогда разумеется, что и т.д.
Порядком подстановки именуется 1. Множества Лекция 1 меньшее натуральное число , такое, что .
Инверсией подстановки именуется переставление (рокировка) 2-ух примыкающих значений в нижнем ряду канонической записи.
Если п – число инверсий, приводящих подстановку к единичной, а функция такая, что 1. Множества Лекция 1 , то подстановка именуется чётной, если , то подстановка именуется нечётной.
Задачка 12. Отыскать число инверсий и чётность подстановки
^ Решение. Имеем
Тогда , потому т.е. подстановка чётная.
^ Одна инверсия меняет чётность подстановки и символ 1. Множества Лекция 1 функции .
Неважно какая перемена и местами именуется транспозицией.
Число чётных и нечётных подстановок п-й степени идиентично и равно .
Выражение именуется симметричным по своим переменным, если неважно какая подстановка (где - огромное количество подстановок п 1. Множества Лекция 1-й степени) оставляет значение F постоянным: .
Задачка 13. 50 наилучших студентов института одарили за успехи поездкой в Великобританию и Германию. Из их 5 не обладали ни одним разговорным зарубежным языком, 34 знали британский язык и 27 – германский. Сколько 1. Множества Лекция 1 студентов обладало 2-мя разговорными зарубежными языками?
Решение. Введём обозначения множеств:
^ Е – огромное количество студентов, не обладающих ни одним зарубежным языком;
А – огромное количество всех студентов, ;

В – огромное количество студентов, обладающих 1. Множества Лекция 1 английским языком, ;
С – огромное количество студентов, обладающих германским языком, ;
D – огромное количество студентов, обладающих английским и германским языками, .
^ Представим огромного количества графически при помощи кругов Эйлера (рис. 1.5).
Метод 1. Составим уравнение: , откуда .

Метод 2. Найдём 1. Множества Лекция 1 из уравнения либо , .

Как следует, 16 студентов свободно общались на 2-ух зарубежных языках.
Задачка 14. Каждый студент группы программистов занимается в свободное время в НСО либо спортом. Сколько студентов в группе, если 23 увлекаются 1. Множества Лекция 1 спортом, 12 занимаются в НСО, а 7 совмещают занятия в НСО и увлечения спортом?
Решение. Изобразим огромного количества кругами Эйлера, обозначив огромного количества «спортсменов» - А и «исследователей» - В (рис. 1.6). Тогда
Задачка 15. Из 35 студентов 1. Множества Лекция 1, побывавших на каникулах в Москве, все, не считая двоих, делились впечатлениями. О посещении Огромного театра с экстазом вспоминали 12 человек, Кремля – 14, а 16 – о концерте, по три студента запомнили посещение театра и Кремля, также театра 1. Множества Лекция 1 и концерта, а четыре – концерта и пребывания в Кремле. Сколько студентов сохранили мемуары сразу о театре, концерте и Кремле?
Решение. Введём обозначения: А – огромное количество студентов, вспоминающих о театре, ; В – о Кремле 1. Множества Лекция 1, ; С – о концерте, ; D – огромное количество всех студентов, побывавших в поездке (рис. 1.6). , тогда , .
^ Проверочная работа по теме Подстановки


В – 1
Найдите и порядок каждой из подстановок:



В – 2
^ Найдите и порядок каждой из подстановок 1. Множества Лекция 1:



В – 3
^ Найдите и порядок каждой из подстановок:



В – 4
^ Найдите и порядок каждой из подстановок:



В – 5
^ Найдите и порядок каждой из подстановок:



В – 6
^ Найдите и порядок каждой из подстановок:


Тема 2. Графы
Лекция 1.
Цель – познакомить студентов 1. Множества Лекция 1 с основными понятиями и определениями графа и его частей.
^ 2.1. Главные понятия и определения графа и его частей
Графом именуется пара 2-ух конечных множеств: огромное количество точек и огромное количество линий, соединяющих некие пары 1. Множества Лекция 1 точек.
^ Точки именуются верхушками, либо узлами, графа, полосы – рёбрами графа.
Если ребро графа G соединяет две его верхушки V и W, (т.е. ), то молвят, что это ребро им инцидентно. Две верхушки 1. Множества Лекция 1 графа именуются смежными, если существует инцидентное им ребро: на рис. 2.1, а смежными являются верхушки А и В, А и С. Если граф G имеет ребро , у которого начало и конец совпадают, то 1. Множества Лекция 1 это ребро именуется петлёй. На рис. 2.1, б петля - . Два ребра именуются смежными, если они имеют общую верхушку.
Рёбра, которые начинаются в одной и той же верхушке, завершаются также в одной и той 1. Множества Лекция 1 же верхушке, именуются кратными, либо параллельными. Количество схожих пар вида именуется кратностью ребра . Число рёбер, инцидентных верхушке А, именуется степенью этой верхушки и обозначается (от англ. degree – степень).
Верхушка 1. Множества Лекция 1 графа, имеющая степень, равную нулю, именуется изолированной. Граф, состоящий из изолированных вершин, именуется нуль-графом. Верхушка графа, имеющая степень, равную 1, именуется висящей.
Аксиома 2.1. В графе сумма степеней всех его вершин – число чётное 1. Множества Лекция 1, равное удвоенному числу рёбер графа:
,
где - число вершин; - число рёбер графа.
Верхушка именуется чётной (нечётной), если её степень – чётное (нечётное) число.
^ Аксиома 2.2. Число нечётных вершин хоть какого графа – чётно.
Следствие. Нереально начертить граф с 1. Множества Лекция 1 нечётным числом нечётных вершин.

Граф G именуется полным, если любые две его разные верхушки соединены одним и только одним ребром.
Дополнением графа именуется граф с теми же верхушками V, что 1. Множества Лекция 1 и граф G, и имеющий те и только те рёбра , которые нужно добавить к графу G, чтоб он стал полным.
Если все пары во огромном количестве Ч являются упорядоченными, т.е. кортежами длины 2, то граф 1. Множества Лекция 1 именуется нацеленным, орграфом, либо направленным. Началом ребра именуется верхушка, обозначенная в кортеже первой, концом – 2-ая верхушка этой пары (графически она указана стрелкой). Рёбра нацеленного графа имеют определённые фиксированные начало и конец и 1. Множества Лекция 1 именуются дугами.
^ Степенью входа (выхода) верхушки нацеленного графа именуется число рёбер, для которых эта верхушка является концом (началом).
Дуги орграфа именуются кратными, если они имеют однообразные исходные и конечные 1. Множества Лекция 1 верхушки, т.е. схожие направления.
Последовательность попарно смежных вершин неориентированного графа, т.е. последовательность рёбер неориентированного графа, в какой 2-ая верхушка предшествующего ребра совпадает с первой верхушкой последующего, именуется маршрутом. Число рёбер маршрута именуется 1. Множества Лекция 1 длиной маршрута. Если исходная верхушка маршрута совпадает с конечной, то таковой маршрут именуется замкнутым либо циклом.
Расстоянием меж 2-мя верхушками именуется малая длина из всех вероятных маршрутов меж этими верхушками при условии, что 1. Множества Лекция 1 существует хотя бы один таковой маршрут. Обозначается как (от лат. distantio – расстояние) .
^ Если хоть какое ребро в маршруте встречается только один раз, то маршрут именуется цепью.
В орграфе маршрут является нацеленным и 1. Множества Лекция 1 именуется оковём.
Путь – упорядоченная последовательность рёбер нацеленного графа, в какой конец предшествующего ребра совпадает с началом последующего и все рёбра единственны. Цикл в орграфе – путь, у которого совпадают начало и конец 1. Множества Лекция 1.
Цепь, путь и цикл в графе именуются ординарными, если они проходят через всякую из вершин менее 1-го раза. Неориентированный граф именуется связным, если меж хоть какими 2-мя его верхушками есть маршрут. Так, графы 1. Множества Лекция 1 G1 и G3 (рис. 2.1, а, в) являются связными, а граф G2 (рис. 2.1, б) – бессвязным.
Две верхушки именуются связными, если существует маршрут меж ними. Связность меж верхушками является отношением эквивалентности.
Все подграфы 1. Множества Лекция 1 Vi (классы эквивалентности) графа G именуют связными компонентами, либо компонентами связности.
Направленный цикл в конечном связном графе, проходящий через каждое ребро по одному разу в 2-ух направлениях, именуют методом обхода всего графа 1. Множества Лекция 1 и употребляют в решении многих прикладных задач.
Аксиома 2.3. Для того чтоб связный граф G являлся обычным циклом, нужно и довольно, чтоб любая его верхушка имела степень, равную 2.
Ребро связного графа G именуется мостом 1. Множества Лекция 1, если после его удаления G станет бессвязным и распадётся на два связных графа и .
Аксиома 2.4. Ребро графа является мостом и тогда только тогда, когда не принадлежит ни одному циклу.
Графы 1. Множества Лекция 1 и именуются изоморфными, если существует взаимно-однозначное соответствие меж их рёбрами и верхушками, причём надлежащие рёбра соединяют надлежащие верхушки. Другими словами, графы и именуются изоморфными, если и существует подстановка , такая, что , а 1. Множества Лекция 1 .
Граф G именуется планарным (плоским), если существует изоморфный ему граф , в изображении которого на плоскости рёбра пересекаются исключительно в верхушках. Областью именуется подмножество плоскости, пересекающееся с планарным графом только по некому обычному циклу 1. Множества Лекция 1 графа, являющемуся границей области.
Аксиома 2.5 (Эйлера). Связный тонкий граф с п верхушками и т рёбрами разбивает плоскость на r областей (включая внешнюю), причём . ^ Задачка 16 «О трёх колодцах». Проложить дорожки от трёх 1. Множества Лекция 1 домов к каждому из трёх колодцев так, чтоб никакие две дорожки не пересекались.
Решение: Представим, что эти 9 тропинок можно проложить. Обозначим домики точками А, В, С, колодцы - точками К1, К2, К3. Каждую точку 1. Множества Лекция 1-дом соединим с каждой точкой-колодцем. Вышли ребра (графа) в количестве 9 штук, которые попарно не пересекаются. Такие ребра образуют на рассматриваемой плоскости задачки многоугольник, поделенный на наименьшие многоугольники. Для такового 1. Множества Лекция 1 разбиения должно производиться известное соотношение Эйлера  п - т + r = 2, при этом n = 6 и m = 9. Выходит, r = 5. Любая из 5 граней имеет по последней мере четыре ребра, потому что, по условию задачки Эйлера, ни одна из 1. Множества Лекция 1 дорожек не должна впрямую соединять два колодца либо два дома. Потому что хоть какое ребро лежит ровно в 2-х гранях, то количество ребер графа должно быть не меньше 5*4/2 = 10. Это противоречит условию начальной задачки 1. Множества Лекция 1, по которому их число равно девять! Приобретенное противоречие обосновывает, что ответ в задачке о 3х колодцах Эйлера отрицателен.

Граф именуется двудольным, если его верхушки разбиты на два непересекающихся подмножества: , а рёбра связывают 1. Множества Лекция 1 верхушки только из различных классов (не непременно все пары). Если любая верхушка огромного количества V1 связана ребром с каждой верхушкой огромного количества V2, то двудольный граф именуется полным двудольным 1. Множества Лекция 1 и обозначается , где .
Эйлеровым оковём (циклом) графа именуется путь (цикл), который содержит все рёбра графа только один раз. Граф, владеющий эйлеровым циклом, именуется эйлеровым. Тонкий эйлеров граф также именуют уникурсальным.
Аксиома 2.6. Граф G является 1. Множества Лекция 1 эйлеровым и тогда только тогда, когда G – связный граф, имеющий все чётные верхушки.
Гамильтоновым оковём (циклом) графа G именуется путь (цикл), проходящий через каждую его верхушку только один раз. Граф, содержащий гамильтонов цикл 1. Множества Лекция 1, именуется гамильтоновым.
^ Задачка 17 «О кёнигсбергских мостах» (Эйлера). Нужно обойти все 7 мостов так, чтоб на каждом побывать только один раз и возвратиться к началу пути (рис. 2.3).

















2.2. Операции над графами
Объединением графов 1. Множества Лекция 1 и именуется граф , огромное количество вершин которого , а огромное количество рёбер .
Скрещением графов и именуется граф , для которого - огромное количество рёбер, а - огромное количество вершин.
Подграфом графа именуется граф , все верхушки и рёбра которого 1. Множества Лекция 1 являются подмножествами огромного количества вершин и рёбер графа G.
Кольцевой суммой 2-ух графов именуется граф , порождённый обилием вершин и обилием рёбер , т.е. обилием рёбер, содержащихся или в , или в , но не в 1. Множества Лекция 1 .
Компонентой связности неориентированного графа именуется его подграф с обилием вершин и обилием рёбер , инцидентных только верхушкам из огромного количества , причём ни одна верхушка из не смежна с верхушками из огромного количества .
2.3. Деревья 1. Множества Лекция 1. Лес. Бинарные деревья
Деревом именуют конечный связный граф с выделенной верхушкой (корнем), не имеющий циклов (рис. 2.4).





















Для каждой пары вершин дерева – узлов – существует единственный маршрут, потому верхушки комфортно систематизировать по 1. Множества Лекция 1 степени удалённости от корневой верхушки. Расстояние до корневой верхушки именуется ярусом s верхушки, .
Аксиома 2.7. Граф является деревом и тогда только тогда, когда производится хотя бы одно из критерий:
^ граф связен и не содержит 1. Множества Лекция 1 циклов;
граф не содержит циклов и имеет п – 1 ребро;

граф связен и имеет п – 1 ребро;
граф не содержит циклов, но добавление ребра меж несмежными верхушками приводит к возникновению 1-го и только 1. Множества Лекция 1 1-го простого цикла;
граф связный, но утрачивает это свойство после удаления хоть какого ребра;

в графе всякая пара вершин соединена цепью, и только одной.

Висящие верхушки, кроме корневой, именуются листьями.

Упорядоченное объединение 1. Множества Лекция 1 деревьев представляет собой бессвязный граф, именуемый лесом. Остовом связного графа G именуется хоть какой его подграф, содержащий все верхушки графа G и являющийся деревом.
Кодеревом остова Т графа G именуется дополнение Т до 1. Множества Лекция 1 G, т.е. таковой его подграф, который содержит все его верхушки и только те его рёбра, которые не входят в Т.
При описании деревьев принято использовать определения: отец, отпрыск, предок, потомок.
Любая верхушка 1. Множества Лекция 1 дерева именуется узлом, причём каждый узел является корнем дерева, состоящего из поддеревьев. Узел k-го яруса именуется папой узла (k + 1)–го яруса, если они смежны. Узел (k + 1)–го яруса именуется отпрыском узла 1. Множества Лекция 1 k-го яруса. Два узла, имеющие 1-го отца, именуются братьями (рис. 2.5).
^ Упорядоченным деревом именуется дерево, в каком поддеревья каждого узла образуют упорядоченное подмножество. Для упорядоченных деревьев принята терминология: старший и 1. Множества Лекция 1 младший отпрыск для обозначения соответственно первого и последнего отпрыской некого узла.
Деревья, в каких каждый узел или является листом, или образует два поддерева: левое и правое, именуются бинарными деревьями и применяются при делении 1. Множества Лекция 1 огромного количества на два взаимоисключающих подмножества по какому-то признаку (дихотомическое деление). Строго бинарным деревом именуется таковой граф (рис. 2.6), у которого каждый узел, не являющийся листом, содержит два и только два 1. Множества Лекция 1 поддерева – левое и правое.
Бинарное дерево уровня п именуется полным, если каждый его узел уровня п является листом, а каждый узел уровня меньше, чем п, имеет непустое левое и правое поддеревья.
Цикломатическое число 1. Множества Лекция 1 графа. Цикломатическим числом неориентированного графа G именуется число , где - число его рёбер; - число связных компонент графа; - число вершин.
2.4. Методы задания графа. Изоморфные графы
^ Геометрическое представление плоского графа именуется его реализацией.
При переходе от алгебраического метода 1. Множества Лекция 1 (метода задания графа дугами оковём указания вершин, которым они инцидентны) к геометрическому одному и тому же графу могут соответствовать разные изображения – изоморфные графы.
Граф можно задавать таблицей, состоящей из п строк 1. Множества Лекция 1 (верхушки) и т столбцов (рёбра).
Одним из самых распространённых методов задания графа является матричный метод.
Матрицей инцидентности именуется таблица В, состоящая из п строк (верхушки) и т столбцов (рёбра), в какой: , если верхушка инцидентна ребру ; , если верхушка не инцидентна ребру ; , если верхушка является началом дуги ; , если верхушка не инцидентна дуге ; , если верхушка является концом дуги .
Матрицей смежности графа 1. Множества Лекция 1 без кратных рёбер именуется квадратная матрица А порядка п, в какой:
, если ; , если .
При восстановлении графа по его матрице инцидентности можно получить граф только с точностью до изоморфизма.
Задачка 18. Пусть 1. Множества Лекция 1 граф G задан матрицей смежности А. Выстроить диаграмму этого графа, если Указание. Так как матрица А несимметрична (к примеру ), то она может задавать только направленный граф.




Задачка 19. Пусть граф G задан матрицей смежности А 1. Множества Лекция 1. Выстроить диаграмму этого графа, если





Решение. Диаграмму графа, имеющего 6 вершин, можно представить последующим образом (рис. 2.7).













1-ispolzovanie-eksperimentalnogo-metoda-dlya-izucheniya-psihopatologicheskih-yavlenij-istoriya-razvitiya-estestvennih-nauk-svidetelstvuet-o-tom-chto-razvitie-kazhdo.html
1-istoriya-razvitiya-i-sovremennie-vozmozhnosti-plastikovih-bankovskih-kartochek.html
1-istoriya-voprosa.html