Dimat2/LinAlg

Lineáris leképezés
Legyenek V1 és V2 ugyanazon T test feletti vektorterek, és tekintsük az f:V1 -> V2 függvényt.
Az f függvényt additívnak nevezzük, ha minden x,y eleme V1 esetén f(x+y)=f(x)+f(y) teljesül.
Az f függvényt homogénnek nevezzük, ha minden x,y eleme V1 és lambda eleme T esetén f(lambda*x)= lambda *f(x) teljesül.
Ha f additív és homogén, akkor f-et lineáris leképezésnek nevezzük (a V1 és V2 vektorterek között)
Például:
1, f:R négyzetből képezünk R-et, f(x,y)=x (projekció leképezés az x tengelyre)
Additivitás
f((a,b)+(c,d))=f(a+c,b+d)=a+c
f(a,b)=a
f(c,d)=c
f(a,b)+f(c,d)=a+c => egyenlőek tehát additív
Homogenitás
f(lambda(a,b))=f(lambda*a,lambda*b)=lambda * a
lambda*f(a,b)=lambda*a => egyenlőek tehát homogén így f lineáris leképezés
Lineáris leképezések tulajdonságai:
Legyenek V1 és V2 ugyanazon T test feletti vektorok.
f:V1->V2 lineáris leképezés
1, f(0)=0 (nullvektor)
biz: f(0)=f(0+0)=f(0)+f(0)   /-f(0)
     0=f(0)
2, minden a eleme V1 esetéb f(-a)=-f(a)
3, Ha L altere V1-nek, akkor altér f(L) altere V2-nek
4, Ha a1,a2,..., an és "a" a V1 vektortér vektorai és a=lambda1*a1+lambda2*a2+...lambdan*an valamelylambda1, lambda2,...,lambdan skalárok esetén, akkor f(a)=lambda*f(a1)+lambda2*f(a2)+...+lambdan*f(an)
Ebből következik, hogy minden lineáris leképezés egyértelműen megadható úgy, hogy  megadjuk a bázisvektorok képeit.
Lineáris leképezések alaptétele: Legyenek a1,a2,...,an a V1 vektortér egy bázisa, b1,b2,...,bn pedig a V2 vektortér tetszőleges vektorai.Ekkor pontosan egy olyan f:V1->V2 lineáris leképezés létezik, melyre f(a1)=b1, f(a2)=b2,....,f(an)=bn teljesül
Ez a lineáris leképezés a következőképp konstruálható meg
Legyen a1 eleme V1 tetszőleges vektor. Ekkor létezik lambda1,lambda2,...,lambdan skalárok, hogy a=lambda1*a1+lambda2*a2+...+lambdan*an. Legyen ekkor f(a)=lambda1*b1+lambda2*b2+...."lambdan*bn, könnyű bebizonyítani, hogy ez így lineáris leképzeés ha "a" helyére a1-et írunk: a1=1*a1, f(a1)=1*b1 ...
példa:
bázisok: a1(0,1) a2=(1,0) f(a1)=b1=(2,4) f(a2)=b2=(4,5)
f(5,5)= ?
(5,5)=5*(1,0)+5*(0,1)
f(5,5)=5*(4,5)+5*(2,4)=(20,25)+(10,20)=(30,45)
f(5,5)=(30,45)
5, A V1 tér generátorrendszerének képe a generátorrendszer lesz a V2 térben.
6, Lineárisan függő vektorrendszer képe lineárisan függő vektorrendszer.
7, Ha L altere V1 térnek, akkor dim L >= dimf(L).
Magtér
Legyenek V1 és V2 ugyanazon T test feletti vektorterek, f:V1->V2 lineáris leképezés.
A kerf={x eleme V1: f(x)=0} halmazt az f lineáris leképezés magjának nevezzük
A mag a nullvektort biztosan tartalmazza.
pl: f:R négyzetből képez R-et f(a,b)=a ker f ={(0,b): b eleme R}
Tétel: A ker f altere a V1-nek
Biz: Megmutatjuk, hogy ha a,b eleme ker f => a-b eleme ker f, és minden lambda skalár esetén lambda*ä eleme ker f
f(a-b)=f(a)-f(b) = 0-0=0 tehát a-b eleme ker f
f(lambda*a)=lambda*f(a)=lambda*0=0 tehát lambda*a eleme ker f
Nullitás rangtétele:
dim ker f + dimf(V) = dimV1  // a ker f a magtér, az f(V) a képtér és a V1 a leképezés alaptere
Tétel: Egy lineáris leképezés pontosan akkor kölcsönösen egyértelmű, ha a magja csak a nullvektort tartalmazza.
Biz: 1. Legyen f:V1->V2 kölcsönösen egyértelmű lineáris leképezés. Ekkor 0eleme ker f, és mivel különböző elemek képe különböző, így a nullvektoron kívül más vektor nem lehet a magban.
2. Legyen f:V1->V2 olyan lineáris leképezés, hogy ker f={0}. Legyenek a,b eleme V1, és TFM f(a)=f(b)
f(a-b)=f(a)-f(b)=0 ekkor a-b eleme ker f tehát a-b=0 vagy is a=b
Bijektív: injektív és szürjektív.
f:V1->V2  f injektív, ha különböző vektorok képei és különböznek (f injektív akkor és csak akkor ha ker f ={0})
f szürjektív, ha V2 minden vektora hozzá van rendelve valamely V1-beli vektorhoz az f által f(v1)=V2
pl: f:R négyzetből képek R-t, f(x,y)=x szürjektív, de nem injektív... pl: f(1,0)=1 vagy f(1,13)=1
Izomorfizmus:
Ha egy lineáris leképezés bijektív, akkor azt izomorfizmusnak hívjuk. A V1 és V2 vektortereket izomorf vektortereknek nevezzük, ha létezik f:V1->V2 izomorfizmus.
Izomorf vektorterek között algebrai különbség nincs (tulajdonságokat bármelyben lehet vizsgálni)
pl: dimenzióik egyenlők
A vektorterek között az izomorfizmus ekvivalencia reláció.
-Reflexív: minden V vektortér izomorf önmagával (identikus leképezés)
-Szimetrikus: ha V1 izomorf V2-vel => V2 is izomorf V1-el
-Tranzitív: ha V1 izomorf V2-vel és V2 izomorf V3-al akkor V1 izomorf V3-al
Egy lineáris leképezés lineárisan független vektorrendszert nem feltétlenül lineárisan független vektorrendszerbe viszi át.
Pl: f:v1->V2, f(x)=0 (a{0} önmagába lineárisan függő rendszer)
Izomorfizmus lineárisan független vektorrendszert lineárisan függetlenbe visz át.
Biz: Legyenek V1 és V2 ugyanazon T test feletti vektorterek, és legyen f:V1->V2 izomorfizmus.
Legyenek a1,...,an lineárisan független vektorai a V1-nek
Megmutatjuk, hogy f(a1),..,f(an) lineárisan független vektorai V2-nek.
lambda1*f(a1)+lambda2*f(a2)+...+lambdan*f(an)=0  (minden lambda i =0; i=1,..,n)
f(lambda1*a1)+f(lambda2*a2)+....+f(lambda n*an)=0 (mivel f lineáris leképezés)
f(lambda1*a1+lambda2*a2+..."lambda n *an)=0 akkor lambda1*a1+....+lambda n *an eleme ker f
Mivel az izomorfizmus injektív akkor lambda1*a1+lambda2*a2+....+lambda n*an = 0
Mivel a1,a2,...,an független vektorai V1-nek, így ez az egyenlőség csak akkor teljesül, ha lambda1=lambda2=...=lambda n=0
Izomorf vektorterek dimeziója megegyezik (véges dimenziós vektorterek esetén igaz).
Biz: V1 éa V2 izomorf vektorterek akkor létezik f:V1->V2 izomorfizmus ha dimV1=n akkor van V1-ben n darab vektorból álló bázis. Ennek az n darab vektornak a képe az előbb bizonyítottak  szerint szintén lineárisan független generátorrendszer, azaz bázisa lesz a V2-nek akkor dim V2 = n .
Ha 2 végesdimenziós vektortér dimenziója megegyezik akkor a 2 vektortér izomorf.
Biz: Legyen V1 egy n dimenziós vektortér a T test felett. Rögzítsünk benne egy bázist:a1,a2,...,an
Ekkor minden a eleme V1 vektorhoz létezik lambda1,lambda2,...,lambda n skalárok, hogy az "a" egyértelműen felírható a=lambda1*a1+lambda2*a2+..."lambda n*an alakban.
Legyen f:V1->T az n-diken , f(a)=(lambda1,lambda2,...,lambda n) a T az n-diken a rendezett elem n.esek, a végén a zárójelben lévő lambdék az "a" vektor a1,a2,..,an bázisra vonatkozó koordinátái
Ez a leképezés lineáris és bijektív => izomorfizmus. Beláttuk, hogy minden n dimenziós T test feletti vektortér izomorf T n-dikkel. Mivel az izomorfizmus tranzitív, a T test feletti n dimenziós vektor terek izomorfak.
Lineáris transzformáció
Legyen V egy vektortér. Az f:V->V lineáris leképezést V-n ható lineáris transzformásiónak nevezzük.
pl: f:R négyzet képez R négyzetbe, f(x,y)=(x,-y) ez injektív és szürjektív is
    g: R nlgyzet képez R négyeztbe, g(x,y)=(0,0) ez nem injektív és nem is szürjektív
Egy lineáris transzformáció pontosan akkor injektív, ha szürjektív.
Biz: ha f:V->V injektív lineáris leképezés akkor ker f ={0}
Nullitás rangtétel -> dim ker f + dim f(V)= dimV
-f(V) vagy maga a V, vagy annak egy altere
-ha alterével megegyező dimenziójú, akkor egyenlők
Annak a bizonyítása, hogy szürjektív lineáris leképezés injektív, pontosan így van, csak fordítva.
Még egy példa a lineáris transzformációra: legyen V egy n dienziós vektortér a T test felett, és legyen A egy adott nxn tipusú mátrix T test felette. Ekkor tekintsük a T az nediken vektorteret.
Ekkor az f:T az nedikent képezzük T az ndikbe, f(x)=a*x lineáris transzformáció. Meg fogjuk mutatni, hogy minden T az nediken ható lineáris transzformáció megoldható így.
Kérdés: hogyan találjuk meg ezt az A matrixot?
Veszünk a T az nediken térben egy bázist: a1,a2,..,an
Az f(a1),f(a2),...,f(an) vektorok szintén a T az nediken elemei, így ezek is előállíthatók az a1,a2,..,an vektor lineáris kombinációjaként.
Az A matrix pontosan az a mátrix , melynek i. oszlopában az f(ai) vektor a1,a2,..,an bázisra vonatkozó koordinátái állnak.
Ezt a mátrixot nevezzük az f lineáris transzformáció a1,a2,..,an bázisra vonatkozó mátrixának.
Kérdés: hogyan változik egy lineáris transzformáció mátrixa, ha megváltoztatom a bázist?
Bázis és koordinátatranszformáció:
Ha egy vektornak ismerjük a koordinátáit egy adott bázisra vonatkozóan, akkor hogyan kaphatjuk meg ugyanezen vektor koordinátáit egy másik bázisra vonatkozóan?
Ha több vektornak is szeretnénk tudni a koordinátáit az L bázisra vonatkozóan, akkor célszerű a lineáris egyenletrendszer mátrixos alakjával foglalkozni, ugyanis a megoldandó lineáris egyenletrendszer mátrixa nem fog változni, ha megváltoztatjuk az "a" vektort, mert ez az M mátrix csak attól a bázistól függ, melyre át akarunk térni. A szübanforgó vektor új koordinátáit megkapjuk úgy, hogy ezeket a koordinátákat tartalmazó 2x1 es mátrixot balról megszorozzuk a lineáris egyenletrendszer alapmátrixának inverzével. Ezt az M mátrixot nevezzük az e bázisról az L bázisra való átmenet mátrixának (báziscsere mátrix).
Legyen V egy n dimenziós tetszőleges vektortét T test felett, és legyen e1,e2,...,en és l1,l2,...,ln egy-egy bázisa V-nek. Ekkor azt az nxn tipúsú mátrixot, melynek i. oszlopában az Li vektor e bázisra vonatkozó koordinátái állnak, az e bázisról az L bázisra való báziscsere mátrixának hívjuk.
Legyen S az e-ről L-re való bázissere mátrixa. Ekkor S-nek létezik inverze, és S a -1ediken az L-ről e-re való báziscsere mátrixa.
Legyen x és y a b eleme V vektor koordinátáit tartalmazó nx1 tipusú mátrix az e, illetve L bázisra vonatkozóan. Ekkor Y=S a -1 ediken * X.
Legyen V egy tetszőleges vektortér T test felett, és legyenek e és L egy-egy bázisa V-nek. Legyen továbbá f:V->V lineáris transzformáció , melynek mátrixa az e bázisra vonatkozóan A, az L bázisra vonatkozóan pedig B.
Ekkor B=S a -1 ediken*A*S ahol S az e-ről L-re való báziscsere mátrixa
Legyenek f és g lineáris transzformációk a V T test feletti vektortérben. Ekkor az f+g, fkörg és lambda*f(lambda eleme T) függvények is lineáris transzformációi a V vektortérnek.
Megj: (f+g)(x)=f(x)+g(x) //mátrixok összege
      (f kör g)(x)=f(g(x))  // mátrixok szorzata
      (lambda * f)(x)=lambda*f(x)  //mátrix lambda-szorosa
Ha egy adott bázisra vonatkozóan az f és g mátrixai A és B, akkor: f+g mátrixa A+B, f kör g mátrixa A*B, lambda * f mátrixa lambda*A mátrix lesz
Jelölje End(V) az összes V-n ható lineáris transzformáció halmazár. Ez vektortér lesz T test felett a fent definiált összeadással és skalárral való szorzással.
Tekintsük a T test feletti nxn tipúsú mátrixokat: gecinagy M nxm (T)
TFH V egy n dimenziós vektortér, és rögzítsük egy bázisát. Legyen fí az a leképezés, amely V minden lineáris leképezéséhez hozzárendeli a megadott bázisra vonatkozó mátrixát.
fí:End(V) ->nagy M nxm (T) fí injektív és szürjektív is
Ha az előbbiek szerint ez lineáris leképezés, továbbá kölcsönösen egyértelmű. Theát fí izomorfizmus.
Ennek jelentése az, hogy a V vektortér lineáris transzformációi helyett elegendő a T test feletti nxn tipusú mátrixokat tanulmányozni.
Lineáris transzformációk spektrál elmélete
Legyen V egy T test feletti vektortér, és f egy lineáris transzformáció V-n. Ha valamely lambda eleme T skalárra és a eleme V vektorra teljesül, hogy f(a) = lambda*a, akkor a lambda-t az f sajátértékének, az "a" vektort pedig f lambda-hoz tartozó sajátvektorának nevezzük
Egy adott lambda sajátértékhez tartozó sajátvektorok alteret alkotnak V-ben.
Megj: Tehát ugyanahhoz a sajátértékhez több sajátvektor is tartozhat, de egy sajátvektor csak egyetlen sajátértékhez tartozik.
Megj: AZ Llambda={x eleme V: f(x)=lambda*x} halmazt az f lineáris transzformáció lambda sajátértékéhez tartozó sajátalterének nevezzük.
Legyen az f lineáris transzformáció mátrixa egy adott bázisra vonatkozóan A, és lambda pedig egy sajátértéke f-nek. Ha "a" egy lambda-hoz tartozó sajátvektora f-nek és Xo az "a" adott bátisra vonatkozó koordinátaoszlopa, akkor:
f(a)=lambda*a
A*Xo=lambda*Xo
A*Xo-lambda*Xo=0
(A-lambda*E)*Xo=0
Tehát f lambda-hoz tartozó sajátvektorainak koordinátáit az (A-lambda*E)*Xo=0 homogén lineáris egyenletrendszer megoldásaiként kapjuk.
Legyen A egy T test feletti nxm tipusú mátrix. Ekkor a det(A-X*E) kifejezés tulajdonképpen egy pilonom, melyet az A mátrix karakterisztikus polinomjának nevezzük.
Belátható, hogy egy lineáris transzformáció különböző bázisra vonatkozó mátrixának karakterisztikus polinomja ugyanazok. Ezt a "közös" polinomot nevezzük a lineáris transzformáció karakterisztikus polinomján. A V T test feletti vektortér egy lineáris transzformációjának sajátértékei pontosan, a karakterisztikus polinom T-be eső gyökei lesznek.
Ha lambda1,lambda2,...,lambda n páronként különböző sajátértékei az f lineáris transzformációnak , és a1,a2,..,ak egy-egy hozzájuk tartozó sajátvektor, akkor a1,a2,..,ak lineárisan független vektorrendszer. Ennek következménye, hogy különböző sajátértékhez tartozó sajátaltereknek csak a nullvektor lehet közös eleme.

Skaláris szorzat(belső szorzat)
A V valós vektorteret Euklideszi térnek nevezzük, ha értelmezve van egy <.,.>: VxV->R függvény az alábbi tulajdonságokkal:
1, <x,y>>=0 és <x,x>=a akkor és csak akkor ha x= 0
2,<x,y> = <y,x> (szimmetrikus)
3, a, <x1 + x2> = <x1,y> + <x2,y>
   b, <lambda*x,y> = lambda<x,y>
(a 2. tulajdonság garantálja, hogy a 3.ban a második helyen is állhatnak ezek)
Ezesetben a <.,.> függvényt skaláris (vagy belső) szorzatnak nevezzük.
Pl: 1, R az nediken Euklideszi tér az alábbi belső szrozattal:
x=(x1,x2,...,xn) y=(y1,y2,..,yn)
<x,y>=x1y1+x2y2+...+xn*yn

   2, a sír szabadvektorainak vektorterében: <a,b>=|a|*|b|*cosalfa(a,b)
Legyen E egy Euklideszi tér. Az x eleme E vektor hosszán(normáján) az ||x||=gyökjel alatt <x,y> számot értjük.
Cauchy-Bunyakovszkij-Schwartz egyenlőtlenség
|<x,y>| <= ||x||*||y|| teljesül minden Euklideszi tér minden x,y vektoraira. Egyenlőtlenség pontosan akkor teljesül, ha a 2 vektor lineárisan függő.
Biz: Legyen lambda tetszőleges valós szám
<x+lambda*y, x+lambda*y> >= 0
<x,x>+<x,lambda*y>+<lambda*y,x>+<lambda*y,lambda*y> >= 0
<x,x>+lambda<x,y>+lambda<y,x>+lambdanégyzet<y,y> >= 0
<y,y>*lambdanégyzet+2*<x,y>*lmabda+<x,x> >= 0 A bal oldalon egy valós együtthatós másodfokú polinom van, melynek változója lambda. /f(lambda)/. Mivel a polinom helyettesítési értéke minden lambda eseteéb >= 0 akkor a D <= 0 (polinom diszkriminánsa)
Ha itt az egyenlőség teljesül akkor D=0, tehát létezik lambda eleme R, melyre f(lambda)=0
Erre a lambdára az <x+lambda*y,x+lambda*y>=0 akkor x+lambda*y=0 tehát x=-lambda*y
(tehát egyik vektor skalárszorosa a másiknak)
Az x és y vektorok szögén azt a 0 fok és 180 fok közötti szöget értjük, melynek cosinusa <x,y> / ||x||*||y||
pl: x=(1,2) eleme R négyeztnek y=(4,5) eleme R négyzetnek
   <x,y> = 1*2+2*5=14
   ||x||= gyökjel alatt 1 a nagyézeten + 2 a négyzeten = gyökjel alatt 5
   ||y||=gyökjek alatt 4 a négyzeten + 5 a négyzeten = gyökjel alatt 41
cos alfa= 14 / gyökjel alatt 5 * gyökjel alatt 41 = 14 / gyökjel alatt 205 alfa= 12,09 fok
Minkowski - egyenlőtlesnég
||x+y|| <= ||x||+||y|| teljesül minden Euklideszi tér minden x,y vektoraira. Egyenlőség pontosak akkor teljesül, ha egyik a másiknak a nemnegatív számszorosa.
Biz:
||a|| = gyökjel alatt <a,a> ebből adódóan ||a|| a négyzeten = <a,a>
||x+y|| a négyzeten = <x+y, x+y>
||x+y|| a négyzeten = <x,x>+<x,y>+<y,x>+<y,y>
||x+y|| a négyzeten = ||x|| a négyzeten + 2*<x,y>+ ||y|| a négyzeten <= ||x|| a négyzeten + ||y|| a négyzeten + 2*|<x,y>| <= ||x|| a négyzeten + ||y|| a négyzeten + 2*||x||*||y|| = (||x||+||y||) a négyzeten
||x+y|| a négyzeten <= (||x||+||y||) a négyzeten tehát ||x+y|| <= ||x||+||y||
A második becslésnél a CBS-t használzuk, ott akkor írhatnánk egyenlőséget, ha egyik vektor a másiknak a skalárszorosa lenne.
<x,lambda*x> <= |<x,lambda*x>|
Ha a lambda nem negaítv akkor az egyenlőség teljesül
Ortogonalitás
Az a,b eleme E (a,b nem egyenlő 0) vektorok szögén azt az alfa szöget értjük, melyre cos alfa = (a,b) / ||a|| * ||b||
Síkgeometriában a merőlegesség azt jelenti, hogy a 2 vektor 90 fokos szöget zár be: cos90fok = 0 tehát (a,b) = 0
Azt mondjuk, hogy az a,b eleme E vektorok ortogonálisak , ha (a,b) = 0 (belső szorzat)
Pit. tétel: ||c|| a négyzeten = ||a|| a négyzeten +||b|| a négyzeten
Az a,b eleme E vektorok pontosan akkor ortogonálisak, ha ||a|| a négyzeten + ||b|| a négyzeten = ||a+b|| a négyzeten (tetszőleges dimenzióban)
Biz: ||a+b|| a négyzeten = (a+b,a+b)= (a,a)+(a,b)+(b,a)+(b,b)= ||a|| a négyzeten + 2*(a,b) + ||b|| a négyzeten = ||a|| a négyzeten + ||b|| a négyzeten
Egy vektorrendszert ortogonális vektorrendszernek nevezünk, ha minden 2 különböző vektorra ortogonális.
Egy "a" vektor egységvektor, ha ||a|| = 1.Egy vektorrendszert ortonomált vektorrendszernek nevezünk, ha ortogonális vektorrendszer és minden vektorra egységvektor.
Áll: Egy nullvektort nem tartalmazó ortogonális vektorrendszer lineárisan független.
Gram - Schmidt - féle ortogonalizálási eljárás
Az E Euklideszi tér minden b1,b2,...,bn bázisához található olyan e1,e2,..,en ortonomált bázis, hogy b1,b2,...,bn és e1,e2,...,ek vektorrendszerek ugyanazt a k dimenziós alteret generálják Vk = 1,2,...,n esetén.
1. lépés: e1= b1 / ||b1||
2. lépés: e2' = b2 - (b2,e1)*e1
          e2 = e2' / ||e2'||  ha e2'=0 lenne akkor b2=(b2,e1)*e1 lenne tehát b2 b1 nek skalárszorosa lenne, vagy is nem lenne létező bázis
e2 és e1 ortogonálisak akkor és csak akkor ha e2' és e1 ortogonálisak
3. lépés: e3'=b3 - (b3,e2)*e2-(b3,e1)*e1
         e3= e3' / ||e3|| stb stb....
n. lépés: en' = bn - (bn, en-1)*en-1 -....-(bn,e1)*e1
Pl: alkalmazzuk a Gram-shmidt féle ortogonalizálási eljárást az a1, a2, a3 vektorokra!
a1=(0,1,0,1) a2=(-2,3,0,1) a3=(1,1,1,5)
e1= a1/ ||a|| => ||a|| = gyökjel alatt 0 a négyzeten + 1 a négyzeten + 0 a négyzeten + 1 a négyzeten = gyökjel alatt 2
e1=(0, 1/gyök2, 0, 1/gyök2)
e2' = a2-(a2,e1)*e1
(a2,e21) = -2*+3*1/gyök2+0*0+1*1/gyök2 = 3/gyök2+1/gyök2= 4/gyök2
e2'= (-2,3,0,1)- 4/gyök2*(0,1/gyök2,0,1/gyök2) = (-2,3,0,1) - (0,2,0,2)= (-2,1,0,-1)
||e2'|| = gyökjel alatt 4 + 1 + 1 = gyök6
e2 = e2' / ||e2'|| = (-2/gyök6, 1/gyök6,0,-1/gyök6)
e3'=.... és így tovább
Miért jó az ortonomált bázis?
Ortonomált bázisra vonatkozó koordináták kiszámíthatók a belső szorzat segítségével. Legyen e1,e2,...,en egy ortonomált bázisa az E Euklediszi térnek, és legyen x eleme E tetszőleges vektor. Ekkor x = alfa1*e1 + alfa2*e2+....+alfan*en alakba írható valamely alfa1,alfa2,...,alfan valós számokkal.
alfa - k hogyan kapható meg? alfa i = (x,ei)
Gráfelméleti alapok:
Königsbergi hidak problémája
rajz....
Probléma: lehetséges-e, hogyha elindulunk egy szárazföldi pontról, és minden hidat pontosan egyszer használunk, akkor vissza érhetünk a kiindulási pontra?
rajz...
Irányított gráf:
Legyenes E és C nem egyenlő 0 adott halmazok, és legyen fí:E -> CxC adott függvény. Ekkor a G=(E,fí,C) rendezett hármast irányított gráfnak nevezz
ük.
Iránytalan gráf:
Legyenes E és C nem egyenlő 0 adott halmazok, és legyen fí:E -> CxC adott függvény, ahol CxC a C halmas elemeiből képezett elempárok halmazát jelöli ( 2 C-beli elem, de a sorrendjük nem számít). Ekkor a G(E,fí,C)-t íránytalan gráfnak nevezzük.
Példára visszatalva
C={c1,c2,c3,c4} E={e1,e2,...,e7}
fí(e1)={c1,c2}
fí(e2)={c1,c2}
fí(e3)={c1,c3}
....
fí(e7)={c2,c3}
Megj: (...) -> rendezett, számít a sorrend, irányított gráfoknál
      {...} -> sorrend nem számít, iránytalan gráfoknál
Üres gráf: Azokat a gráfokat, ahol E üres, üres gráfoknak nevezzük.
Véges gráf: Ha E is és C is véges halmazok, véges gráfról beszélünk.
Kezdőpontok, végpontok:
Irányított gráfban, ha fí(ei) = (Ck,Cl)  /k és l lehetnek egyenlőek / akkor azt mondjuk, hogy az ei-nek a Ck a kezdőpontja, a Ce pedig a végpontja.
Iránytalan gráfban, ha fí(ei)={Ck,Cl} akkor azt mondjuk, hogy az ei végpontjai Ck és Cl.
Részgráf:
 A G' = (E',fí',C') gráf a G =(E,fí,C) gráf részgráfja, ha E' részhalmaza E, C' részhalmaza C és fí'(x) = f(x) minden x eleme E' esetén
A részgráfot az eredeti gráfból élek és csúcsok törlésével kaphatjuk meg úgy, hogy csúcs törlése esetén az összes ráilleszkedő élt is töröljük.
Hurokél:
 A G(E,fí,C) gráfban az ei élt hurokélnek nevezzük, ha van olyam Ck, hogy fí(ei) = (Ck,Ck) (irányított gráf) és fí(ei) = {Ck,Ck} (iránytalan gráf)
Párhuzamos élek:
 A G=(E,fí,C) irányított gráfban az ei és ej éleket szigorúan párhuzamos éleknek nevezzük, ha van olyan Ck,Ce eleme C, hogy fí(ei) = (Ck,Ce) és fí(ej)=(Ck,Ce). Ha pedig fí(ei)=(Ck,Ce) és fí(ej)=(Ce,Ck) akkor ei és ej éleket párhuzamos éleknek nevezzük.
Irányítatlan gráfban ez a 2 fogalom egybeesik: ott, ha 2 élnek ugyanazok a végpontjai, akkor azokat az éleket többszörös éleknek nevezzük.
Egyszerű gráf:
Egy gráfot egyszerű gráfnak nevezzük, ha nincs benne se hurokél, se többszörös él.
Fokszám:
Egy gráf egy adott csúcsűnak fokszámán a gráf arra a csúcsra illeszkedő éleinek számát értjük. A hurokél 2-vel növeli a fokszámot. Véges gráfban a csúcsok fokszámainak összege az élek számának kétszeresével egyenlő. Véges gráfban a páratlan fokszámú csúcsok száma páros.
Biz: Legyen G=(E,fí,C) véges gráf, és jelölje a Ci csúcs fokszámát delta(ci)
|E|: élek halmazának a számossága (élek száma)
2*|E| = szumma dalta(c) = szumma delta(c) + szumma delta(c) => páros, ami csak úgy lehet, hogy az összeadandók száma páros (páratlan számok)
Vonal:
Legyen G=(E,fí,C) egy adott gráf. Vonalnak nevezzük a csúcsoknak és éleknek egy olyan C1,e1,c2,e2,c3,e3....,cn,en, Cn+1 sorozatát, ahol az ei él a Ci és Ci+1 csúcsokat köti össze.
Út:
Útnak nevezzük az olyan vonalat, melyben minden csúcs csak egyszer szerepel.
Megj: nem a gráf összes csúcsa!! c1,e1,c2,e2,c3,e3,....,cn,en,Cn+1, ahol ci-k különböznek
Kör:
Egy vonalat körnek nevezünk, ha a C1,C2,...,Cn külöbözőek, és Cn+1 = C1
Út hossza:
Út hossza alatt az útban szereplő élek számát értjül.
pl: C4,e5,c1,e2,c2 => 2 hosszúságú út C4-ből C2-be
Távolság:
2 csúcs távolságán az őket összekötő utak hosszának a minimumát értjük. Ha a 2 csúcsot nem köt össze út, akkor távolságuk végtelen.
Átmérő:
A gráf átmérője a gráf csúcsai közötti távolság maximuma.
Összefüggő gráf:
Egy gráfot összefüggőnek nevezünk, ha minden csúcsából minden csúcsába vezet út.
Komponens:
Egy gráf maximális összefüggő részgráfjait a gráf komponenseinek nevezzük, azaz a G=(E,fí,C) gráfnak a G'=(E',fí',C') gráf komponense, ha G' összefüggő részgráfja G-nek, és G-ben nem létezik olyan G'' összefüggő részgráf, melynek G' valódi részgráfja. (nem egyenlő vele)
Fa,erdő:
Egy gráfot fának nevezünk, ha egyszerű, összefüggő és körmentes.
Egy fagráfnak mindenképpen van legalább 2 elsőfokú csúcsa.
Egy fagráfban: |C|=|E|+1
Egy gráfot erődnek hívunk, ha komponensei fák.
Izomorfia:
A G=(E,fí,C) és G'=(E',fí',C') gráfokat izomorf gráfoknak nevezzül, ha:
- létezik f:C->C kölcsönösen egyértelmű leképezés
- létezik g:E->E kölcsönösen egyértelmű leképezés
- ha fí(e)=(ci,cj), akkor fí'(g(e))=(f(Ci),f(cj))
Feszítőfa:
Egy gráf feszítőfája alatt olyan fagráfot értünk, amely tartalmazza az eredeti gráf minden csúcsát, és az élei is az eredeti gráf élei özül kerülnek ki.
Teljes gráf:
Egy egyszerű gráfot n-szögpontú teljes gráfnak nevezünk, ha n csúcsa van, és bármely 2 csúcsot él köti össze.
n=1
n=2....
n-szögpontú teljes gráf éleinek száma: n*(n-1) / 2
Komplementgráf:
Egy n csúcsú egyszerű gráf komplementergráfján azt a gráfot értjük, mely az eredetit az n-szögpontú teljes gráffá egészíti ki.
Euler-vonal, Euler-kör, Hamilton-kör:
Egy gráf Euler-vonalán egy olyan vonalat értünk, amely a gráf minden élét pontosan egyszer tartalmazza (csúcs ismétlődhet)
Ha a kezdő és végpontja ugyan az: Euler-kör (zárt Euler-vonal)
Egy gráfot Euler-gráfnak nevezünk, ha van zárt Euler-vonala.
Egy gráf pontosan akkor Euler-gráf, ha összefüggő, és minden csúcsának a foka páros.
A gráf egy útját Hamilton-útnak nevezzük, ha az út a gráf minden csúcsát pontosan egyszer tartalmazza. Ha ez az út kör, akkor Hamilton-körnek nevezzük.
Ore-tétel:
ha egy gráf csúcsainak száma nagyobb mint 2, és bármely 2 nem szomszédos csúcs fokszámának összege nagyobb egyenlő mint a gráf csúcsainak száma, akkor a gráfnak van Hamilton-köre
Dirac-Tétel:
Ha egy n=2*k csúcspontú gráf minden csúcsának a foka legalább k, akkor a gráfnak van Hamilton-köre.
Gráfok csúcsmátrixa:
Legyen adott a G=(E,fí,C) irányított gráf, ahol a |c|=n. Azt az nxm tipusú mátrixot, melynek Aij eleme a Ci csúcsból a Cj-be menő élek száma, a G gráf csúcsmátrixának nevezzük. A csúcsmátrix L_edik hatványának i. sor j. oszlopában lévő elem megadja a Ci csúcsból Cj-be vezető l hosszúságú vonalak számát.
A Ci csúcsból a Cj csúcsba akkor vezet R hosszúságú legrvidebb út, ha a k-nál kisebb kitevőjű hatványában a csúcsmátrixnak az i. sor j. oszlopeleme 0, a k. hatványában viszont már nem 0.
Kódelmélet
Adó-csatorna-vevő
Kimeneti ábécé: véges sok jellből álló halmaz A={a1,a2,...,an}
Információ továbbításának folyamata:
- olyan csatornát veszünk alapul, ami csak kétféle jel továbbítására képes (0,1)
-  az adó által közölt információt át kell alakítani 0 1 sorozatú => kódolás
- a 0 1 sorozat átalakítása valamilyen csatornán továbbítható fizikai jelekké => moduláció
- fizikai jelek küldése a csatornán
- a fizikai jelek felfogása a vevői oldalon
- a fogadott fizikai jelek visszaállítása 0 1 sorozattá => demodulálás
- a 0 1 sorozatból vissza kell állítani az eredeti közlést => dekódolás
Betű szerinti kódolás:
Az ábécé minden egyes betűjéhez hozzárendelünk egy bináris sorozatot. Az ai jelhez rendelt bináris sorozatot jelöle alfa i. Ilyen módon kapunk egy K = {alfa1,alfa2,...,alfa n} halmazt, melyet kódnak, míg a K halmaz elemeit kódszavaknak nevezzük.
Pl. A={a,b,c,d} K={00,01,101,110}
dac = 11000101
Ha L egy véges halmaz, akkor legyen L csillag az L-ből leképezhető véges sorozatok halmaza. Kódoláskor tulajdonképpen egy M: A a csilladikon -> {0,1}a csilladikon függvényt adunk meg. Ha ez a függvény invertálható, és ismerjük az inverzét, akkor a dekódolás elvégezhető.
PL: K1={00,01,11,0001}
ab -> 0001
d -> 0001
ez a függvény nem invertálható tehát nem dekódolható egyértelműen a kódolt információ.
Itt megadott A->{0,1}a csilladikonra képező függvény még invertálható, de az általa generált A a csilladikon ->{0,1}csilladikon függvény már nem.
Felbontható kódok:
A K={alfa1,alfa2,...,alfan} kódot felbonthatónak nevezzük, ha bármely bináris sorozat egyértelműen felbontható K-beli kódszavak sorozatára. Ha minden egyes betűhöz ugyan olyan hosszúságú kódszót rendelünk, akkor az felbontható kódot eredményez.
PL: K2={00,01,10,11}
Prefix kód:
Egy kódot akkor nevezünk prefix kódnak, ha egyik kódszó sem kezdőszelete semelyik másik kódszónak.
Pl:K,K2
A prefix kódok mind felbonthatók.
Van olyan felbontható kód, ami nem prefix.
Pl: K3={10,100,1000,10000}
McMillan-egyenlőtlenség:
Jelölje l1,l2,...,ln rendre az alfa1,alfa2,...,alfan kódszavak hosszát. Ha a K={alfa1,alfa2,..,alfan} kód felbontható, akkor szumma i=1 tart n-ig 2 a -li-ediken <= 1
Ez csak szükséges, de nem elégséges feltétel
PL: K1={00,01,11,0001}
2 a -2diken + 2 a -2diken + 2 a -2diken + 2 a -4diken = 1/4 +1/4 +1/4+1/16 = 13/16 <= 1
2 kódot akkor nevezünk ekvivalensnek, ha a kódszavak száma ugyanannyi, és a 2 küdban a kódszavak összepárosíthatók úgy, hogy a párok komponenseinek ugyanannyi a hossza. Azaz az egyik kódról a másikra létezik kölcsönösen egyértelmű leképezés, amely egy adott hosszúságú kódszóhoz ugyanolyan hosszúságú kódszót rendel. Minden felbontható kódhoz van vele ekvivalens prefix kód.
Optimális kódok
Adott egy F forrás, melynek kimenő ábécéje A={a1,a2,...,an}  és tudjuk, hogy az F az A jeleit véletlenszerűen, egymástól függetlenül rendre P1,P2,...,Pn valószínűséggel bocsájtja ki. Ekkor szumma i=1től n-ig Pi=1
Egy F által kibácsájtott M jelből álló közlésben az ai jel várhatóan M*Pi-szer fog szerepelni.
Legyen K={alfa1,alfa2,...,alfa n} egy felbontható kód, melyben a kódszavak hossza l1,l2,..,ln. Ekkor az M jelből álló kölésekhez tartozó kód átlagos hossza:
l1*pi*M+l2*Pi*M+...+ln*pi*M = M*(l1*P1+l2*P2+...+li*Pi)=M*szumma i=1 tart n-ig li*Pi
A K0 felbontható kódot az F forrás feletti K felbontható kód esetén L(K0) <= L(K)
Bármely forráshoz található optimális prefix kód.
Az F forrsához tartozó entrópia alatt a M(F) = szumma i=1 tart n-ig Pi* 2esalapúlogaritmus 1/Pi valós számot értjük.
H(F)= - szummha i=1 tart n-ig Pi*log2Pi
Shanon-tétel
Bármely F melletti K felbontható kód esetén H(F) <=L(K)
Ha K0 optimális felbontható kód az F forrásra nézve, akkor L(K0) <= M(F)+1