משתמש:בר/בדידה

הכלה והדחה

$|A\cup B|=|A|+|B|-|A\cap B|$

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

$\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}|A_{i}|-\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|+\sum _{1\leqslant i<j<k\leqslant n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n+1}\left|A_{1}\cap \cdots \cap A_{n}\right|$

גרפים

גרף פשוט גרף לא מכוון ללא לולאות וללא קשתות מקבילות.

גרף רגולרי גרף שבו דרגת כל הקודקודים שווה, כלומר מספר הקשתות היוצאות מכל קודקוד קבוע.

גרף דו-צדדי גרף שבו ניתן לחלק את הקודקודים לשתי קבוצות זרות, כך שלא קיימת קשת בין שני קודקודים השייכים לאותה הקבוצה.

גרף קשיר גרף שבו קיים מסלול בין כל שני קודקודים.

רכיב קשירות של גרף הוא תת-גרף קשיר מקסימלי, כלומר, קבוצת קודקודים שיש מסלול בין כל שני קודקודים שלה, והכוללת עם כל קודקוד גם את השכנים שלו; יחד עם הקשתות המחברות את הקודקודים האלה. כל גרף מתפרק באופן יחיד לרכיבי קשירות.

משפט הדרגות

גרפים $G$ ו-$H$ הם איזומורפיים אם קיימת פונקציה $f:V\left(G\right)\rightarrow V\left(H\right)$ חד-חד-ערכית ועל, כך שעבור כל $v,w\in V\left(G\right)$, מספר הקשתות המקשרות בין $v$ ו-$w$ זהה למספר הקשתות המקשרות בין $f\left(v\right)$ ו-$f\left(w\right)$.