5: Принцип включення та виключення
- Page ID
- 64043
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Одним з наших найперших принципів підрахунку був принцип суми, який говорить про те, що розмір об'єднання нероз'єднаних множин - це сума їх розмірів. Обчислення розмірів перекриваються множин вимагає, цілком природно, інформації про те, як вони перекриваються. Врахування такої інформації дозволить нам розробити потужне розширення принципу суми, відомого як «принцип включення та виключення».
- 5.1: Розмір об'єднання множин
- Одним з наших найперших принципів підрахунку був принцип суми, який говорить про те, що розмір об'єднання нероз'єднаних множин - це сума їх розмірів. Обчислення розмірів перекриваються множин вимагає, цілком природно, інформації про те, як вони перекриваються. Врахування такої інформації дозволить нам розробити потужне розширення принципу суми, відомого як «принцип включення та виключення».
- 5.2: Заявки на включення та виключення
- Ми визначили граф, який складається з безлічі V елементів, що називаються вершинами, та набору E елементів, що називаються ребрами, таким чином, що кожне ребро з'єднує дві вершини. Забарвлення графа елементами множини C (кольорів) - це призначення елемента C кожній вершині графа; тобто функція з набору вершин V графа до C. Забарвлення називається правильним, якщо для кожного ребра, що з'єднує дві різні вершини, дві вершини, які вона об'єднує, мають різну кольори.
- 5.3: Видалення-скорочення та хроматичний поліном
- У розділі 2 ми ввели повторення видалення-скорочення для підрахунку охоплюючих дерев графа. У цьому розділі ми будемо використовувати повторення видалення-скорочення, щоб зменшити обчислення хроматичного полінома графа (на прикладі рис. 5.3.1) до обчислення хроматичних поліномів, які можна легко обчислити.
- 5.4: Принцип включення і виключення (вправи)
- Цей розділ містить додаткові проблеми, пов'язані з матеріалами, розглянутими в розділі 5.
Мініатюра: включення — виключення, проілюстроване діаграмою Венна для трьох наборів. (CC BY-SA 3.0; Вікіпедія).