Kihagyás

8. előadás

\[ \binom n0-\binom n1+\binom n2-\cdots=0 \]
\[ \sum_{k=0}^n (-1)^k \binom nk \]

Ha |A| és |B| diszjunkt \(\Rightarrow |A \cup B| = |A| + |B|\)

Általánosságban: \(|A \cup B| = |A| + |B| - |A \cap B|\)

Szita formula (inclusion exclusion principle):

\[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C| \]

1. TÉTEL - Szitaformula

Tétel

\(A_1, A_2, \dots, A_n\) tetszőleges céges halmaz, akkor:

\(|A_1 \cup A_2 \cup \; \cdots \; \cup A_n| = |A_1| + |A_2| + |A_3| + \cdots + |A_n| - |A_1 \cap A_2| - |A_1 \cap A_3| - \cdots - |A_n \cap A_n|\) Nem tudom hogy van tovább, legörgetett lmao

Példa

Például: Hány olyan szám van 1000-ig (1..1000), mely se 2-vel, se 3-mal, se 5-tel nem osztható

Hány olyan van, amely valemelyikkel osztható?

\[ A: \text{páros} \\ B: 3\text{-mal osztható} \\ C: \text{5-tel osztható} \]
\[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C| \]
\[ \frac{1000}{2} + \left\lfloor\frac{1000}{3}\right\rfloor + \frac{1000}{5} - \left\lfloor\frac{1000}{6}\right\rfloor - \frac{1000}{10} - \left\lfloor\frac{1000}{15}\right\rfloor + \left\lfloor\frac{1000}{30}\right\rfloor = 734 \]

Rossz esetek: \(734\)

Jó esetek: \(1000 - 734 = 266\)

Gráfok

Irányított, irányítatlan

Irányítótt/irányítatlan gráfok

Relációk: reflexív, tranzitív stb.

Gráfok: Mi a legrövidebb út? Legdrágább út? stb.

Irányítatlan gráf

\((V, E, \varphi)\), ahol

\(V\): nemüres halmaz, a csúcsok halmaza

\(E\): Élek halmaza, \(E \cap V = \varnothing\)

\(\varphi\): \(E \to\) {\(V\)-beli rendezetlen párok}, az úgy nevezett illeszkedési függvény

Például

Gráf példa

\(V = \{a, b, c, d\} \quad E = \{x, y, z, w\}\)

\(\varphi:\)

  • \(x \mapsto \{a,c\}\)
  • \(y \mapsto \{a,c\}\)
  • \(z \mapsto \{b,c\}\)
  • \(w \mapsto \{d\}\)

DEF

Ha \(v \in V\) és \(e \in E\) esetén \(v \in \varphi(e)\), akkor a

v az egyik végpontjaú

v illeszkedik e-re

e illeszkedik v-re

Definíció

\(v_1, \; v_2, \in V \;\) szomszédos, ha \(v_1 \ne v_2\) és \(\exists e \in E: \varphi\)

(Sorry, befejezetlen, nem tudok ilyen gyorsan írni)

Definíció: Szomszédos élek

Két él szomszédos, ha van közös végpontjuk (\(e_1 \ne e_2\))

Definíció: hurokél

Egy él hurokél, ha a két végpontja megegyezik.

Definíció: párhuzamos

\(e_1 \neq e_2\) PÁRHUZAMOS, ha \(\varphi(e_1) = \varphi(e_2)\)

Definíció: Egyszerű gráf

\(G\) gráf egyszerű, ha se hurokél, se párhuzamos él nincs.

Definíció: Véges gráf

\(G\) véges, ha V és E is véges.

Definíció: Izolált él

Egy \(v \in V\) izolált csúcs, ha nem illeszkedik rá él.

Definíció: Fokszám

Egy \(v \in V\) fokszáma \(d(v)\): a rá illeszkedő élek száma, de a hurokéleket kétszer számolva

Állítás: fokszámok és élek számának kapcsolata

Egy véges gráfba:

\(2|E| = \sum_{v \in V}d(v)\)

Tehát a fokszámok összege = 2-szer az élek száma

Séta (walk)

Egy G gráf v és w csúcsa közötti n hosszú séta:

\(v_0,e_1,v_1,e_2,v_2,\cdots,v_{n-1},e_n,v_n\) ahol \(v_0 = v\), \(v_n = w\), és \(\forall j = 1,2,\ldots,n: \varphi(e_j)=\{v_{j-i},v_j\}\)

Példa gráf

4 hosszú séta például: \(AeBgBgBhC\)

Vonal (trail)

Egy séta vonal, ha minden éle különböző

Kör

Egy legalább 1 hosszú zárt vonalat köznek nevezkünk, ha a kezdő- és végpont azonosságától eltekintve minden csúcsa különböző

Út

???????????

Állítás: Ha két pontot séta köt össze, akkor van köztük út is.

Következmény: Az a reláció \(V\)-n: \(\{(v_1, v_2) | \exists \text{ út } v_1\text{-ből } v_2\text{-be}\}\) ekvivalenciareláció

  • Reflexív: \(v\)-ből \(v\)-be van 0 hosszú út
  • Szimmetrikus: \(v\)-ből \(w\)-be van út, akkor van \(w\)-ből \(v\)-be is
  • Tranzitív: \(v_1\)-ből van út \(v_2\)-be, és \(v_2\)-ből van út \(v_3\)-ba, akkor van séta \(v_1\) és \(v_3\) között, tehát út is van

Az így kapott osztályok és az osztályokon belül futó élek: komponensek

Összefüggő gráf

Egy G gráf összefüggő (connected), ha \(\forall v_1, v_2 \in V \exists \text{út }v_1\text{-ből }v_2\text{-be}\)