Kihagyás

Definíciók

Halmazok

Valódi részhalmaz: \(A \neq B \land A \subseteq B\)

Diszjunkt: \(A \cap B = \emptyset\)

Szimmetrikus differencia: \(A \triangle B = (A \cup B) \setminus (A \cap B)\) (Minden kivéve a metszetek)

Halmazműveletek tulajdonságai

  • Kommutatív (felcserélhető)
  • Asszociatív (átzárójelezhető)
  • Disztributív
    • \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
  • Komplementer
    • \(A \cup \overline{A} = U\)
    • \(A \cap \overline{A} = \emptyset\)
    • \(\overline{\overline{A}} = A\)
  • Különbség
    • \(A \setminus B = A \cap \overline{B}\)

Relációk

Tulajdonságok

  • Reflexív: \(\forall a : (a,a) \in R\)
  • Irreflexív: \(\forall a : (a,a) \notin R\)
  • Szimmetrikus: \(\forall (a,b) \in R \Rightarrow (b,a) \in R\)
  • Antiszimmetrikus: \(\forall (a,b) \in R \land (b,a) \in R \Rightarrow a = b\)
  • Tranzitív: \(\forall (a,b) \in R \land (b,c) \in R \Rightarrow (a,c) \in R\)

Összefüggések

Ha \(R\) irreflexív és szimmetrikus, akkor nem lehet tranzitív.

Ekvivalenciareláció: reflexív, szimmetrikus, tranzitív

Részbenrendezés: reflexív, antiszimmetrikus, tranzitív

Dichotóm: \(\forall x,y \in A: (x,y) \in R \lor (y,x) \in R\)

Trichotóm:

  1. \(x = y\)
  2. \((x,y) \in R\)
  3. \((y,x) \in R\)

közül pontosan egy teljesül

Függvények

Ha az \(A\) és \(B\) nemüres halmazok közötti hozzárendelés (reláció) egyértelmű, akkor függvényről beszélünk.

Injektív: \(\forall x,y \in A: f(x) = f(y) \Rightarrow x = y\)

Magyarul a hozzárendelés kölcsönösen egyértelmű.

Szürjektív: Az \(f: A \rightarrow B\) függvény szürjektív, ha az egész B halmaz előáll képként. A \(B\) minden eleme hozzá van rendelve az \(A\) valamelyik eleméhez.

Bijektív: Injektív és szürjektív.

Kompozíció: \(f \circ g = f(g(x))\)

Komplex számok

\(i^2 = -1\)

Nevezetes szögek

sin

  • \(\sin 0\pi = \sin 0\degree = 0\)
  • \(\sin \frac{\pi}{6} = \sin 30\degree = \frac{1}{2}\)
  • \(\sin \frac{\pi}{4} = \sin 45\degree = \frac{\sqrt{2}}{2}\)
  • \(\sin \frac{\pi}{3} = \sin 60\degree = \frac{\sqrt{3}}{2}\)
  • \(\sin \frac{\pi}{2} = \sin 90\degree = 1\)
  • \(\sin \pi = \sin 180\degree = 0\)

cos

  • \(\cos 0\pi = \cos 0\degree = 1\)
  • \(\cos \frac{\pi}{6} = \cos 30\degree = \frac{\sqrt{3}}{2}\)
  • \(\cos \frac{\pi}{4} = \cos 45\degree = \frac{\sqrt{2}}{2}\)
  • \(\cos \frac{\pi}{3} = \cos 60\degree = \frac{1}{2}\)
  • \(\cos \frac{\pi}{2} = \cos 90\degree = 0\)
  • \(\cos \pi = \cos 180\degree = -1\)

Algebrai alak

\(z = a + bi\)

Hossz:

\(|z| = \sqrt{a^2+b^2}\)

Konjugált:

\(\overline{z} = a - bi\)

Trigonometrikus alak

\(z = r(\cos \alpha + i\sin \alpha)\)

\(r = |z| = \sqrt{a^2+b^2}\) - A sugár a komplex szám hossza

\(\cos \alpha\) = \(\frac{a}{r}\) - A komplex szám valós része

Műveletek

Szorzás:

\[ z_1 \cdot z_2 = r_1 \cdot r_2 (\cos(\alpha_1 + \alpha_2) + i\sin(\alpha_1 + \alpha_2)) \]

Osztás:

\[ \frac{z_1}{z_2} = \frac{r_1}{r_2} (\cos(\alpha_1 - \alpha_2) + i\sin(\alpha_1 - \alpha_2)) \]

Hatványozás:

\[ z^n = r^n (\cos(n \cdot \alpha) + i\sin(n \cdot \alpha)) \]

Gyökvonás:

\[ \sqrt[n]{z} = \sqrt[n]{r} (\cos(\frac{\alpha + 2k\pi}{n}) + i\sin(\frac{\alpha + 2k\pi}{n})) \]

Kombinatorika

See here

Binomiális tétel

\[ (a+b)^n = \sum_{k=0}^n \binom{n}{k} a^kb^{n-k} \]

Szita formula

\[ |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| \]

Gráfok

Mi a gráf?

Csúcsok és élek halmaza.

  • \(V\) - csúcsok halmaza
  • \(E\) - élek halmaza

Fogalmak

  • Irányítatlan gráf: Az élek nem rendelkeznek iránnyal (halmazok)
  • Irányított gráf: Az élek rendelkeznek iránnyal (rendezett párok)
  • Hurokél: Egy csúcs magába vezető éle
  • Párhuzamos él: Két csúcsot több él köt össze
  • Egyszerű gráf: Nincs benne hurokél és párhuzamos él
  • Összetett gráf: Nem egyszerű
  • Izolált csúcs: Nincs belőle él
  • Összefüggő gráf: Bármely két csúcs között vezet séta
  • Körmentes gráf:: Minden csúcs között kizárólag egy út vezet
  • Fa: kör nélküli, összefüggő egyszerű gráf
  • Teljes gráf: Minden csúcspár között van él
  • Fokszám: \(V\)-re illeszkedő élek száma
    • Jele: \(d(v)\)
    • Irányított gráf esetén külön kell számolni a be- és kifokszámot
    • Mindig páros

A fokszámok összege megegyezik az élek számának kétszeresével.

Teljes gráf éleinek száma

\[ \frac{n \cdot (n-1)}{2} \]

Gráf bejárás

  • Séta: nincs feltétel
  • Vonal: séta, amelyben nincs él ismétlődés
  • Út: vonal, amelyben nincs cúcs ismétlődés
  • Kör: vonal, amely ugyanoda ér vissza (\(v_0 = v_n\))

Izomorfia

Két gráf izomorf, ha az egyiket a másikba lehet ábrázolni úgy, hogy a csúcsok és élek közötti kapcsolatok megmaradnak.

Pontosabban, ha a két gráf csúcsai között van olyan leképzeés ami az élek illeszkedését megtartja.

Izomorfia

Két gráf melyek izomorfak egymással

Fák

Gráf amely körmentes és összefüggő.

Tulajdonságok

  • \(|E| = |V| - 1\)
  • Bármely két csúcs között pontosan egy út létezik
  • Minden fában van min. 2 elsőfokú csúcs
  • \(f_1 \geq c + 2\)
    • \(f_1\): elsőfokú csúcsok száma
    • \(c\): legalább harmadfokú csúcsok száma

Euler vonal

Olyan vonal amelyben a gráf minden éle szerepel és minden él pontosan egyszer szerepel.

Egy összefüggő véges gráfban...

  • pontosan akkor van zárt Euler-vonal/Euler kör ha minden csúcs fokszáma páros
  • pontosan akkor van nyílt Euler-vonal ha pontosan 0 vagy 2 páratlan fokszámú csúcs van

Hamilton-út és Hamilton-kör

  • Hamilton-út: olyan út amelyen minden csúcs pontosan egyszer szerepel
  • Hamilton-kör: olyan kör amelyen minden csúcs pontosan egyszer szerepel

Dirac-tétel

Ha egy n csúcsú egyszerű gráfban minden csúcs fokszáma legalább \(\frac{n}{2}\) akkor van benne Hamilton-kör. (Elégséges, de nem szükséges feltétel)

Szükséges feltétel

Egy gráfban csak akkor lehet Hamilton-kör, ha \(k\) db csúcs kivételével, a kör maximum \(k\) részre esik szét. (Szükséges, de nem elégséges feltétel)

Hasonlóan, akkor van benne Hamilton-út, ha \(k\) db csúcs kivételével, a kör maximum \(k+1\) részre esik szét.

Tételek

Tétel: \(A \cap B = B \cap A\)

Bizonyítás

  • Igazságtábla

Tétel: A kompozíció asszociatív \(\forall R, T, S\) relációra

\[ (R\circ S)\circ T = R\circ (S\circ T) \]

Bizonyítás

\[ (x,w)\in (R\circ S)\circ T \underset{?}{\Longleftrightarrow} (x,w) \in R\circ(S\circ T) \]

Bal oldal

\[ (x,w)\in (R\circ S)\circ T\\ \Updownarrow \\ \exists y : (x,y) \in T \land (y,w) \in R \circ S\\ \Updownarrow \\ \exists y \exists z : (x,y) \in T \land (y,z) \in S \land (z,w) \in R \]

Jobb oldal

\[ (x,w) \in R\circ(S\circ T) \\ \Updownarrow \\ \exists z : (x,z) \in S \circ T \land (z,w) \in R \\ \Updownarrow \\ \exists y \exists z : (x,y) \in T \land (y,z) \in S \land (z,w) \in R \]

Tétel: Kompozíció inverzének disztributivitása

\[ (R\circ S)^{-1} = S^{-1} \circ R^{-1} \]

Adott S és R reláció, bizonyítsuk be, hogy a komponáltjuk inverze a sorrend felcserélésével felbontható

Bizonyítás

\[\begin{array}{ccl} (z,x)\in (R\circ S)^{-1} &\quad& \\ \Updownarrow &\leftarrow& \text{1. Inverz definíciója}\\ (x,z) \in R\circ S \\ \Updownarrow &\leftarrow& \text{2. Kompozíció definíciója}\\ \exists y:(x,y) \in S\quad\land\quad(y,z) \in R \\ \Updownarrow &\leftarrow& \text{3. Inverz definíciója}\\ \exists y:(y,x)\in S^{-1}\quad\land\quad(z,y) \in R^{-1} \\ \Updownarrow &\leftarrow& \text{4. Kompozíció definíciója}\\ (z,x) \in S^{-1} \circ R^{-1} \\ \end{array}\]

Tétel: Összetett függvényekkel kapcsolatos tételek

  • \(\text{f injektív és g injektív} \Rightarrow f \circ g \text{ Injektív}\)

  • \(f: B \rightarrow C \text{ Szürjektív és } g:A \rightarrow B \text{ Szürjektív} \Rightarrow f \circ g: A \rightarrow C \text{ Szürjektív}\)

  • \(f: B \rightarrow C \text{ Bijektív és } g: A \rightarrow B \text{ Bijektív } \Rightarrow f \circ g: A \rightarrow C \text{ Bijektív }\)

Bizonyítás

Injektív

\[ f(g(x)) = f(g(t)) \xRightarrow{\text{f injektív}} g(x) = g(t) \xRightarrow{\text{ g injektív }} x = t \checkmark \]

Szürjektív

\[ z \in C \xRightarrow{\text{f szürjektív}} \exists y \in B: f(y) = z \xRightarrow{\text{g szürjektív}} \exists x \in A: g(x) = y \Rightarrow f(g(x)) = z \checkmark \]

\(\text{Bijektív} \checkmark\)

Tétel: Szorzás Moivre-féle képlete

\[ \text{Ha } z= r \cdot (\cos \alpha + i \cdot \sin \alpha) \]
\[ w = s \cdot (\cos \beta + i \cdot \sin \beta) \]
\[ z \cdot w = r \cdot s \cdot(\cos (\alpha + \beta) + i \cdot \sin (\alpha + \beta)) \]

Bizonyítás

Fontos a bizonyításhoz (Triviális, de biztonság kedvéért iderakom): $$ i^2 = -1 $$

\[ (\cos \alpha + i \cdot \sin \alpha) \cdot (\cos \beta + i \cdot \sin \beta) \stackrel{\mathbb{C}\text{ osztói}}{=} (\cos \alpha \cdot \cos \beta - \sin \alpha \cdot \sin \beta) + (\cos \alpha \cdot \sin \beta + \sin \alpha \cdot \cos \beta) \cdot i = \cos(\alpha + \beta) + \sin(\alpha + \beta) \cdot i \quad \checkmark \]

Tétel: Komplex számok n-edik hatványára vonatkozó tétele

\[ \text{Ha } z \neq 0 \]
\[ z = r \cdot (\cos \gamma + i \cdot \sin \gamma) \text{, } n \in \mathbb{N}^+ \text{, akkor azok a } w \in \mathbb{C} \text{ értékek, melyekre} w^n = z \text{, a következők (n db): } \]
\[ w = \sqrt[n]{r} \cdot \left(\cos \frac{\gamma + 2k\pi}{n} + i \cdot \sin \frac{\gamma + 2k\pi}{n}\right) \]
\[ k = 0,1,2...., n-1 \]

Bizonyítás

\[ \text{Ha } w^n = z \text{, és w trigonometrikus alakja: } w = s \cdot (\cos \alpha + i \cdot \sin \alpha) \text{, akkor} w^n = s^n \cdot (\cos n \cdot \alpha + i \cdot \sin n\cdot\alpha) = r \cdot (\cos \gamma + i \cdot \sin \gamma) = z \]
\[ \iff \]
\[ s^n = r \]

és $$ n\cdot\alpha = \gamma + 2k\pi \text{, ahol } k \in \mathbb{Z} $$

\[ \alpha = \frac{\gamma+2k\pi}{n} \text{ bármilyen } k \in \mathbb{Z} \]
\[ \text{De ha } k' = k +n \Rightarrow \alpha = \frac{\gamma + 2k\pi}{n} \]
\[ \alpha' = \frac{\gamma + 2k'\pi}{n} \]

Ugyanazt a w-t adja. $$ \Rightarrow \text{ elég a } k=0,1,2,..,n-1 \text{-et behelyettesíteni.} $$

Tétel: Komplex szám n-edik gyöke \(v \cdot w_k\) alakú tétele

Ha z-nek ismerjük egy n-edik gyökét: v akkor $$ v^n = z \text{, akkor az összes (többi) n-edik gyöke: } v \cdot w_k \text{ alakú, ahol } w_k \text{ az n-edik egységgyök} $$

Bizonyítás

  • Vegyük ezt a kifejezést: \((v \cdot w_k)^n\)
  • \(v^n = z\)
  • Minden egységgyökre igaz hogy \((w_k)^n=1\)
  • Tehát: \((v \cdot w_k)^n = v^n \cdot (w_k)^n = z \cdot 1 = z\)

Tétel: Az alábbiak ekivalensek egy \(\epsilon\) egységgyökre

  • \(\text{a, }\epsilon \text{ primitív n-edik egységgyök (rendje n)}\)
  • \(\text{b, }\epsilon \text{hatványai az összes n-edik egységyököt előállítják}\)
  • \(\text{, }\epsilon^0, \epsilon^1,...\epsilon^n-1 \text{ mind különböző}\)

Bizonyítás

\[ \text{c, } \Rightarrow \text{b, } (\epsilon^k)^n = (\epsilon^n)^k = 1 \text{, tehát } \epsilon^k \text{ is n-edik egységgyök, és ha mind különböző akkor megvan mind az n.} \]
\[ \text{b, } \Rightarrow \text{ c, ha lenne két azonos katvány: } 0 \leq i < j \leq n-1: \]
\[ \epsilon^i = \epsilon^j \Rightarrow \epsilon^{j-i} = 1 = \epsilon^0 \Rightarrow \epsilon^0, \epsilon^1, \epsilon^2, \ldots, \epsilon^{j-i} \text{, után az első (j-i) érték ismétlődik, CSAK (j-i) darab egységgyök áll elő.} \]
\[ \text{a, } \Leftarrow \text{ c, Ha az első } \epsilon^0, \epsilon^1, ..., \epsilon^n-1 \text{ mind különbözők, akkor} \epsilon^1 \neq \epsilon^0 = 1 \]
\[ \epsilon^2 \neq 1 \]
\[ \epsilon^3 \neq 1 \]

stb... $$ \Rightarrow \text{ n a legkisebb pozitív kitevő: } \epsilon^n = 1 $$

\[ \text{a, } \Rightarrow \text{ c, Ha nem lenne mind különböző: } \Rightarrow 0 \leq i < j \leq n-1 \]
\[ \epsilon^i = \epsilon^j \Rightarrow \epsilon^j-i=1 \text{, } j-i < n \]

Tétel: Egy n elemű halmaznak n! darab permutációja van

Bizonyítás

Indukció: n=0,1 $$ \text{Ha n-re igaz} \xRightarrow{\text{?}} n+1-re $$

Legyen |A| = n+1, és képezzük az n+1 hosszú sorozatot

  • Mi az utolsó eleme?
    • n+1 féle eset
  • Mi az első n eleme?
    • A maradék n elem permutációja, Indukció: n! eset
\[ \Rightarrow \text{Az esetek száma: (n+1)} \cdot \text{n! = (n+1!)} \]

Kombinatorikás tételek pain

Tétel: Gráfok fokszáma

A fokszám mindig páros.

Bizonyítás

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

Tétel: Fák ekvivalens jellemzése

Ha \(G\) egyszerű gráf, akkor a következő állítások ekvivalensek:

  1. \(G\) fa
  2. \(G\) körmentes, de ha bárhová behúzunk egy élt, kör keletkezik.
  3. \(G\) bármelyik 2 csúcsa között pontosan 1 út van.
  4. \(G\) összefüggő, de bármelyik élt elhagyva már nem az.

Bizonyítás

  1. \(\Rightarrow\) 2 Körmentes

    Behúzunk \(G\)-be +1 élt, \(v_1\) és \(v_2\) közé. De \(G\) összefüggő, tehát volt út \(v_1\) és \(v_2\) között, ezért a behúzott éllel kör keletkezett.

  2. \(\Rightarrow\) 3 \(v_1\) és \(v_2\) között út létezik

    Ha behúznék egy élt, keletkezne új kör, ebben szerepel az új él. A kör többi éle egy út \(v_1\) és \(v_2\) között.

    Csak 1 út van:

    Ha lenne 2 út, akkor azok között lenne egy kör, de \(G\) körmentes.

  3. \(\Rightarrow\) 4 \(G\) összefüggő, de bármelyik élt elhagyva már nem az

    Ha elhagyható lenne egy él, akkor nem lenne körmentes, hisz az elhagyott él után már nem lehet út \(v_1\) és \(v_2\) között.

  4. \(\Rightarrow\) 1 \(G\) fa

    • Összefüggő \(\checkmark\)
    • Körmentes \(\checkmark\) (1. biz miatt)

Tétel

Ha \(G\) egy véges körmentes véges gráf legalább 1 éllel \(\Rightarrow\) \(\exists\) benne elsőfokú csúcs.

Bizonyítás

Keressük meg a leghosszabb (egyik) utat \(G\)-ben. Ennek a végpontjai elsőfokúak, mert ha nem lennének azok, akkor ez nem lehetne a leghosszabb út.

Tétel

\(n \in \mathbb{N}^+\). Egy \(n\) csúcsú \(G\) egyszerű gráfra ekvivalensek a következő állítások:

  1. \(G\) fa
  2. \(G\)-nek (n-1) éle van, és körmentes
  3. \(G\)-nek (n-1) éle van, és összefüggő

Bizonyítás

  1. \(\Rightarrow\) 2 \(G\)-nek \(n-1\) éle van és körmentes

    Indukció:

    n=1 \(\rightarrow\) 0 él

    n-re tudjuk \(\Rightarrow\) (n+1)-re?

    n+1 csúcsú fa \(\Rightarrow\) \(\exists\) elsőfokú csúcs: \(v\)

    Ha az elsőfokú csúcsot, és a hozzá tartozó élt elhagyjuk, akkor egy \(n\) csúcsú fa keletkezik \(\Rightarrow\) (n-1) él \(\Rightarrow\) \(G\): n él n = (n+1)-1

  2. \(\Rightarrow\) 3 (n-1) éle van, és összefüggő

    Indukció n=1 \(\checkmark\)

    n-re tudjuk \(\Rightarrow\) (n+1)-re?

    LEMMA: \(\exists\) elsőfokú csúcs

    Ind. feltevés \(\Rightarrow\) eltávolítva az elsőfokú csúcsot (az élek?) \(\Rightarrow\) összefüggő a kapott gráf \(\Rightarrow\) \(G\) is összefüggő

  3. \(\Rightarrow\) 1 \(G\) fa

    KELL: Körmentes a gráf

    Ha nem lenne az, akkor ismételten, hagyjunk el körökből éleket, amíg végül körmentes lesz \(\Rightarrow\) FA

Tétel

\(G\)-nek \(\exists\) feszítőfája \(\Longleftrightarrow\) \(G\) összefüggő

Bizonyítás (véges \(G\)-re)

Ha \(G\) összefüggő \(\Rightarrow\) addig hagyjuk el belőle a körben szereplő éleket, amíg körmentes nem lesz. Ekkor \(G\)-nek van feszítőfája.

Tétel

Egy \(n\) csúcsú, \(e\) élű összefüggő gráfba \(\exists e-n+1\) db kör, melyek páronként különböző élhalmazúak.

Bizonyítás

Tekintsük \(G\) egy feszítőfáját: \((n-1)\) él.

A feszítőfán kívül van \(e-(n-1)=e-n+1\) db él.

Ezen extra élek közül bármelyiket hozzávéve a feszítőfához, kör keletkezik. \(\rightsquigarrow\) ha mindig csak az ilyen élt veszünk hozzá, akkor páronként kölönbözőek a körök.

Euler Tétel

Ha \(G\) egy véges összefüggő gráf:

G-ben \(\exists\) Zárt Euler vonal \(\Longleftrightarrow\) \(\forall\) csúcs foka páros

Bizonyítás

Minden áthaladáskor egy csúcsnál 2 élt használunk el. A kezdő és végpontnál pedig az első és utolsó él is párba állítható. Amikor az Euler-vonal áthalad egy csúcson, akkor egy ilyen áthaladás 2-vel járul hozzá a csúcs fokszámához, ezért minden csúcs fokszáma páros.