Diszkrét Matematika II. - Bácsó Sándor

Országok listájaHungaryDebreceni EgyetemInformatikai KarProgramtervező informatikusDiszkrét Matematika 2.JegyzetekDiszkrét Matematika II. - Bácsó Sándor

Bácsó Sándor

Diszkrét Matematika II.

mobiDIÁK könyvtár

Bácsó Sándor

Diszkrét Matematika II.

mobiDIÁK könyvtár SOROZATSZERKESZT Fazekas István

Bácsó Sándor

Diszkrét Matematika II.
egyetemi jegyzet

mobiDIÁK könyvtár Debreceni Egyetem Informatikai Intézet

Lektor Fazekas István

Copyright c Bácsó Sándor, 2003 Copyright c elektronikus közlés mobiDIÁK könyvtár, 2003 mobiDIÁK könyvtár Debreceni Egyetem Informatikai Intézet 4010 Debrecen, Pf. 12 http://mobidiak.unideb.hu

A m egyéni tanulmányozás céljára szabadon letölthet. Minden egyéb felhasználás csak a szerz elzetes írásbeli engedélyével történhet. A m a A mobiDIÁK önszervez mobil portál (IKTA, OMFB-00373/2003) és a GNU Iterátor, a legújabb generációs portál szoftver (ITEM, 50/2003) projektek keretében készült.

Tartalomjegyzék
1. Euklideszi és unitér terek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1. Lineáris, bilineáris és kvadratikus formák . . . . . . . . . . . . . . . . . . . . . . . 2. Euklideszi terek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3. Unitér terek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4. Euklideszi terek lineáris operátorai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5. Unitér terek lineáris operátorai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. Gráfelmélet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1. Gráfelméleti alapfogalmak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. Euler-kör, Euler-vonal, Hamilton-kör . . . . . . . . . . . . . . . . . . . . . . . . . . . 3. Gráfok csúcsmátrixa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3. Kódelmélet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1. Kombinatórikus valószínség . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. Bet szerinti kódolás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3. Felbontható kódok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4. Optimális kódok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5. Optimális kód konstrukciója . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6. Hibajavító kódok zajos csatorna esetén . . . . . . . . . . . . . . . . . . . . . . . . . 7. Lineáris kódok és Hamming kódok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Irodalomjegyzék . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tárgymutató . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 9 21 29 32 41 43 43 49 51 53 53 61 62 63 64 66 67 71 73

7

1. fejezet

Euklideszi és unitér terek
1. Lineáris, bilineáris és kvadratikus formák
1.1. Definíció. Legyen V egy n-dimenziós vektortér az R test felett. Az L : V R lineáris leképezést lineáris formának vagy lineáris funkcionálnak nevezzük. 1.2. Megjegyzés. Az L : V R leképezés lineáris forma, ha 1. additív: a, b V esetén L(a + b) = L(a) + L(b), 2. homogén: a V és R esetén L(a) = L(a). 1.3. Megjegyzés. A V vektortéren értelmezett lineáris formák halmaza vektorteret alkot, melyet V duális terének nevezünk. Jele: V . 1.4. Megjegyzés. Legyen L : V R lineáris forma, és (a) = (a1 , . . . , an ) bázis V -ben. Ekkor egy tetszleges a V vektor esetén ha a = 1 a1 + · · · + n an , akkor
n

L(a) = L(1 a1 + · · · + n an ) = 1 L(a1 ) + · · · + n L(an ) =
l1 ln

i li .
i=1

Ez azt jelenti, hogy elegend ismernünk L hatását a bázisvektorokon, mert az li (i = 1, . . . , n) számok segítségével L tetszleges vektoron felvett értékét meg tudjuk határozni. 1.5. Definíció. Az L : V R lineáris forma (a) = (a1 , . . . , an ) bázisra vonatkozó báziselállításának nevezzük az l 1 , . . . , ln skalárokat, ahol li = L(ai ) (i = 1, . . . , n). 1.6. Következmény. Ha az L : V R lineáris forma (a) bázisra vonatkozó báziselállítása l1 , . . . , ln és a = 1 a1 + · · · + n an , akkor
n

L(a) =
i=1 9

i li .

10

1. EUKLIDESZI ÉS UNITÉR TEREK

1.7. Tétel. Legyen az L : V R lineáris forma (a) = (a1 , . . . , an ) bázisra vonatkozó elállítása l1 , . . . , ln , a (b) = (b1 , . . . , bn ) bázisra vonatkozó elállítása pedig k1 , . . . , kn és legyen a bázistranszformáció mátrixa S : (a) (b). Ekkor l1 k1 . . ha l = . és k = . akkor k = Sl. . . ln kn
n S

Bizonyítás. Ha (a) (b), akkor bj =
n

S

sij ai , így
i=1 n n

kj = L(bj ) = L
i=1

sij ai

=
i=1

sij L(ai ) =
li i=1

sij li = (Sl)j .

1.8. Következmény. Ha megadunk egy l 1 , . . . , ln szám n-est, akkor egy és csak egy olyan lineáris forma létezik, amelynek az (a) rögzített bázisra vonatkozó báziselállítása l1 , . . . , ln . 1.9. Tétel. A V n-dimenziós vektortér V duális vektortere szintén n-dimenziós, és egy bázisát adják azok az M i : V R (i = 1, . . . , n) lineáris formák, amelyeknek az (a) = (a1 , . . . , an ) bázisra vonatkozó báziselállításuk: Mi (aj ) = ij (j = 1, . . . , n) . Bizonyítás. 1. Lineárisan függetlenek: Ha ahol O : V R, O(a) = 0 az azonosan nulla lineáris forma, akkor 1 M1 (aj ) + · · · + j Mj (aj ) + · · · + n Mn (aj ) = O(aj ) = 0,
0 1 0

1 M1 + · · · + n Mn = O,

tehát j = 0 j = (1, . . . , n). 2. Generátorrendszer: Megmutatjuk, hogy egy tetszleges L : V R lineáris forma eláll az M1 , . . . , Mn lineáris formák lineáris kombinációjaként. Legyen a V egy tetszleges vektor, melynek felírása az (a) bázisban: a = 1 a1 + · · · + n an . Ekkor Mi (a) = Mi (1 a1 + · · · + n an ) = 1 Mi (a1 ) + · · · + i Mi (ai ) + · · · + n Mi (an ) = i ,
0 1 0

1. LINEÁRIS, BILINEÁRIS ÉS KVADRATIKUS FORMÁK

11

és L(a) = L(1 a1 + · · · + n an ) =
n n

1 L(a1 ) + · · · + n L(an ) =
M1 (a) l1 Mn (a) ln

li Mi (a),
i=1

tehát L =
i=1

li Mi .

1.10. Definíció. A B : V ×V R leképezést bilineáris formának nevezzük, ha mindkét változójában lineáris: x, y,z V és , R esetén 1. B(x + y, z) = B(x, z) + B(y, z), 2. B(x, y + z) = B(x, y) + B(x, z). 1.11. Megjegyzés. A V vektortéren legyen (a) = (a1 , . . . , an ) egy bázis, és B : V × V R egy bilineáris forma. Ha az x V vektor felírása az (a) bázisban x = x1 a1 +· · ·+xn an , az y V vektoré pedig y = y1 a1 +· · ·+yn an , akkor
n n n n

Tehát elegend ismernünk a bilineáris forma hatását a bázisvektor párokon, mert a cij = B(ai , aj ) R számok segítségével a B tetszleges vektorpáron felvett értékét meghatározhatjuk. 1.12. Definíció. A B : V × V R bilineáris forma mátrixa az (a) = (a1 , . . . , an ) bázisra vonatkozóan a C = (cij ) mátrix, ahol cij = B(ai , aj ). 1.13. Tétel. Legyen a B : V × V R bilineáris forma mátrixa az (a) = (a1 , . . . , an ) bázisra vonatkozóan C és az x, y V vektorok lineáris kombinációként való elállítása az (a) bázisban x = x 1 a1 + · · · + xn an illetve y = y1 a1 + · · · + yn an . Ha x1 y1 . . X = . és Y = . , . . xn yn akkor B(x, y) = X T CY.

B(x, y) = B

xi ai ,

i=1

j=1

yj aj =

xi yj B(ai , aj ) .
cij

i=1 j=1

12

1. EUKLIDESZI ÉS UNITÉR TEREK

Bizonyítás. Az 1.11. megjegyzés szerint
n

B(x, y) =
i=1

c11 . . . . .. xi yj cij = (x1 , . . . , xn ) . . . j=1 cn1 . . .
n



cnn

c1n y1 . . = X T CY. . . . . yn

1.14. Megjegyzés. Egy V n-dimenziós vektortéren értelmezett összes bilineáris formák halmaza vektorteret alkot az alábbi összeadásra és skalárszorzásra nézve: 1. (B1 + B2 )(x, y)=B1 (x, y) + B2 (x, y), 2. (B)(x, y)=B(x, y). Mivel minden bilineáris forma azonosítható a mátrixával (minden bilineáris formát egyértelmen meghatároz a bázisvektor párokon felvett értéke, vagyis a cij számok, és minden C Mn×n mátrix esetén az (x, y) - X T CY leképezés bilineáris forma), így ennek a vektortérnek a dimenziója megegyezik az (n × n)-es mátrixok terének dimenziójával, n 2 -tel.
S

1.15. Tétel. Legyenek (a) = (a1 , . . . , an ) és (b) = (b1 , . . . , bn ) bázisok V -

ben, és a bázistranszformáció mátrixa S : (a) (b). Ha a B : V × V R bilineáris forma mátrixa az (a) bázisban A, a (b) bázisban C, akkor C = S T AS.
n

Bizonyítás. Ha (a) (b), akkor bj =

S

sij ai , így
i=1 n n

Cij = cij = B(bi , bj ) = B(
k=1 n n n

ski ak ,
l=1 n

slj al ) =

ski slj B(ak , al ) =
k=1 l=1 Akl k=1

T Sik l=1

Akl Slj = (S T AS)ij .
(AS)kj

1.16. Következmény. Egy bilineáris forma különböz bázisokban vett mátrixainak rangja megegyezik. Bizonyítás. Mivel egy bázistarnszformáció S mátrixa és annak transzponáltja S T is reguláris és egy reguláris mátrixszal való szorzás nem változtat egy mátrix rangján, így rg(S T AS) = rgA.

1. LINEÁRIS, BILINEÁRIS ÉS KVADRATIKUS FORMÁK

13

1.17. Definíció. Egy bilineáris forma valamely bázisban vett mátrixának a rangját a bilineáris forma rangjának nevezzük. 1.18. Definíció. Egy B : V × V R bilineáris formát szimmetrikusnak nevezzük, ha bármely x, y V esetén B(x, y) = B(y, x). 1.19. Tétel. Egy B : V × V R bilineáris forma akkor és csak akkor szimmetrikus, ha tetszleges bázisban vett mátrixa szimmetrikus. Bizonyítás. 1. Belátjuk, hogy ha B mátrixa valamely bázisban szimmetrikus, akkor minden bázisban az. Legyen B mátrixa az (a) bázisban A, a (b) bázisban C és (a) (b) . Ha A szimmetrikus, azaz AT = A, akkor C T = (S T AS)T = S T AT (S T )T = S T AS = C,
A S S

tehát C is szimmetrikus. 2. Ha B szimmetrikus bilineáris forma és mátrixa az (a) bázisban C = (cij ), akkor
T Cij = cij = B(ai , aj ) = B(aj , ai ) = cji = Cji = Cij ,

tehát C = C T , vagyis C szimmetrikus mátrix. 3. Legyen B mátrixa az (a) bázisban szimmetrikus: c ij = cji . Ekkor tetn n

szleges x, y V vektorok esetén, ha x = akkor
n n

xi ai és y =
i=1 n j=1

yj aj ,

B(x, y) = B
n n i=1 j=1

xi ai ,
i=1 j=1

tehát B szimmetrikus.

xi yj B(aj , ai ) = B



yj aj =
n j=1



n

xi yj B(ai , aj ) =
i=1 j=1 n cij =cji

yj aj ,
i=1

xi ai = B(y, x),



1.20. Megjegyzés. A szimmetrikus bilineáris formák alteret alkotnak a n(n + 1) bilineáris formák vektorterében. Ennek az altérnek a dimenziója , 2 mivel a szimmetrikus mátrixok altere is ennyi dimenziós (a fátlóban és a fátló felett álló elemeket tetszlegesen választhatjuk).

14

1. EUKLIDESZI ÉS UNITÉR TEREK

1.21. Definíció. A B : V × V R szimmetrikus bilineáris formából származó kvadratikus formának nevezzük a Q : V R leképezést: Q(x) = B(x, x) A B(x, y) bilineáris formát a Q(x) kvadratikus forma poláris formájának nevezzük. 1.22. Tétel. A Q : V R kvadratikus forma egyértelmen meghatározza poláris formáját: 1 B(x, y) = (Q(x + y) - Q(x) - Q(y)). 2 Bizonyítás. A B(x, y) szimmetrikus bilineáris forma kifejezhez az alábbi egyenlségbl: Q(x + y) = B(x + y, x + y) = B(x, x) +B(x, y) + B(y, x) + B(y, y) = Q(x) + 2B(x, y) + Q(y),
Q(x) Q(y)

x V.

tehát

1 B(x, y) = (Q(x + y) - Q(x) - Q(y)). 2

1.23. Definíció. A Q(x) kvadratikus forma mátrixa alatt poláris formájának mátrixát értjük. 1.24. Következmény. A B(x, y) szimmetrikus bilineáris formából származó Q(x) kvadratikus forma hatása az x V vektoron: Q(x) = X T CX, ahol C a kvadratikus forma mátrixa az (a) bázisban, X pedig az x vektor (a) bázisbeli koordinátáiból álló oszlopvektor. 1.25. Definíció. A Q : V R kvadratikus formát kanonikus alakúnak nevezzük, ha valamely bázisban az elállítása alakú. Ezt a bázist a Q(x) kvadratikus forma kanonikus bázisának nevezzük. 1.26. Következmény. Egy kvadratikus forma az (a) bázisban pontosan akkor kanonikus alakú, ha mátrixa ebben a bázisban diagonális, mert
n n

Q(x) = 1 x2 + · · · + n x2 1 n

Q(x) = X T CX =
i=1 j=1

cij xi xj

akkor lesz kanonikus alakú, ha i = j esetén c ij = 0.

1. LINEÁRIS, BILINEÁRIS ÉS KVADRATIKUS FORMÁK

15

1.27. Tétel. Lagrange tétel. A V vektortéren értelmezett tetszleges Q(x) kvadratikus forma esetén létezik V -nek olyan bázisa, melyben Q(x) kanonikus alakú. 1.28. Következmény. Minden C Mn×n szimmetrikus mátrixhoz található olyan S Mn×n reguláris mátrix, hogy S T CS diagonális alakú. 1.29. Következmény. Egy kvadratikus forma különböz bázisokban vett mátrixainak a rangja megegyezik.

1.30. Definíció. Egy kvadratikus forma rangján valamely bázisban vett mátrixának rangját értjük. 1.31. Definíció. Egy kvadratikus formát normál alakúnak nevezünk, ha a kanonikus alakjában csak +1, -1 és 0 együtthatók szerepelnek.

1.32. Következmény. Minden kvadratikus formához létezik olyan bázis, amelyben normál alakú.

Bizonyítás. Legyen (a) = (a1 , . . . , an ) az a bázis, melyben a Q(x) kvadratikus forma kanonikus alakú: Q(x) = 1 x2 + · · · + n x2 . Ha tekintjük Q-t n 1 a a1 an (b) = ,..., |1 | |n |
n

báziban, akkor Q(x) =
i=1

i x2 , ahol i {1, -1, 0}. Ekkor az (a) (b) i 1 ... . ... .. 0 . , . . 1
|n |

bázistranszformáció mátrixa: és Q mátrixa a (b) 1 | | .1 T S CS = . . 0 bázisban: ... . ... .. 0 . . . 1
|n |

S=

. . . 0

|1 |


1 |1 |



... .1 . . .. . 0 ... ... .. . ...

. . . 0

n |n |

0 . . . .



1 0 |1 | . . . . . . n 0

... . ... ..

0 . . . 1
|n |



=

16

1. EUKLIDESZI ÉS UNITÉR TEREK

1.33. Tétel (Sylvester-féle tehetetlenségi törvény vagy inercia tétel). Egy kvadratikus forma normál alakjában szerepl +1, -1 és 0 együtthatók száma független a négyzetösszeg alakra hozás módjától. 1.34. Következmény. Minden szimmetrikus C M n×n mátrixhoz létezik olyan S Mn×n reguláris mátrix, hogy S T CS diagonális alakú, és a fátlóban csak +1, -1 és nulla szerepel. 1.35. Tétel. Legyen a V vektortéren értelmezett Q(x) kvadratikus forma mátrixa az (a) bázisban C Mn×n , és jelölje i az i-edik fminor-determinánst: c11 . . . c1i . .. . i = . . . . . . ci1 ... cii Ekkor létezik V -nek olyan (b) kanonikus bázisa, melyben Q(x) = 1 x2 + · · · + n x2 , 1 n ahol 1 = 1 1 n-1 , 2 = , . . . , n = . 1 2 n

1.36. Definíció. A V vektortéren értelmezett Q(x) kvadratikus forma 1. pozitív definit, ha Q(x) > 0 (x = 0) V, 2. negatív definit, ha Q(x) < 0 (x = 0) V, 3. pozitív szemidefinit, ha Q(x) 0 x V, és létezik x = 0 úgy, hogy Q(x) = 0, 4. negatív szemidefinit, ha Q(x) 0 x V, és létezik x = 0 úgy, hogy Q(x) = 0, 5. 5. indefinit, ha Q(x) negatív és pozitív értékeket egyaránt felvesz. 1.37. Példa. Ha az R3 vektortéren értelmezett kvadratikus forma normál alakja 1. Q(x) = x2 + x2 + x2 , akkor Q pozitív definit, 1 2 3 2. Q(x) = -x2 - x2 - x2 , akkor Q negatív definit, 1 2 3 3. Q(x) = x2 +x2 , akkor Q pozitív szemidefinit, mert például Q((0, 0, 1)) = 1 2 0, 4. Q(x) = -x2 -x2 , akkor Q negatív szemidefinit, mert például Q((0, 0, 1)) 1 2 = 0, 5. Q(x) = x2 - x2 + x2 , akkor Q indefinit, mert például Q((1, 0, 0)) > 0 1 2 3 de Q((0, 1, 0)) < 0.

1. LINEÁRIS, BILINEÁRIS ÉS KVADRATIKUS FORMÁK

17

1.38. Következmény. A Q(x) kvadratikus forma akkor és csak akkor pozitív definit, ha kanonikus elállításában minden együtthatója pozitív. 1.39. Következmény. Egy véges dimenziós vektortéren értelmezett pozitív és negatív definit kvadratikus formák rangja megegyezik a vektortér dimenziójával. Bizonyítás. Kvadratikus forma kanonikus bázisban felírt mátrixa diagonális alakú, és az átlóban a kanonikus alakban szerepl együtthatók állnak. Az 1.38. következmény miatt pozitív (negatív) definit kvadratikus forma esetén az átlóban nem szerepelhetnek nullák, így a mátrix determinánsa (az átlóban szerepl elemek szorzata) nem nulla. 1.40. Következmény. A Q(x) kvadratikus forma akkor és csak akkor pozitív definit, ha mátrixának 1 , . . . , n fminor-determinánsa pozitívak. Bizonyítás. Az 1.35. tétel következménye. 1.41. Megjegyzés. Lineáris, bilineáris és kvadratikus formákat a komplex számtest felett is lehet értelmezni, de a definíciójuk és a viselkedésük némileg eltér a valós esettl. A következkben csak ezekre a különbségekre térünk ki, azokat a tulajdonságokat, amelyeket változtatás nélkül át lehet vinni R-rl C-re, nem soroljuk fel. 1.42. Definíció. 1. Legyen V vektortér a C test felett. Az L 1 : V C leképezést elsfajú lineáris formának (vagy funkcionálnak) nevezzük, ha bármely x, y V és C esetén teljesülnek az alábbiak: (a) L1 (x + y) = L1 (x) + L1 (y), (b) L1 (x) = L1 (x). 2. Az L2 : V C leképezést másodfajú lineáris formának nevezzük, ha tetszleges x, y V és C esetén fennáll, hogy (a) L2 (x + y) = L2 (x) + L2 (y), (b) L2 (x) = L2 (x). 1.43. Tétel. Legyen (a) = (a 1 , . . . , an ) egy bázis a V vektortéren és x V egy tetszleges vektor, melynek az (a) bázisbeli felírása: x = x 1 a1 +. . . xn an . Ha L1 : V C egy elsfajú lineáris forma és L 1 (ai ) = li (i = 1, . . . , n) az L1 báziselállítása az (a) bázisra vonatkozóan, akkor
n

L1 (x) =
i=1

xi li .

18

1. EUKLIDESZI ÉS UNITÉR TEREK

Ha L2 : V C egy másodfajú lineáris forma és L 2 (ai ) = ki (i = 1, . . . , n) az L2 báziselállítása az (a) bázisra vonatkozóan, akkor
n

L2 (x) =
i=1

xi ki .

Bizonyítás. Az elsfajú lineáris formára vonatkozó állítás megegyezik a valós esettel, a másodfajú lineáris formára pedig:
n

L2 (x) = L2 (x1 a1 + . . . xn an ) = x1 L2 (a1 ) + · · · + xn L2 (an ) =
k1 kn

xi ki .
i=1

1.44. Definíció. Legyen V egy vektortér a C test felett. A B : V × V C leképezést bilineáris formának nevezzük, ha rögzített y V vektor mellett B(x, y) elsfajú lineáris forma és rögzített x V vektor mellett B(x, y) másodfajú lineáris forma. Másképpen B(x, y) els változójában lineáris, második változójában pedig másodfajú lineáris: 1. B(x + y, z) = B(x, z) + B(y, z) x, y, z V, 2. B(x, y) = B(x, y) x, y V, C, 3. B(x, y + z) = B(x, y) + B(x, z) x, y, z V, 4. 4. B(x, y) = B(x, y) x, y V, C. 1.45. Tétel. Legyen B : V × V C egy bilineáris forma, x, y V tetszleges vektorok melyeknek az (a) = (a 1 , . . . , an ) bázisban a felírása x = x1 a1 + · · · + xn an illetve y = y1 a1 + · · · + yn an . Ha a B bilineáris forma báziselállítása (a)-ra vonatkozóan B(ai , aj ) = cij (i, j = 1, . . . , n), akkor
n n

B(x, y) =
i=1 j=1

cij xi yj .

Másképpen, ha C = (cij ) Mn×n , x1 y1 . . , Y = . X = . . . xn yn
n n

akkor

B(x, y) = X T CY .

Bizonyítás. Az állítás a bilineáris forma definíciójának következménye:
n n

B(x, y) = B

xi ai ,

i=1

j=1

yj aj =

xi yj B(ai , aj ) = X T CY .
cij

i=1 j=1

1. LINEÁRIS, BILINEÁRIS ÉS KVADRATIKUS FORMÁK

19

1.46. Definíció. A B : V × V C bilineáris formát Hermite-szimmetrikus vagy Hermite-féle bilineáris formának nevezzük, ha bármely x, y V vektorok esetén B(x, y) = B(y, x). 1.47. Tétel. Egy B : V × V C bilineáris forma akkor és csak akkor T Hermite-féle, ha mátrixa konjugált szimmetrikus: C = C , vagyis cij = cji . Bizonyítás. 1. Ha B Hermite-féle bilineáris forma, és mátrixa az (a) bázisban C = (cij ), akkor cij = B(ai , aj ) = B(aj , ai ) = cji . 2. Ha cij = cji , akkor tetszleges x, y V esetén
n n n n

B(x, y) =
i=1 j=1 n n

cij xi yj =
i=1 j=1 n n

cji xi yj =

cji xi yj =
i=1 j=1 i=1 j=1

cji yj xi = B(y, x).

1.48. Definíció. Egy B : V × V C Hermite-féle bilineáris formából származó Hermite-féle kvadratikus forma: Q : V C, Q(x) = B(x, x). 1.49. Tétel. Egy Q : V C Hermite-féle kvadratikus forma értéke mindig valós szám. Bizonyítás. Mivel egy z C szám pontosan akkor valós szám ha z = z és B Hermite-szimmetrikus bilineáris forma volt, így Q(x) = B(x, x) = B(x, x) = Q(x) miatt Q(x) R. 1.50. Tétel. Egy Q(x) Hermite-féle kvadratikus forma egyértelmen meghatározza azt az Hermite-szimmetrikus bilineáris formát, amelybl származik: 1 B(x, y) = Q(x + y) - Q(x) - Q(y) + i Q(x + iy) - Q(x) - Q(y) . 2

20

1. EUKLIDESZI ÉS UNITÉR TEREK

Bizonyítás. Elször a bilineáris forma valós részét határozzuk meg: Q(x + y) = B(x + y, x + y) = B(x, x) +B(x, y) + B(y, x) + B(y, y) =
Q(x) B(x,y) Q(y)

Q(x) + Q(y) + B(x, y) + B(x, y),
2ReB(x,y)

ahonnan ReB(x, y) = B(x, y) képzetes része pedig: Q(x + iy) = B(x + iy, x + iy) = B(x, x) + B(x, iy) + B(iy, x) + B(iy, iy) =
Q(x) iB(x,y) iB(y,x) iiB(y,y)

1 (Q(x + y) - Q(x) - Q(y)). 2

Q(x) + Q(y) - iB(x, y) + iB(x, y) = Q(x) + Q(y) - i (B(x, y) - B(x, y)) =
2iImB(x,y)

Q(x) + Q(y) + 2ImB(x, y), ahonnan ImB(x, y) = 1 (Q(x + iy) - Q(x) - Q(y)). 2

1.51. Következmény. Legyen (a) bázis a V vektortéren. Egy Q : V R Hermite-féle kvadratikus forma hatása egy tetszleges vektoron:
n

Q(x) =
i=1

cij xi xj = X T CX.

1.52. Tétel. Legyen V egy vektortér a C test felett. Tetszleges V -n értelmezett Q(x) Hermite-féle kvadratikus forma esetén létezik V -ben olyan bázis, melyben Q(x) kanonikus alakú: Q(x) = 1 x1 x1 + · · · + n xn xn és 1 , . . . , n valós számok.

2. EUKLIDESZI TEREK

21

2. Euklideszi terek
2.1. Definíció. Az E véges dimenziós valós vektorteret Euklideszi térnek nevezzük, ha E-n adott egy olyan szimmetrikus bilineáris forma, melyhez tartozó kvadratikus forma pozitív definit. Ekkor a bilineáris formát E-n definiált bels szorzásnak vagy skaláris szorzásnak nevezzük. Jele: (x, y). 2.2. Definíció. Legyen x E, ekkor x normáján vagy hosszán az x = (x, x) számot értjük. 2.3. Megjegyzés. Mivel a bels szorzathoz (mint bilineáris formához) tartozó kvadratikus forma pozitív definit, így (x, x) 0 miden x E esetén. Ez azt jelenti, hogy a norma definíciójában szerepl (x, x) tetszleges x E esetén értelmezhet.

2.4. Tétel. Az E Euklideszi téren a norma teljesíti az alábbi tulajdonságokat: bármely x E vektor és R esetén: 1. x 0 ; x = 0 x = 0, 2. x = || x .

Bizonyítás. 1. Következik abból, hogy x 2 = (x, x) pozitív definit kvadratikus forma. 2. x = (x, x) = 2 (x, x) = || (x, x) = || x .

2.5. Példa. R3 -ban, ha jelöli az x, y R3 vektorok szögét, akkor bels szorzat, és a természetes báziban felírt x = (x 1 , x2 , x3 ), y = (y1 , y2 , y3 ) vektorok esetén (x, y) = x1 y1 + x2 y2 + x3 y3 . 2.6. Definíció. Azokat az e E vektorokat, melyekre , e = 1 normált vektoroknak nevezzük. x normált vektor. 2.7. Példa. Tetszleges (x = 0) E vektor esetén x 2.8. Definíció. Legyen E Euklideszi tér. Az x, y E nemnulla vektorok szögén a következt értjük: (x, y) = arccos . x y Ekkor egy x R3 vektor normája x2 + x2 + x2 = |x| lesz. 1 2 3 (x, y) = |x||y| cos

22

1. EUKLIDESZI ÉS UNITÉR TEREK

2.9. Megjegyzés. Mivel a definíció szerint cos = -1 (x, y) 1 x y

(x, y) , így x y

fenn kell hogy álljon, de ez a következ, fontos tétel miatt mindig teljesül. 2.10. Tétel (Cauchy-Swarz-Bunyakowszky egyenltlenség). Az E Euklideszi vektortér tetszleges x, y vektoraira teljesül, hogy Egyenlség akkor és csak akkor áll fenn, ha x = µy valamely µ R esetén. Bizonyítás. 1. Tekintsük a 0 x + y x
2 2

|(x, y)| x y .

= (x + y, x + y) = (x, x) + 2 (y, y) + 2(x, y)
2

=

+ 2 y

+ 2(x, y)

egyenltlenséget, amely minden x, y E és R esetén teljesül. Ez ban másodfokú, így akkor és csak akkor teljesülhet, ha a diszkrimináns kisebb vagy egyenl mint nulla (ellenkez esetben a 0 = y 2 2 + 2(x, y) + x 2 másodfokú egyenletnek két különböz valós gyöke van, és ezen két gyök által meghatározott nyílt intervallumban a jobboldal negatív értékeket vesz fel). Tehát 4(x, y)2 - 4 x (x, y)2 x
2 2

y

2

0,

y 2,

2. Egyenlség pontosan akkor teljesül valamely x, y esetén, ha a diszkrimináns nulla. Ekkor a 0 = x + y 2 másodfokú egyenletnek pontosan egy 1 megoldása van és erre x + 1 y = 0 , tehát x és y lineárisan függek. 2.11. Tétel (Minkowski egyenltlenség vagy háromszög egyenltlenség). Az E Euklideszi tér tetszleges x, y vektoraira fennáll, hogy és x+y = x + y x+y x + y ha létezik 0 : x = y.

|(x, y)| x y .

2. EUKLIDESZI TEREK

23

Bizonyítás. 1. A Cauchy-Swarz-Bunyakowszky egyenltlenséget használva x+y
2

= (x + y, x + y) = x x
2

2

+ y

2

+ 2(x, y)

+ y

2

+ 2 x y = ( x + y )2 .

2. Egyenlség akkor és csak akkor áll fenn, ha (x, y) = x y , aminek szükséges feltétele, hogy x és y lineárisan függ legyen. Ha x = y, akkor (x, y) = (y, y) = y 2 , így < 0 esetén (x, y) < 0 x y miatt nem teljesülhet az egyenlség. 2.12. Következmény. Ha xi , yi R (i = 1, . . . , n), akkor
n 2 n n

xi yi
i=1



x2 i
i=1 i=1

2 yi .

Bizonyítás. A 2.5. példában szerepl bels szorzatra felírva a Cauchy-SwarzBunyakowszky egyenltlenséget adódik az állítás. 2.13. Megjegyzés. Egy V vektorteret normált térnek nevezzük, ha adva van rajta egy : V R leképezés (norma), amely teljesíti az alábbi tulajdonságokat: bármely x, y V és T esetén 1. x 0 és x = 0 ha x = 0, 2. x = || x . 3. x + y x + y . Az Euklideszi terek a bels szorzatból származó normával normált teret alkotnak a 2.4. tétel és a Minkowsky egyenltlenség szerint, de nem minden normált tér Euklideszi tér. 2.14. Definíció. Az E Euklideszi tér x és y vektorainak távolsága: d(x, y) = x - y 2.15. Következmény. Tetszleges x, y, z E vektorok esetén: Bizonyítás. Az állítás a Minkowsky egyenltlenség felírva az x - y és z - y vektorokra: d(x, z) = x-z = (x-y)-(z -y) x -y + z -y = d(x, y)+d(y, z). d(x, z) d(x, y) + d(y, z).

24

1. EUKLIDESZI ÉS UNITÉR TEREK

2.16. Megjegyzés. A V vektorteret metrikus térnek nevezzük, ha adva van rajta egy d : V × V R leképezés (metrika), amely teljesíti az alábbi tulajdonságokat: bármely x, y, z V esetén 1. d(x, y) 0 és d(x, y) = 0 ha x = y, 2. d(x, y) = d(y, x), 3. d(x, z) d(x, y) + d(y, z).

Minden normált tér metrikus tér a d(x, y)= x - y metrikával (természetesen az Euklideszi tereken a bels szorzatból származó norma segítségével definiált távolságfüggvény eleget tesz a metrika követelményeinek), de nem minden metrikus tér normált tér. 2.17. Definíció. Az E Euklideszi vektortér x és y vektorait merlegesnek vagy ortogonálisnak nevezzük, ha (x, y) = 0 . Jele: xy. 2.18. Következmény. A nullvektor minden E-beli vektorra merleges. 2.19. Definíció. Az (a1 , . . . , ak ) E-beli vektorrendszert ortogonálisnak nevezzük, ha vektorai páronként merlegesek egymásra, azaz a i aj , (i, j = 1, . . . , k) i = j. 2.20. Definíció. Az (e1 , . . . , ek ) E vektorrendszer ortonormált, ha vektorai páronként merlegesek és normáltak: ei ej (i, j = 1, . . . , k) i = j, ei = 1 (i = 1, . . . , k). Másképpen (e i , ej ) = ij (i, j = 1, . . . , k). 2.21. Tétel (Pythagoras tétel). Legyen E Euklideszi vektortér. Az x, y E vektorok akkor és csak akkor merlegesek egymásra, ha x+y Bizonyítás. Mivel x+y
2 2

= x

2

+ y 2.
2

= (x + y, x + y) = x
2

+ y

2

+ 2(x, y), így

1. ha xy, akkor (x, y) = 0 miatt x+y 2. ha x+y
2

= x

2

+ y 2,

= x

2

+ y 2 , akkor 2(x, y) = 0 miatt xy .

2.22. Tétel. Ha (e1 , . . . , ek ) E ortonormált vektorrendszer, akkor lineárisan független vektorrendszer. Bizonyítás. Belátjuk, hogy a nullvektor csak triviális lineáris kombinációként állítható el az e1 , . . . , ek vektorokból. Ha 0 = 1 e1 + · · · + k ek , akkor 0 = (0, ei ) = (1 e1 + · · · + k ek , ei ) =

2. EUKLIDESZI TEREK

25

1 (e1 , ei ) + · · · + i (ei , ei ) + · · · + k (ek , ei ) = i
0 1 0

teljesül minden i {1, . . . , k} esetén. 2.23. Definíció. Az (e1 , . . . , en ) E ortonormált vektorrendszert ortonormált bázisnak nevezzük, ha generátorrendszere E-nek, azaz ha E egy ndimenziós Euklideszi tér. 2.24. Tétel (Gram-Schmidt-féle ortogonalizációs eljárás). Az E Euklideszi tér tetszleges (a) = (a 1 , . . . , an ) bázisához létezik olyan (e) = (e1 , . . . , en ) ortonormált bázisa E-nek, hogy L(a1 , . . . , ak ) = L(e1 , . . . , ek ) (k = 1, . . . , n). Bizonyítás. Adunk egy gyakorlatban is jól használható eljárást az (e) bázis megkonstruálására. a 1. Legyen e1 = 1 , ekkor természetesen L(a 1 ) = L(e1 ) , és e1 normált a1 vektor. 2. Ha már létezik e1 , . . . , ek ortonormált rendszer, melyre L(a1 , . . . , ak ) = L(e1 , . . . , ek ), akkor legyen az ek+1 vektor a következ: ek+1 = ak+1 - (ak+1 , e1 )e1 - · · · - (ak+1 , ek )ek . Ekkor ennek a vektornak a normáltja megfelel lesz: ha ek+1 = akkor (a) e1 , . . . , ek , ek+1 ortonormált rendszer, mert (ek+1 , ei ) = 1 ek+1 (ak+1 , ei ) - (ak+1 , e1 ) (e1 , ei ) - · · · - (ak+1 , ei ) (ei , ei )
0 1

ek+1 , ek+1

- · · · - (ak+1 , ek ) (ek , ei )
0

=

1 ek+1

(ak+1 , ei ) - (ak+1 , ei ) = 0,

(b)

L(a1 , . . . , ak+1 ) = L(e1 , . . . , ek+1 ), mert ek+1 -et az e1 , . . . , ek , ak+1 vektorok lineáris kombinációjaként állítottuk el.

2.25. Következmény. Minden ortonormált vektorrendszer kiegészíthet ortonormált bázissá.

26

1. EUKLIDESZI ÉS UNITÉR TEREK

2.26. Tétel. Legyen az E Euklideszi téren (e) = (e1 , . . . , en ) ortonormált bázis és az x, y E vektorok felírása az (e) bázisban x = x 1 e1 + · · · + xn en illetve y = y1 e1 + · · · + yn en . Ekkor
n

(x, y) =
i=1

xi yi .

Bizonyítás. A bels szorzat bilinearitása miatt
n n n

(x, y) = (x1 e1 +· · ·+xn en , y1 e1 +· · ·+yn en ) =

xi yj (ei , ej ) =
i=1 j=1 ij i=1

xi yj .

2.27. Tétel. Legyen (e) = (e 1 , . . . , en ) ortonormált bázis az E Euklideszi vektortéren, és x E. Ekkor az x vektor úgynevezett Fourier elállítása:
n

x=
i=1

(x, ei )ei .

Bizonyítás. Ha az x vektor felírása az (e) bázisban x = x 1 ei + · · · + xn en , akkor
n

(x, ei ) = (x1 e1 + · · · + xn en , ei ) =
n n

xi (ej , ei ) = xi ,
j=1 ij

tehát x =
i=1

xi ei =
i=1

(x, ei )ei .

2.28. Tétel. Ha (e) = (e1 , . . . , en ) ortonormált bázis az E Euklideszi téren és x E, akkor 1. Bessel egyenltlenség:
k i=1

(x, ei )2 x

2

1 k n,

2. Parseval egyenlség:
n

(x, ei )2 = x 2 .
i=1

2. EUKLIDESZI TEREK

27

Bizonyítás. Felhasználva, hogy (x, e i ) = xi és a 2.26. tétel alapján
n n k n

x

2

= (x, x) =
i=1 k

x2 = i
i=1

(x, ei )2 =
i=1

(x, ei )2 +
i=k+1

(x, ei )2



(x, ei )2 .
i=1

2.29. Definíció. Azt mondjuk, hogy az E 1 és az E2 Euklideszi vektorterek izometrikusan izomorfak, ha létezik : E 1 E2 bijektív leképezés, amely megtartja a bels szorzatot, azaz (x, y)1 = ((x), (y))2 ahol (, )1 jelöli az E1 -beli bels szorzást és (, )2 pedig az E2 -belit. 2.30. Tétel. Minden n-dimenziós Euklideszi vektortér izometrikusan izomorf a 2.5. példában szerepl bels szorzással ellátott R n -el. Bizonyítás. Már beláttuk, hogy minden n-dimenziós vektortér izomorf R n el és az izomorfizmust a koordinátaleképezés valósítja meg (lásd Diszkrét Matematika 1. 5. fejezet). Belátjuk, hogy ez a leképezés megtartja a bels szorzatot. Legyen E-ben (a) = (a1 , . . . , an ) ortonormált bázis és az x, y E vektorok felírása (a)-ben x = x1 a1 +· · ·+xn an illetve y = y1 a1 +· · ·+yn an . Rn -ben legyen (e) = (e1 , . . . , en ) a kanonikus bázis, a koordinátaleképezés pedig (x) = x1 e1 + · · · + xn en = (x1 , . . . , xn ). Ha az E-beli bels szorzást (, )1 jelöli és az R-beli bels szorzást (, ) , akkor
n

x, y E1 ,

(x, y)1 =
i=1

xi yi ,
n

((x), (y)) = ((x1 , . . . , xn ), (y1 , . . . , yn )) =
i=1

xi yi .

2.31. Következmény. Két Euklideszi tér pontosan akkor izomorf, ha dimenziójuk megegyezik. 2.32. Tétel. Legyen E Euklideszi tér és x E. Ekkor az x vektorra merleges vektorok halmaza alteret alkot E-ben.

28

1. EUKLIDESZI ÉS UNITÉR TEREK

Bizonyítás. 1. Ha ax és bx, azaz (a, x) = 0, (b, x) = 0, akkor (a + b, x) = (a, x) + (b, x) = 0 + 0 = 0, tehá a + bx. 2. Ha ax vagyis (a, x) = 0 akkor (a, x) = (a, x) = 0, tehát ax. 2.33. Példa. R3 -ban az e3 = (0, 0, 1) vektorra merleges vektorok halmaza az {(x, y, 0) | x, y R} sík. 2.34. Definíció. Legyen H egy altér az E Euklideszi térben. A H altér ortogonális komplementerének nevezzük azon vektorok halmazát, amelyek H minden vektorára merlegesek. Jele H . 2.35. Tétel. Legyen E Euklideszi tér és H E altér. Ekkor H is altér. (x + y, h) = (x, h) + (y, h) = 0 + 0 = 0 tehá x + y H . 2. Ha x H vagyis (x, h) = 0 0 h H, tehát x H . h H, h H, akkor H = {x E | xh h H}.

Bizonyítás. 1. Ha x, y H azaz (x, h) = 0, (y, h) = 0

h H, akkor (x, h) = (x, h) =

Bizonyítás. 1. és 2. nyilvánvaló. 3. egyen e1 , . . . , ek otonormált bázisa H-nak (ilyen a Gram-Schmidt ortogonalizációs eljárással megadható) és (e) = (e1 , . . . , ek , . . . , en ) ennek kiegészítése E ortonormált bázisává. Ekkor minden x E egyértelmen felírható (e)-beli elemek lineáris kombinációjaként: x = x1 e1 + · · · + xk ek + xk+1 ek+1 + · · · + xn en ,
x H x H

2.36. Következmény. Legyen H altér az E Euklideszi térben. Ekkor 1. x H akkor és csak akkor, ha x merleges H minden bázisvektorára. 2. H ortogonális komplementerének az ortogonális komplementere is altér. 3. (H ) = H és H H = E .

tehát minden x E egyértelmen felírható x = x +x alakban, ahol

Ez pontosan azt jelenti, hogy E = H H .

x H, x H .

3. UNITÉR TEREK

29

2.37. Definíció. Ha H altér az E Euklideszi vektortérben, és x = x + x , ahol x H és x H , akkor az x vektornak a H altértl vett távolságán az x számot értjük. 2.38. Megjegyzés. Legyen E Euklideszi tér és H egy altere. Az x vektor x = x +x x H, x H felbontásában az x komponens nem más mint x merleges vetülete a H altérre, x pedig x merleges vetülete a H altérre. Ha (e) = (e1 , . . . , en ) otronormált bázis és H = L(e 1 , . . . , ek ) , akkor a Fourier elállítást használva a merleges vetületek egyszeren kiszámíthatók: x
T

H x
T

x = x1 e1 + · · · + xn en = (x, e1 )e1 + · · · + (x, en )en x = (x, e1 )e1 + · · · + (x, ek )ek

e3 e E2

B

x = (x, ek+1 )ek+1 + · · · + (x, en )en e1


q x

H

3. Unitér terek
3.1. Megjegyzés. Mivel az Unitér terek és az Euklideszi terek között sok hasonlóság van, azokat a bizonyításokat amelyek változtatásnélkül vihetk át Unitér terekre, nem írjuk le. 3.2. Definíció. Legyen U vektortér C felett és (, ) : U × U C leképezés olyan, hogy bármely x, y, z U és C esetén 1. 2. 3. 4. (x, y) = (y, x), azaz Hermite-szimmetrikus, (x, y) = (x, y), azaz els változójában homogén, (x + y, z) = (x, z) + (y, z), azaz els változójában additív, (x, x) 0 és (x, x) = 0 x = 0.

Ekkor azt mondjuk, hogy U unitér tér az (x, y) bels szorzással ellátva.

30

1. EUKLIDESZI ÉS UNITÉR TEREK

3.3. Következmény. Ha U unitér tér az (x, y) bels szorzással, akkor minden x, y, z U és C esetén 1. (x, y) = (x, y), 2. (x, y + z) = (x, y) + (x, z), 3. (x, x) valós szám.

Bizonyítás. 1. (x, y) = (y, x) = (y, x) = (y, x) = (x, y), 2. (x, y + z) = (y + z, x) = (y, x) + (z, x) = (y, x) + (z, x) = (x, y) + (x, z), 3. Az (x, y) = (y, x) egyenlségbe y helyébe is x-et írva (x, x) = (x, x), tehát (x, x) egyenl a konjugáltjával, így valós szám. 3.4. Következmény. Ha az U komplex számtest felett értelmezett vektortéren megadunk egy Hermite-féle bilineáris formát, melybl származó kvadratikus forma pozitív definit, akkor ezáltal egy bels szorzást definiáltunk, és minden Unitér téren adott bels szorzás Hermite-szimmetrikus bilineáris forma, amelyhez tartozó kvadratikus forma pozitív definit. 3.5. Definíció. Egy U Unitér tér tetszleges x elemének hossza vagy normája az x = (x, x) valós szám. 3.6. Definíció. Az U Unitér tér x és y vektorait merlegesnek vagy ortogonálisnak nevezzük, ha (x, y) = 0. 3.7. Definíció. Az (e) = (e 1 , . . . , en ) U vektorrendszert ortonormáltnak nevezzük, ha páronként merleges egységvektorok: (e i , ej ) = ij (i, j = 1, . . . , n). 3.8. Tétel. Egy U Unitér tér ortonormált vektorrendszerének tagjai lineárisan függetlenek. 3.9. Megjegyzés. A Gram-Schmidt-féle ortogonalizációs eljárás Unitér tereken ugyanúgy végrehajtható, mint Euklidesz tereken. 3.10. Tétel. Legyen az U Unitér téren (e) = (e 1 , . . . , en ) ortonormált bázis és az x, y U vektorok felírása az (e) bázisban x = x 1 e1 + · · · + xn en illetve y = y1 e1 + · · · + yn en . Ekkor
n

(x, y) =
i=1

xi yi .

3. UNITÉR TEREK

31

Bizonyítás. A bels szorzat bilinearitása miatt
n n n

(x, y) = (x1 e1 +· · ·+xn en , y1 e1 +· · ·+yn en ) =

xi yj (ei , ej ) =
i=1 j=1 ij i=1

xi yj .

3.11. Tétel. Legyen (e) = (e 1 , . . . , en ) ortonormált bázis az U Unitér vektortéren, és x U. Ekkor az x vektor úgynevezett Fourier elállítása:
n

x=
i=1

(x, ei )ei .

3.12. Tétel. Ha (e) = (e1 , . . . , en ) ortonormált bázis az U Unitér téren és x, y U, akkor 1. Bessel egyenltlenség:
k i=1

|(x, ei )|2 x

2

1 k n,

2. Parseval egyenlség:
n i=1

|(x, ei )|2 = x 2 .

3. Cauchy-Swarz-Bunyakowszky egyenltlenség: |(x, y)| x y . Bizonyítás. Felhasználva, hogy (x, e i ) = xi és a 3.10. tétel alapján
n n k n

x

2

= (x, x) =
k

xi xi =
i=1 |x | i i=1

|(x, ei )| =

2

i=1

|(x, ei )| +

2

i=k+1

|(x, ei )|2



i=1

|(x, ei )|2 .

3.13. Tétel. Ha H altér az U Unitér téren és H jelöli az ortogonális komplementerét, akkor H H = U és (H ) = H.

32

1. EUKLIDESZI ÉS UNITÉR TEREK

4. Euklideszi terek lineáris operátorai
4.1. Tétel. Legyen E egy véges dimenziós Euklideszi tér és : E E egy lineáris operátor. Ekkor -nek létezik egy- vagy két-dimenziós invariáns altere. Bizonyítás. Legyen mátrixa valamely bázisban A, és tekintsük a lineáris leképezés karakterisztikus egyenletének (amely független a bázis megválasztásától) egy gyökét, azaz |A - E| = 0. 1. Ha valós gyök, akkor sajátérték és létezik x E úgy, hogy (x) = x. Ekkor a x sajátvektor által generált L(x) egy dimenziós altér invariáns. 2. Ha = + i = 0 komplex gyök, akkor tekintsük E-t egy idre C-feletti vektortérként, és -t pedig mint ezen a vektortéren értelmezett lineáris transzformációt (az eredeti bázisra vonatkozó A mátrixszal). A skalártartománynak ezen kibvítése természetesen csak egy absztrakció amire azért van szükségünk, mert a komplex esetben sajátértéke -nek, így létezik hozzá a sajátvektor, és ennek segítségével fogjuk megkonstruálni E-nek egy két dimenziós invariáns alterét. Legyen x az a vektor melynek koordinátái az a vektor koordinátáinak valós részei, és y koordinátái legyenek az a koordinátáinak képzetes részei. Ekkor a = x + iy, ahol x, y E valós vektorok. Mivel (a) = (a) = (x + iy) = ( + i)(x + iy) = x - y + i(x + y) illetve így (4.1) (4.2) (x) = x - y, (y) = x + y. (a) = (x + iy) = (x) + i(y),

Belátjuk, hogy x, y nem nullvektorok és lineárisan függetlenek. (a) Ha x = 0 lenne, akkor (x) = 0, amibl (4.1) miatt y = 0 következik. Ekkor a = 0, ami ellentmond annak, hogy a sajátvektor volt. (b) Ha y = 0, akkor (y) = 0, amibl (4.2) miatt x = 0, igy a nullvektor lenne, ami ellentmondás.

4. EUKLIDESZI TEREK LINEÁRIS OPERÁTORAI

33

(c)

Indirekt tegyük fel, hogy x, y lineárisan függ vektorok, azaz létezik olyan = 0 szám, amire y = x. Ekkor (4.2)-bl és (4.1)-bl (x) = x + x, Kivonva az els egyenlet -szorosát a másodikból (1+ 2 )(x) = (1 + 2 ) x , tehát (x) = x, ami (4.1) miatt azt jelenti, hogy (x) = x - x.

y = 0, és ez ellentmond annak, hogy sem sem y nem nulla. Ezzel beláttuk, hogy az L(x, y) két-dimenziós, és (4.1),(4.2) szerint ez invariáns altér E-ben. 4.2. Tétel. Legyen E egy Euklideszi vektortér és , : E E lineáris operátorok. Ha bármely x, y E esetén (x, (y)) = (x, (y)), akkor . Bizonyítás. Ha teljesülnek a tétel feltételei, akkor 0 = (x, (y)) - (x, (y)) = (x, (y) - (y)) = (x, ( - )(y)), ami x := ( - )(y) esetén azt jelenti, hogy 0 = (( - )(y), ( - )(y)) = ( - )(y) 2 . Ekkor ( - )(y) = 0 vagyis (y) = (y). Mivel y tetszleges volt, így . 4.3. Definíció. Legyen : E E lineáris operátor az E Euklideszi téren. A : E E lineáris operátort a adjungáltjának nevezzük, ha bármely x, y E esetén ((x), y) = (x, (y)). 4.4. Tétel. Az E Euklideszi tér tetszleges : E E lineáris operátorának egyértelmen létezik adjungált operátora. Ha az E egy ortonormált bázisában mátrixa A, akkor ebben a bázisban mátrixa AT . Bizonyítás. Legyen az E Euklideszi térnek (e) = (e1 , . . . , en ) egy ortonormált bázisa és ebben a bázisban mátrixa A = (a ij ) és mátrixa A =

=0

34

1. EUKLIDESZI ÉS UNITÉR TEREK n

(a ). ij

Ekkor (ei ) =
k=1

aik ek , így
n n

((ei ), ej ) =
k=1

aik ek , ej
n

=
k=1 n

aik (ek , ej ) = aij ,
kj

(ei , (ej )) = a , ji A



ei ,
k=1

a ek jk

=
k=1

a (ei , ek ) = a . ji jk
ki

Innen aij = tehát = szükséges. A bels szorzat bilinearitása és linearitása miatt ha a bázisvektorokra teljesül, hogy ((e i ), ej ) = (ei , (ej )), akkor ez tetszleges x, y E vektorokra is teljesül. Ekkor az a lineáris transzformáció melynek mátrixa az (e) bázisban A T , eleget tesz az adjungált operátor definíciójában szerepl követelményeknek. Ha két adjungált operátor is létezne, akkor bármely x, y E esetén ((x), y) = (x, (y)) = (x, (y)) teljesülne, ami a 4.2. tétel miatt csak akkor lehetséges, ha . Tehát adjugált oprátor minden lineáris transzformáció esetén létezik, egyértelm és ortonormált bázis esetén mátrixa a mátrixának transzponáltja. 4.5. Tétel. Legyenek és lineáris operátorok az E Euklideszi téren, Id pedig legyen az identikus transzformáció. Ekkor 1. Id = Id , 2. ( ) = , 3. ( + ) = + , 4. ( ) = , 5. ha invertálható, akkor (-1 ) = ( )-1 . Bizonyítás. Legyen x, y E tetszleges. Ekkor 2. (x, ( ) (y)) = ( (x), y) = (y, (x)) = ((y), x) = (x, (y)), 3. (x, ( + ) (y)) = (( + )(x), y) = ((x) + (x), y) = ((x), y) + ((x), y) = (x, (y)) + (x, (y)) = (x, (y) + (y)) = (x, ( + )(y)), 4. (x, ( ) (y)) = (( )(x), y) = (((x)), y) = ((x), (y)) 5. a 3. tulajdonság miatt = (x, ( (y))) = (x, ( )(y)),

AT

(-1 ) = (-1 ) = Id = Id.

4. EUKLIDESZI TEREK LINEÁRIS OPERÁTORAI

35

Megjegyezzük, hogy a tétel következménye a mátrixok transzponáltjára vonatkozó tulajdonságoknak is, hiszen az adjungált operátorok azonosíthatóak a mátrixukkal, ami éppen az eredeti operátor mátrixának transzponáltja. 4.6. Definíció. Az E Euklideszi tér : E E lineáris operátorát önadjungált vagy szimmetrikus operátornak nevezzük, ha = , azaz az operátor adjungáltja saját maga. 4.7. Következmény. Legyen a : E E lineáris operátor mátrixa az E Euklideszi tér egy ortonormált bázisában A. akkor és csak akkor lesz önadjungált operátor, ha A = AT , azaz mátrixa tetszleges ortonormált bázisban szimmetrikus. 4.8. Tétel. Legyenek , : E E önadjungált operátorok, Id pedig az identikus leképezés az E Euklideszi téren. Ekkor 1. Id = Id , tehát Id önadjungált, 2. ( + ) = + , önadjungált operátorok összege is az, 3. ( ) = akkor és csak akkor teljesül, ha és felcserélhet, azaz ha = . Bizonyítás. Az állítások a 4.5. tétel következményei. 4.9. Példa. 1. Egy = 0 skalárral való nyújtás önadjungált operátor: (x) = x x E (lásd 2.38. megjegyzés) esetén ((x), y) = (x, y) = (x, y) = (x, y) = (x, (y)). 2. Egy H E altérre történ merleges vetítés önadjungált operátor: (x) = x , ahol x H és x = x - x H esetén ((x), y) = (x , y) = ( x , y + y ) = (x , y ) + (x , y ) = (x , y )
H H H 0

(x, (y)) = (x, y ) = (x + x , y ) = (x , y ) + (x , y ) = (x , y ) ,
0

tehát ((x), y) = (x, (y)), azaz valóban önadjungált. 4.10. Tétel. Ha H a önadjungált operátor invariáns altere, akkor H is invariáns altér. Bizonyítás. Legyen x H és belátjuk, hogy (x) is H eleme, azaz ((x), h) = 0 minden h H esetén. Mivel önadjungált és H invariáns altér, így ((x), h) = ( x , (h)) = 0.
H H

36

1. EUKLIDESZI ÉS UNITÉR TEREK

4.11. Tétel. Egy : E E önadjungált lineáris operátor karakterisztikus egyenletének minden gyöke valós. Bizonyítás. Indirekt tegyük fel, hogy létezik = + i ( = 0) nem valós gyök. Ekkor a 4.1. tétel bizonyításában leírtak alapján léteznek x, y E nem nulla vektorok úgy, hogy (y) = x + y, így ((x), y) = (x - y, y) = (x, y) - (y, y) (x, (y)) = (x, x + y) = (x, x) + (x, y). Mivel önadjungált, ezért az egyenletek baloldalai megegyeznek, és a jobboldalakat egyenlvé téve ((x, x) + (y, y)) = 0
=0 =0 =0

(x) = x - y

adódik, ami ellentmondás. 4.12. Következmény. Önadjungált lineáris operátor spektruma teljes. 4.13. Tétel (Struktúratétel). Ha : E E önadjungált lineáris operáror az E véges dimenziós Euklideszi téren, akkor E-ben létezik sajátvektoraiból álló ortonormált bázis. Bizonyítás. E dimenziója szerinti teljes indukciót alkalmazunk. Ha dim E = 1, akkor az állítás nyilvánvaló. Tegyük fel, hogy a tétel igaz minden n-nél kisebb dimenziós Euklideszi tér esetén, és legyen most E ndimenziós. Tekintsük egy x E sajátvektorát a önadjungált operátornak (ilyen létezik a 4.12. következmény miatt). Ekkor a H := L(x) altér invariáns, és a 4.10. tétel szerint H szintén invariáns altér. Mivel H 1-dimenziós altér, ezért H (n - 1)-dimenziós Euklideszi tér, így az indukciós feltevés szerint létezik olyan (e 1 , . . . , en-1 ) ortonormált bázisa amely sajátvektoraiból áll. Az x sajátvektor merleges a H altér miden vektorára, így x e1 , . . . , en-1 , ortonormált bázis lesz E-ben. x 4.14. Megjegyzés. Mivel sajátvektorokból álló bázisban a lineáris transzformációk mátrixai diagonális alakúak, így a Struktúratétel szerint minden önadjungált operátor mátrixa diagonalizálható.

4. EUKLIDESZI TEREK LINEÁRIS OPERÁTORAI

37

4.15. Tétel (Ftengelytranszformációs tétel). Egy véges dimenziós Euklideszi téren adott Q(x) kvadratikus formához létezik olyan ortonormált bázis, amelyben a kvadratikus forma kanonikus alakú, és az ebben szerepl együtthatók a kvadratikus forma tetszleges bázisra vonatkozó mátrixának sajátértékei. Bizonyítás. Legyen (b) ortonormált bázis E-ben, és tegyük fel, hogy Q(x) mátrixa (b)-ben A. Legyen az a lineáris transzformáció, amelynek mátrixa (b)-ben A. Mivel A szimmetrikus mátrix, így önadjungált leképezés, tehát létezik sajátvektoraiból álló (e) = (e 1 , . . . , en ) ortonormált bázis. Ha a sajátvektorokhoz tartozó sajátértékek 1 , . . . , n , akkor
n

Q(x) = X AX = (x, (x)) =
(x) n n

T

x,
i=1 n

xi e i i x2 , i
i=1

=

xi (x, (ei )) =
i=1 i ei i=1

i xi (x, ei , ) =
xi

azaz Q(x) az (e) bázisban kanonikus alakú, és a kanonikus alakban szerepl együtthatók a kvadratikus forma mátrixának sajátértékei. 4.16. Következmény. Minden szimmetrikus mátrix diagonalizálható, azaz hasonló egy diagonális mátrixhoz. A hasonlóságot egy olyan S mátrix valósítja meg, amelynek oszlopaiban egymásra merleges egységhosszú vektorok koordinátái szerepelnek, az ilyen mátrixot a késbbiekben ortogonális mátrixnak fogjuk nevezni. 4.17. Definíció. Az E Euklideszi téren adott : E E lineáris transzformációt ortogonálisnak nevezzük, ha bármely x, y E esetén (x, y) = ((x), (y)). 4.18. Következmény. Mivel az ortogonális transzformációk megtartják a bels szorzatot, így megrzik a vektorok normáját és szögét is. 4.19. Tétel. Ha egy : E E lineáris transzformáció megtartja a vektorok normáját (azaz tetszleges x E esetén (x) = x ), akkor ortogonális transzformáció. Bizonyítás. Ha normatartó, akkor x, y E esetén, így (x+y)
2

(x + y) = x + y teljesül minden

= ((x+y), (x+y)) = ((x), (x)) +2((x), (y))+((y), (y))
(x)
2

(y)

2

38

1. EUKLIDESZI ÉS UNITÉR TEREK

= (x) és

2

+ 2((x), (y)) + (y)
2

2

= x

2

+ 2((x), (y)) + y
2

2

(x + y)

= x+y

2

= (x + y, x + y) = x

+ 2(x, y) + y

2

alapján 2((x), (y)) = 2(x, y) adódik, így ortogonális. 4.20. Tétel. A : E E lineáris operátor akkor és csak akkor ortogonális transzformáció, ha ortonormált bázist ortonormált bázisba visz át. Bizonyítás. 1. Ha ortogonális transzformáció, akkor szögtartó és normatartó, tehát merleges vektorokat merleges vektorokba visz és normált vektorokat normált vektorokba. 2. Ha az (e) = (e1 , . . . , en ) ortonormált bázist ortonormált bázisba viszi, akkor
n n n n n

és

(x, y) =

xi ei ,

i=1

j=1

yj e j =
n

xi yj (ei , ej ) =
ij

xi yi

i=1 j=1

i=1

((x), (y)) = =


n

n

xi (ei ),
i=1 n j=1

yj (ej )
ij


n

xi yj ((ei ), (ej )) =
i=1 j=1 i=1

xi yi ,

tehát belsszorzat-tartó, így ortogonális. 4.21. Következmény. A : E E ortogonális lineáris operátor mátrixa reguláris. Bizonyítás. Mivel ortogonális operátor bázist bázisba visz, így a (E) képtér n-dimenziós lesz, tehát szürjektív. Ez ekvivalens azzal, hogy automorfizmus, és ekkor mátrixa reguláris. 4.22. Tétel. A : E E lineáris operátor akkor és csak akkor ortogonális, ha = -1 . Bizonyítás. 1. Ha ortogonális transzformáció, akkor (x, y) = ((x), (y)) = (x, (y)) miatt Id = , tehát = -1 .

4. EUKLIDESZI TEREK LINEÁRIS OPERÁTORAI

39

2. Ha = -1 teljesül, akkor ((x), (y)) = (x, (y)) = (x, y).
-1 =Id

4.23. Következmény. Ha : E E ortogonális operátor, akkor mátrixa az E egy tetszleges ortonormált bázisában olyan, hogy A T = A-1 . Az ilyen mátrixokat ortogonális mátrixoknak nevezzük. Ha mátrixa valamely ortonormált bázisban ortogonális, akkor ortogonális transzformáció. 4.24. Következmény. Ha a : E E ortogonális operátor mátrixa valamely bázisban A, akkor | det A| = 1. Bizonyítás. Mivel hasonló mátrixok determinánsa megegyezik, így elegend ortonormált bázis esetén bizonyítani az állítást. Ekkor A T = A-1 miatt AAT = E, és 1 = det E = det(AAT ) = det A det AT = (det A)2 .
det A

4.25. Következmény. Ortogonális mátrix sor illetve oszlopvektorai ortonormált bázist alkotnak Rn -ben.
n

Bizonyítás. Mivel AAT = E, ezért
k=1

aik aT = (ai , aj ) = ij , tehát az A kj

mátrix sorvektorai egymásra merleges egységhosszú vektorok. 4.26. Példa. R2 -ben az origó körüli szög forgatás mátrixa egy ortogonális mátrix: cos - sin . sin cos 4.27. Következmény. Ortogonális operátor inverze is ortogonális. Bizonyítás. Legyen a ortogonális operátor mátrixa valamely ortonormált bázisban A. Ekkor AT = A-1 , ezért (AT )-1 = (A-1 )-1 , tehát (A-1 )T = (A-1 )-1 . Mivel -1 mátrixa ortogonális mátrix, így -1 ortogonális operátor. 4.28. Következmény. Ha a H E altér invariáns altere a : E E ortogonális operátornak, akkor H is invariáns altér.

40

1. EUKLIDESZI ÉS UNITÉR TEREK

Bizonyítás. Legyen y H . Ekkor hy teljesül vagyis (y, h) = ((y), (h)) = 0 minden h H esetén. Mivel H invariáns altér volt és automorfizmus, így (H) = H, tehát (y) merleges a H altér minden vektorára, azaz (y) H . 4.29. Tétel. Legyen : E E az n-dimenziós E Euklideszi tér ortognális operátora. Ekkor E-ben létezik olyan ortonormált bázis, amelyben mátrixának szerkezete az alábbi: 1 ... 0 . . .. . . . . . 0 . . . 1 -1 . . . 0 . . .. . . . . . . 0 . . . -1 cos 1 - sin 1 sin 1 cos 1 .. . cos - sin
k k

sin k

cos k

4.30. Megjegyzés. Az ortogonális transzformációk mátrixának fenti alakja azt jelenti, hogy E 1 illetve 2-dimenziós invariáns alterek direkt összegére bomlik, és az 1-dimenziós alterekben (+1)-el vagy (-1)-el való szorzásként hat, a 2-dimenziós alterekben pedig origó körüli forgatásként.

4.31. Példa. 1. Ha E 1-dimenziós Euklideszi tér, e E egy normált vektor és ortogonális transzformáció E-n, akkor 1 = e = (e) miatt (e) = ±e. Ekkor tehát vagy (+1)-el vagy (-1)-el való szorzás. 2. Ha E 2-dimenziós Euklideszi tér és a : E E ortogonális operátor mátrixa egy ortonormált bázisban A, akkor AA T = E miatt a11 a12 a21 a22 vagyis a2 + a 2 = 1 11 12 a11 a21 + a12 a22 = 0 a 2 + a2 = 1 21 22 a21 a11 + a22 a12 = 0 a11 a21 a12 a22 = 1 0 , 0 1 (x) = (xe) = x(e) = ±xe = ±x,

5. UNITÉR TEREK LINEÁRIS OPERÁTORAI

41

adódik. Ennel az egyenletrendszernek kétféle mátrix tesz eleget: A1 = cos - sin sin cos A2 = cos sin . sin - cos

Az els esetben origó körüli szög forgatást kapunk, de a második esetben A2 szimmetrikus mátrix, tehát önadjungált leképezés. Ekkor A2 diagonalizálható és a fátlóban a sajátértékek fognak szerepelni, ezek ebben az esetben (+1)-ek vagy (-1)-ek lehetnek: A2 = 1 0 0 2 ahol 1 = ±1 , 2 = ±1 .

5. Unitér terek lineáris operátorai
5.1. Megjegyzés. Mivel az Unitér terek lineáris operátorainak elmélete sok szempontból hasonló az Euklideszi tereken adott lineáris transzformációk elméletével, így ebben a fejezetben csak néhány eltérésre hívjuk fel a figyelmet. 5.2. Tétel. Ha az U unitér téren adott : U U lineáris operátor mátrixa egy ortonormált bázisban A, akkor mátrixa: A = AT . Bizonyítás. Legyen az U Euklideszi térnek (e) = (e1 , . . . , en ) egy ortonormált bázisa és ebben a bázisban mátrixa A = (a ij ) és mátrixa A =
n

(a ). ij

Ekkor (ei ) =
k=1

aik ek , így
n n

((ei ), ej ) =
k=1

aik ek , ej

=
k=1

aik (ek , ej ) = aij ,
kj

n

n

(ei , (ej )) =



ei ,
k=1

a ek jk

=
k=1

a (ei , ek ) = a . ji jk
ki

Innen aij = a , tehát A = AT szükséges. ji 5.3. Definíció. A : U U lineáris operátort önadjungáltnak vagy Hermite-félének nevezzük, ha = . 5.4. Tétel. A : U U önadjungált operátor sajátértékei valósak.

42

1. EUKLIDESZI ÉS UNITÉR TEREK

Bizonyítás. Legyen sajátértéke -nek, és x egy -hoz tartozó sajátvektor. Ekkor (x, x) = (x, x) = ((x), x) = (x, (x)) = (x, (x)) = (x, x) = (x, x), ahonnan (x, x) = 0 miatt = következik, tehát valós szám. 5.5. Következmény. Minden Unitér téren értelmezett önadjungált operátor esetén létezik olyan ortonormált bázis, amelyben az operátor mátrixa diagonális alakú, és a fátlóban valós számok szerepelnek. 5.6. Definíció. A : U U lineáris operátort unitérnek nevezük, ha = -1 . 5.7. Definíció. A : U U lineáris operátort normálisnak nevezzük, ha = , azaz ha és felcserélhet.

5.8. Következmény. Ha egy operátor önadjungált, akkor normális. Ha egy operátor unitér, akkor normális. Megfordítva nem igaz.

5.9. Tétel. Minden : U U normális operátor esetén létezik E-nek olyan ortonormált bázisa, amelyben mátrixa diagonális. 5.10. Megjegyzés. Unitér téren értelmezett normális operátor esetén létezik ortonormált bázis, amelyben a transzformáció mátrixa diagonális alakú. Ha az operátor önadjungált is, akkor a fátlóban valós számok szerepelnek, ha pedig unitér, akkor a fátlóban szerepl sajátértékek abszolút értéke 1.

2. fejezet

Gráfelmélet
1. Gráfelméleti alapfogalmak
1.1. Megjegyzés. A gráfelmélet megszületése Euler nevéhez köthetô, aki 1736-ban vetette fel illetve oldotta meg a königsbergi hidak problémáját. A kérdés az volt, hogy be lehet-e járni a königsbergi Pregel folyóban lév két szigetet a partokkal és egymással összeköt hidakat úgy, hogy mindegyikre csak egyszer lépünk rá és visszatérünk a kiindulási pontra.

A

A

PSfrag replacements

C

D

C

D

B B

1.2. Definíció. Legyenek E és C = diszjunkt halmazok, és legyen : E C × C leképezés. Ekkor a G = (E, , C) hármast irányított gráfnak nevezzük. E-t a gráf éleinek nevezzük, C-t a gráf csúcsainak. A G = (E, , C) gráfot végesnek nevezzük, ha |E| és |C| véges (|E| az E halmaz számosságát jelöli).

43

44

2. GRÁFELMÉLET

1.3. Példa. Legyen a G = (E, , C) gráf esetén E = {e 1 , e2 , e3 , e4 , e5 }, C = {c1 , c2 , c3 } és az élekhez rendelje az alábbi csúcspárokat: c1 e1 c2 (e1 ) = (c1 , c2 ), (e2 ) = (c3 , c1 ), (e3 ) = (c3 , c2 ), (e4 ) = (c2 , c3 ), (e5 ) = (c3 , c3 ). e5 c3
T © T E

e3 e2 e4

1.4. Definíció. A G = (E , , C ) gráfot a G = (E, , C) gráf részgráfjának nevezzük, ha 1. E E és C C, 2. minden e E esetén (e) = (e). 1.5. Definíció. Ha a G = (E, , C) gráfban (e) = (c, c), akkor e-t it hurokélnek nevezzük. 1.6. Definíció. Ha a G = (E, , C) gráfban (e 1 ) = (c1 , c2 ) és (e2 ) = (c1 , c2 ), akkor azt mondjuk, hogy e1 és e2 szigorúan párhuzamos élek. 1.7. Definíció. Ha a G = (E, , C) gráfban (e 1 ) = (c1 , c2 ), és (e2 ) = (c2 , c1 ), akkor e1 és e2 párhuzamos élek. 1.8. Példa. Az 1.3. példában szerepl gráf esetén e 5 egy hurokél, e3 és e4 pedig párhuzamos élek, de nem szigorúan párhuzamosak. 1.9. Definíció. Jelölje C C a C-beli elemekbl álló rendezetlen párok halmazát: C C = {(c1 , c2 ) | c1 , c2 C és a sorrend nem számít} . Ha E egy halmaz, C egy nem üres halmaz és : E C C, akkor a G = (E, , C) hármast irányítatlan gráfnak nevezzük.

1. GRÁFELMÉLETI ALAPFOGALMAK

45

1.10. Megjegyzés. A hurokél definíciója irányítatlan gráfoknál ugyanaz, mint irányított gráfoknál, de a párhuzamosság c1 e1 c2 és a szigorú párhuzamosság között nincs értelme különbséget tenni. Ilyenkor többszörös élrl vagy multiélrl beszélünk, a többszörös éle3 eket tartalmazó gráfokat pedig multigráfoknak e2 e4 nevezzük: (e1 ) = (c1 , c2 ), (e3 ) = (c2 , c3 ), (e5 ) = (c3 , c3 ). (e2 ) = (c1 , c3 ), (e4 ) = (c2 , c3 ), e5 c3

1.11. Definíció. A G = (E, , C) gráfot egyszer gráfnak nevezzük, ha sem párhuzamos éleket, sem hurokéleket nem tartalmaz. 1.12. Definíció. Ha egy gráf nem tartalmaz egyetlen élt sem, akkor üresgráfnak nevezzük. 1.13. Definíció. A G = (E, , C) gráf c C csúcsának a fokán a csúcsra illeszked élek számát értjük, jele: (c). (A hurokéleket kétszeresen számoljuk.) 1.14. Tétel. Kézfogási tétel. Egy G = (E, , C) véges gráf esetén a csúcsok fokszámainak összege egyenl az élek számának kétszeresével: (c) = 2|E|.
cC

Bizonyítás. Mivel minden él pontosan két csúcsra illeszkedik, így a fokszámok összegzésénél minden élt kétszer számolunk. 1.15. Következmény. A G = (E, , C) véges gráf páratlan fokszámú csúcsainak a száma páros. Bizonyítás. A kézfogási tétel szerint 2|E| = páros
cC

(c) =
cC

(c) +
(c)

(c),
cC

páros

(c)

páratlan

páros így a páratlan fokú csúcsok fokszámainak összege is páros. Ez csak akkor lehetséges, ha páros sok ilyen csúcs van.

46

2. GRÁFELMÉLET

1.16. Definíció. Egy G = (E, , C) gráf e 1 , . . . , en E élsorozatát töröttvonalnak nevezzük, ha (e1 ) = (c0 , c1 ), (e2 ) = (c1 , c2 ), . . . , (en ) = (cn-1 , cn ). 1.17. Definíció. Ha a G = (E, , C) gráf egy töröttvonalában a csúcsok mind különbözek, akkor ezt a töröttvonalat útnak nevezzük. Irányított gráf esetén irányított útról beszélünk. 1.18. Definíció. Legyen a G = (E, , C) gráfban e 1 , . . . , en E egy töröttvonal, ahol (e1 ) = (c0 , c1 ),. . . (en ) = (cn-1 , cn ). Ezt a töröttvonalat körnek nevezzük, ha c1 , . . . , cn-1 , cn mind különbözek, de c0 = cn . 1.19. Definíció. Egy G = (E, , C) gráf útjának a hossza alatt az útban szerepl élek számát értjük. 1.20. Definíció. A ci , cj csúcsok távolságán az ket összeköt utak hosszainak minimumát értjük. Jele: d(ci , cj ). Ha két csúcsot nem köt össze út, akkor azt mondjuk, hogy a távolságuk végtelen. 1.21. Definíció. Egy G = (E, , C) gráf átmérje a csúcsok távolságának maximuma: diam(G) = max d(ci , cj ).
ci ,cj C

1.22. Példa. Az alábbi gráf átmérje: c1 diam(G) = max d(ci , cj ) =
ci ,cj C

c5

d(c1 , c6 ) = d(c1 , c5 ) = d(c2 , c5 ) = d(c2 , c6 ) = 3. c2

c3

c4

c6

1.23. Definíció. A G = (E, , C) gráfot összefüggnek nevezzük, ha minden csúcsából minden csúcsába vezet út. 1.24. Tétel. Egy G = (E, , C) összefügg gráf esetén C metrikus tér a d távolságfogalommal.

1. GRÁFELMÉLETI ALAPFOGALMAK

47

1.25. Definíció. A G = (E, , C) gráf G = (E , , C ) részgráfját komponensnek nevezzük, ha 1. G összefügg, 2. G-ben nem létezik olyan G összfügg részgráf, amelynek valódi részgráfja G , tehát a maximális összefügg részgráfok a komponensek. 1.26. Definíció. Egy G = (E, , C) egyszer, összefügg gráfot fának nevezünk, ha nem tartalmaz kört. 1.27. Definíció. Egy G = (E, , C) gráfot erdnek nevezünk, ha komponensei fák. 1.28. Tétel. Minden fagráf tartalmaz legalább két elsfokú csúcsot. 1.29. Definíció. Egy G = (E, , C) gráf páros, ha csúcsainak halmaza felbontható két olyan C1 , C2 halmazra, amelyek diszjunktak, C1 C2 = C és minden e E él esetén ha (e) = (c1 , c2 ), akkor c1 C1 és c2 C2 . 1.30. Példa. Páros gráf: c21

c11 c22 c12 ahol c11 , c12 C1 , c21 , c22 , c23 C2 . c23

1.31. Tétel. Egy G = (E, , C) gráf akkor és csak akkor páros, ha nem tartalmaz páratlan hosszúságú kört. |C| - 1 = |E|.

1.32. Tétel. Ha a G = (E, , C) gráf fa, akkor 1.33. Következmény. Ha a G = (E, , C) gráf erd, és k darab komponensbl áll, akkor |C| - k = |E|.

1.34. Definíció. A G = (E, , C) és a G = (E , , C ) gráfok izomorfak egymással, ha 1. létezik : E E bijektív leképezés, 2. létezik : C C bijektív leképezés,

48

2. GRÁFELMÉLET

1.35. Példa. A G és a G gráf izomorf, de az F és az F gráfok nem izomorfak: c1 e1 c2 (c1 ) e2 e5 e4 c3 e3
(e1 )

3. minden e E, (e) = (c1 , c2 ) esetén ((e)) = ((c1 ), (c2 )).

(c4 )

(e2 ) x

0 c

c4 (c2 ) (c3 ) G F G F 1.36. Definíció. A G = (E, , C) gráfnak a G fagráf a feszítfája, ha G részgráfja G-nek, és G minden csúcsa G -nek is csúcsa. 1.37. Példa. Gráf és feszítfája: c1 c1

(e3 ) (e4 ) (e5 )

E

'

c2

c3

c4

c2

c3

c4

1.38. Tétel. Egy G gráfnak akkor és csak akkor létezik feszítfája, ha összefügg. 1.39. Definíció. Egy G = (E, , C) irányított gráfnak a c C csúcs a gyökere, ha c-bl G minden csúcsába el lehet jutni írányított út mentén. 1.40. Definíció. A G irányított gráfot irányított fának nevezzük, ha G fa és van egy gyökere. 1.41. Definíció. Egy G = (E, , C) egyszer gráfot n-szögpontú teljes gráfnak nevezünk, ha bármely két különböz csúcsát él köti össze, és |C| = n. Jele: T n vagy K n . n(n - 1) . 2 1.43. Definíció. A G = (E, , C) egyszer gráf komplementergráfja az a gráf, amely G-t teljes gráffá egészíti ki. Tehát ha |C| = n, és tekintjük azt a T n teljes gráfot amelynek részgráfja G, akkor T n -bl törölve G éleit megkapjuk a G komplementetgráfját. 1.42. Tétel. A T n n-szögpontú teljes gráf éleinek száma

2. EULER-KÖR, EULER-VONAL, HAMILTON-KÖR

49

1.44. Definíció. Legyen G = (E, , C) gráf és {G 1 , . . . , Gn } a G részgráfjainak egy halmaza. Azt mondjuk, hogy {G 1 , . . . , Gn } a G-nek egy fedése, ha a G valamennyi csúcsa és éle szerepel a G 1 , .., Gn részgráfok valamelyikében. 1.45. Definíció. Ha a G = (E, , C) gráf {G 1 , . . . , Gn } fedésének egyetlen részhalmaza sem fedés, akkor minimális fedésnek nevezzük.

2. Euler-kör, Euler-vonal, Hamilton-kör
2.1. Definíció. Egy G = (E, , C) gráf e 1 , . . . , en élsorozatát Euler-vonalnak nevezzük, ha E minden élét pontosan egyszer tartalmazza. Ha (e1 ) = (c0 , c1 ), . . . , (en ) = (cn-1 , cn ) esetén c0 = c1 , akkor zárt Euler-vonalról beszélünk, ellenkez esetben nyílt Euler-vonalról. 2.2. Példa. A G gráfban {e1 , e2 , e3 , e4 , e5 } egy nyílt Euler-vonal, míg az F gráfban {e1 , e2 , e3 , e4 , e5 , e6 } egy zárt Euler-vonal: e1 e4 e3 e5 e2 e6 e5 e2 e1 e4 e3

G F 2.3. Definíció. Egy G gráf Euler-gráf, ha van zárt Euler-vonala. 2.4. Tétel. Egy G gráf akkor és csak akkor Euler-gráf, ha összefügg, és minden csúcsának a foka páros. 2.5. Definíció. Legyen G = (E, , C) gráf. Ennek egy H = (e1 ) =

(c0 , c1 ), . . . , (en ) = (cn-1 , cn ) útja Hamilton-út, ha a c0 , . . . , cn csúcsok mind különbözek, és G-nek nincs más csúcspontja ezeken kívül. 2.6. Definíció. A G = (E, , C) gráf K körét Hamilton-körnek nevezzük, ha K tartalmazza G minden csúcsát. 2.7. Tétel. Ha egy G egyszer gráfban minden csúcspont foka legalá`bb k 2, akkor van a gráfban egy legalább k + 1 hosszúságú kör.

2.8. Tétel. Ha a G = (E, , C) egyszer gráf minden c C csúcsára fen|C| náll, hogy (c) , akkor a gráf összefügg. 2

50

2. GRÁFELMÉLET

2.9. Definíció. Egy G = (E, , C) gráf esetén az élek halmazának |E| számosságát a G méretének nevezzük, a csúcsok |C| számosságát pedig a G gráf rendjének nevezzük. 2.10. Definíció. Egy élen fekv két csúcsot szomszédos csúcsnak nevezünk, tehát ha (e) = (c1 , c2 ), akkor c1 és c2 szomszédos csúcsok. 2.11. Definíció. Egy egyszer gráf teljes gráf, ha bármely két csúcsa szomszédos. 2.12. Példa. Teljes gráf: c1

c5

c2

c4

c3

2.13. Tétel (Ore tétel). Ha egy G = (E, , C) gráf rendje nagyobb mint 2 és bármely két nem szomszédos ci , cj csúcspont fokának az összege nagyobb vagy egyenl mint G rendje, akkor G-nek van Hamilton köre. 2.14. Példa. Az alábbi gráf nem teljesíti Ore tételét: c1

c6

c2

c5

c3

c4 2.15. Tétel (Dirac tétel). Ha az n = 2k csúcspontú egyszer gráf bármely csúcsának a foka legalább k, akkor G-nek van Hamilton köre.

3. GRÁFOK CSÚCSMÁTRIXA

51

2.16. Megjegyzés. A Hamilton-körök megkeresésének problémájával rokon területe a kombinatórikus optimalizálásnak az úgynevezett utazó ügynök problémája. Itt egy ügynöknek minimális költséggel kell bejárnia bizonyos városokat. Ha a városokat csúcsoknak tekintjük, a városokat összeköt utak lesznek a gráf élei, és minden élhez hozzárendeljük az adott út megtételének a költségét, akkor a feladat egy olyan Hamilton-kör keresése, amely mentén a költségek összege minimális. 2.17. Példa. Az alábbi gráf rendje 6, és minden csúcsának a foka 3, ezért Dirac tétele szerint van Hamilton-köre: c1 e6 c5
'

e1 e8
c3

e5 e7 c4
s



e9

©

e2 e3

e4
E

c2

c6

Például a H = (e1 , e2 , e3 , e4 , e5 , e6 ) kör egy Hamilton kör, hiszen minden csúcs pontosan egyszer szerepel benne: (e 1 ) = (c1 , c3 ), (e2 ) = (c3 , c2 ), (e3 ) = (c2 , c6 ), (e4 ) = (c6 , c4 ), (e5 ) = (c4 , c5 ), (e6 ) = (c5 , c1 ).

3. Gráfok csúcsmátrixa
3.1. Definíció. Legyen G = (E, , C) irányított gráf és |C| = n. A G csúcsmátrixa az az A = (aij ) Mn×n mátrix, melynek aij általános eleme egyenl a ci csúcsból a cj csúcsba vezet élek számával. 3.2. Tétel. Legyen A Mn×n a G gráf csúcsmátrixa. Az A mátrix l-edik hatványának (Al )ij általános eleme megadja a ci csúcsból a cj csúcsba vezet l hosszúságú töröttvonalak számát.

52

2. GRÁFELMÉLET

3.3. Példa. A következ gráf csúcsmátrixnak harmadik hatványa megadja, hogy egyik csúcsból a másikba hányféleképpen lehet eljutni 3 élen végighaladva: c4
'

e3

c3
T

e4

e5
c ©

e6
E

e2

c1 0 0 A= 1 1 1 0 0 0 1 1 0 0 0 0 1 0 1 1 2 A = 1 0 0 0 1 1 1 0 1 1 1 0 0 0

Például c3 csúcsból c3 csúcsba vezet 3 hosszúságú töröttvonalak: (e 3 , e4 , e6 ) és (e5 , e1 , e2 ). 3.4. Lemma. Egy G = (E, , C) irányított, véges gráf pontosan akkor tartalmaz legalább |C| hosszúságú irányított töröttvonalat, ha G-ben van irányított kör. 3.5. Következmény. Egy G = (E, , C) véges, irányított gráf pontosan akkor tartalmaz kört, ha G csúcsmátrixának |C| = n-edik hatványa nem azonosan nulla. 3.6. Tétel. A G = (E, , C) gráf ci , cj C csúcsainak l = d(ci , cj ) távolsága az a legkisebb l szám, amelyre (A l )ij = 0. 3.7. Definíció. Ha G(E, , C) gráfhoz adott egy olyan f leképezés, amely minden élhez egy valós számot rendel, akkor a G(E, , C, f ) egy súlyozott gráf, és f (e) az e él súlya. 3.8. Megjegyzés (A legrövidebb út problémája). Legyen adott a G(E, , C, f ) súlyozott egyszer gráf, ahol valamennyi e E-re f (e) > 0. A gráf két különböz ci és cj csúcsai közötti legrövidebb utat keressük, vagyis azt a ci -bl cj -be vezet utat, amelyre az élek súlyának összege minimális. Abban az esetben ha az élek súlya s, akkor a két csúcs közötti legrövidebb utat, ha az létezik, a csúcsmátrixból kiszámíthatjuk. Legyenek a G gráf csúcsai c1 , c2 , . . . , cn és a csúcsmátrix az A = (aij ). 3.9. Tétel. A ci csúcsból a cj (i = j) csúcsba akkor vezet egy k hosszúságú legrövidebb út, ha ak = 0 és al = 0, ahol l = 0, 1, 2, . . . , k - 1. ij ij

e1 2 1 3 A = 1 1

c2 1 1 1 0 1 1 2 1 1 0 1 1

A 3.3. példa esetén láthatjuk, hogy c 1 -bl c4 -be van 2 hosszúságú legrövidebb út.

3. fejezet

Kódelmélet
1. Kombinatórikus valószínség
1.1. Megjegyzés. A természetben elforduló jelenségeket két csoportba soroljuk: a determinisztikus jelenségek kimenetele kikövetkeztethet, míg a sztochasztikus jelenségek kimenetele nem. A szochasztikus jelenségek közül az egyedi jelenségek csak egyszer fordulnak el, a tömegjelenségek pedig akárhányszor bekövetkezhetnek. A valószínségszámítás a véletlentl függ tömegjelenségek tudománya. 1.2. Definíció. Egy véletlen tömegjelenség megfigyelését kísérletnek nevezzük, egy kísérlet lehetséges kimeneteleit pedig eseményeknek. Azokat az eseményeket amelyek mindig csak egyféleképpen következhetnek be, akárhányszor is végezzük el a kísérletet, elemi eseményeknek nevezzük. 1.3. Példa. Egy szabályos kockával való dobás esetén például esemény az, hogy páros számot dobunk, vagy, hogy 3-nál kisebbet dobunk. Elemi esemény például az, hogy 6-ost dobunk. 1.4. Megjegyzés. Tekintsük egy véletlen tömegjelenséggel kapcsolatban szóbajöhet események halmazát. Ezen halmaz elemeivel különböz mveleteket végezhetünk. A halmaz elemeit A, B, C, · · · -vel jelöljük. 1.5. Definíció. Az A és a B események egyenlek, ha akárhányszor is végezzük el a kísérletet, vagy egyszerre következnek be, vagy egyszerre nem következnek be. Jele: A = B. 1.6. Definíció. Az események halmazának van két kitüntetett eseménye: a lehetetlen esemény olyan esemény amelyik sohasem következik be, jele: , a biztos esemény olyan esemény amelyik mindig bekövetkezik, jele: I. 1.7. Definíció. Az A esemény ellentett vagy másképpen komplementer eseménye pontosan akkor következik be, ha A nem következik be. Jele: A.
53

54

3. KÓDELMÉLET

1.8. Definíció. Az A és a B események összegén azt az eseményt értjük, amelyik pontosan akkor következik be, ha A és B közül legalább az egyik bekövetkezik. Jele: A + B. 1.9. Definíció. Az A és a B események szorzatán azt az eseményt értjük, amelyik pontosan akkor következik be, ha A és B együttesen következik be. Jele: A · B. 1.10. Tétel. Az események közötti mveletek rendelkeznek a következ tulajdonságokkal: 1. A + A = A, A · A = A, 2. A + B = B + A, A · B = B · A, 3. A + (B + C) = (A + B) + C, A · (B · C) = (A · B) · C, 4. A + = A, A · = , 5. A + I = I, A · I = A, 6. A + A = I, A · A = , 7. (A + B) · C = A · C + B · C, A · B + C = (A + C) · (B + C), 8. A + B = A · B, A · B = A + B.

Bizonyítás. Csak az 7. állítás második részét igazoljuk:

(A + C) · (B + C) = (A + C) · B + (A + C) · C = A · B + C · B + A · C + C · C = A·B+C ·B+A·C +C = A·B+C ·B+C ·A+C ·I = A·B+C ·B+C ·(A+I) = A · B + C · B + C · I = A · B + C · (B + I) = A · B + C · I = A · B + C. 1.11. Definíció. Tekintsünk egy H nem üres halmazt, amelyet eseménytérnek nevezünk, elemeit pedig elemi eseményeknek. Tekintsük a H részhalmazainak egy olyan A rendszerét (az A elemeit eseményeknek nevezzük), amelyre teljesülnek a következk: 1. Ha A A, akkor A A, 2. ha A, B A, akkor A · B A és A + B A, 3. H A, A. Ekkor A-t eseményalgebrának nevezzük.

1.12. Példa. A kockadobás kísérlete esetén legyen az eseménytér a H = {1, 2, 3, 4, 5, 6} halmaz, ennek elemei az elemi események. Legyen A = P (H), tehát H összes részhalmazai az események. Például jelentse az A esemény azt, hogy páros számot dobunk, B pedig, hogy 3-nál kisebbet. Ezek az események azonosíthatóak az A = {2, 4, 6} illetve B = {1, 2} halmazokkal, tehát pontosan akkor fog az A esemény bekövetkezni, ha a kísérlet kimenetelének megfelel elemi esemény (például 2-est dobunk) mint

1. KOMBINATÓRIKUS VALÓSZíNSÉG

55

halmazelem szerepel az A halmazban. Ekkor az A + B esemény megfelel az A B = {1, 2, 4, 6} halmaznak, az AB szorzatesemény pedig az A B = {2} metszethalmaznak. Az I biztos esemény megfelelje maga a H halmaz. Az események és a halmazok közötti megfeleltés miatt a halmazelméleti alapfogalmaknál leírtak a megfelel változtatásokkal átvihetk eseményalgebrákra is. 1.13. Tétel. Egy véges eseményalgebrában (azaz a H eseménytér véges) bármely esemény a sorrendtl eltekintve egyértelmen állítható el elemi események összegeként. Tehát ha E1 , . . . , En az elemi események, akkor Ei · Ej = ha i = j és E1 + · · · + En = I. Ekkor minden A A esetén az A = Ei1 + · · · + Eik felírás a sorrendtl eltekintve egyértelm. 1.14. Definíció. Az A1 , . . . , An A események teljes eseményrendszert alkotnak, ha páronként kizárják egymást (azaz bármely két különböz esemény szorzata a lehetetlen esemény) és összegük a biztos esemény, vagyis A1 + · · · + An = I. 1.15. Definíció. Legyen A egy eseményalgebra és A egy esemény A-ból. Végezzük el a kísérletet n-szer és számoljuk össze, hogy ebbl hányszor következett be az A esemény. Ezt a k számot az A esemény gyakoriságának k nevezzük az adott kísérletre vonatkozóan, a hányadost pedig az A relatív n gyakoriságának. 1.16. Megjegyzés. Ha a kísérletek számát minden határon túl növelve azt tapasztaljuk, hogy a relatív gyakoriság értékei egy jól meghatározott számérték körül ingadoznak, akkor ezt a 0 és 1 közé es számot fogjuk az esemény valószínségének nevezni, ez a valószínség tapasztalati megfogalmazása. A következ, matematikai definíció Kolmogorovtól származik. 1.17. Definíció. Legyen A egy eseményalgebra. Ezen eseményalgebra minden egyes A eseményéhez hozzárendelünk egy P (A)-val jelölt valós számot amely rendelkezik a következ tulajdonságokkal: 1. 0 P (A) 1, 2. P (H) = 1, 3. ha A1 , A2 · · · A és Ai · Aj = i = j esetén, akkor


i=1

Ai A és

P
i=1

Ai

=
i=1

P (Ai ).

56

3. KÓDELMÉLET

Ekkor P (A)-t az A esemény valószínségének nevezzük. Egy olyan eseményalgebrát, amelynek minden A eleméhez hozzá van rendelve egy P (A) szám a fenti tulajdonságokkal, valószínségi algebrának nevezzük. Ha az eseményalgebra véges, akkor a valószínségi algebrát is végesnek nevezzük. 1.18. Definíció. Az olyan véges valószínségi algebrát, amelyben az elemi események egyenl valószínséggel bírnak klasszikus valószínségi algebrának nevezzük. 1.19. Tétel. Klasszikus valószínségi algebrában egy esemény valószínségét úgy számíthatjuk ki, hogy az esemény szempontjából kedvez elemi események számát osztjuk az összes elemi esemény számával: P (A) = kedvez elemi események száma . összes elemi esemény száma

Bizonyítás. Véges eseményalgebrában véges sok esemény van, amelyek teljes eseményrendszert alkotnak, azaz páronként kizárják egymást és összegük a biztos esemény. Legyen A egy tetszleges esemény, amely a valószínségszámítás alaptételének értelmében elállítható elemi események összegeként: A = E i1 + · · · + E ik . Ekkor Mivel E1 + · · · + En = I, így P (A) = P (Ei1 + · · · + Eik ) = P (Ei1 ) + · · · + P (Eik ). 1 = P (I) = P (E1 + · · · + En ) és a P (Ei ) valószínségek egymással egyenlek, ezért P (E i ) = i {1, . . . , n} esetén. Tehát P (A) = P (Ei1 ) + · · · + P (Eik ) = 1 1 k + ··· + = . n n n

1 minden n

1.20. Példa. A fenti képletben szerepl számokat általában kombinatórikus úton határozzuk meg. Ha egy magyar kártyából három lapot húzunk, akkor az elemi események száma a lehetséges kártyalap-hármasok száma, tehát 32 1 , és minden elemi esemény valószínsége , tehát ez egy klasszikus 32 3 3

1. KOMBINATÓRIKUS VALÓSZíNSÉG

57

valószínségi algebra. Ekkor annak az eseménynek a valószínsége, hogy a három lap közül legalább egy zöld: kedvez esetek száma = összes esetek száma 8 1 24 8 + 2 2 32 3 24 8 + 1 3 24 0

P =

= 0, 59.

1.21. Definíció. Legyen B egy pozitív valószínség esemény, továbbá A egy tetszleges esemény. Ekkor az A eseménynek B-re mint feltételre vonatkozó feltételes valószínségén a P (A|B)= valószínséget értjük. 1.22. Tétel (Valószínségek szorzástétele). Legyen B egy pozitív valószínség esemény és A egy tetszleges esemény. Ekkor P (A · B) = P (A|B)P (B). 1.23. Definíció. Az A és B eseményeket függetlennek nevezzük, ha P (A · B) = P (A)P (B). 1.24. Tétel (Teljes valószínség tétele). Alkossanak az A 1 , . . . , An esn

P (A · B) P (B)

emények egy teljes eseményrendszert, azaz A i ·Aj = ha i = j és Legyen B egy tetszleges esemény. Ekkor
n

Ai = I .
i=1

P (B) =
i=1

P (B|Ai )P (Ai ).

1.25. Tétel (Bayes tétele). A teljes valószínség tételének feltételei mellett: P (B|Ai )P (Ai ) P (Ai |B) = n . P (B|Aj )P (Aj )
j=1

1.26. Tétel (Nagy számok Bernoulli-féle törvénye). (Kapcsolat a relatív gyakoriság és a valószínség között) Annak a valószínsége, hogy a relatív gyakoriságnak az esemény valószínségétl vett eltérése egy tetszlegesen kicsiny > 0 számnál nagyobb legyen, a nullához fog tartani, ha a

58

3. KÓDELMÉLET

kísérletek száma tart a végtelenhez: k - P (A) > n

P

0,

ha

n .

1.27. Definíció. Ha egy H eseménytér elemi eseményeihez egy-egy valós számot rendelünk, így egy függvényt értelmezünk, amelyet valószínségi változónak nevezünk és -vel jelölünk. Ha a valószínségi változó megszámlalhatóan végtelen sok értéket vesz fel, akkor diszkrét valószínségi változóról beszélünk. (Pl. a kockadobás esetén az elemi eseményeken a valószínségi változó az 1, 2, 3, 4, 5, 6 értékeket veheti fel.) A valószínségi változó folytonos, ha annak értékei az egész számegyeneshez, vagy annak egy részinterrvallumához tartoznak. (Egy folytonos valószínségi változót a következ példában mutatunk be.) 1.28. Definíció. Legyen : H R egy tetszleges valószínségi változó. Ekkor az F : R [0, 1] függvényt a eloszlásfüggvényének nevezzük, ahol F (x) = P ( < x), azaz F -nek az x R helyen felvett értéke megegyezik annak a valószínségével, hogy a valószínségi változó x-nél kisebb értéket vesz fel. 1.29. Definíció. Ha egy kisérlethez tartozó események egy geometriai alakzat részhalmazainak feleltethetk meg úgy, hogy az egyes események valószínsége az eseményhez rendelt részhalmaz geometriai mértékével arányos, akkor geometriai valószínségekrl beszélünk. 1.30. Példa. Egy egységnyi hosszúságú szakaszon találomra kijelölünk két pontot. Mekkora a valószínsége annak, hogy a köztük lév távolság kisebb, mint egy adott h hossz, ahol 0 < h < 1 ? Jelölje a két pont távolságát a szakasz kezdpontjától x és y. Ekkor az eseménytér teszleges elemét azonosíthatjuk az egységnégyzet (x, y) koordinátájú pontjával. Annak valószínségét keressük, hogy |x - y| < h, vagyis y < x + h és y > x - h.

1. KOMBINATÓRIKUS VALÓSZíNSÉG

59

6

(0, 1)

y =x+h

y =x-h T (0, h)
-

(h, 0)

(1, 0)

Ha az (x, y) koordinátájú pont a vonalazott részbe esik akkor teljesül, hogy |x - y| < h, ellenkez esetben pedig nem teljesül. így a keresett valószínség a vonalazott rész területének és a négyzet teületének aránya: (1 - h)2 T 2 = 1 - (1 - h)2 = 2h - h2 . P = = 1 1 Legyen továbbá a valószínségi változó a két pont közötti távolság. Ekkor eloszlásfüggvénye: 0 ha x < 0 F (x) = P ( < x) = 2x - x2 ha 0 x 1 . 1 ha 1 < x 1-2 Annak a valószínsége, hogy a két pont távolsága legalább P 3 4 =1-P 3 < 4 =1- 3 2· - 4 3 4 3 : 4
2

=

1 . 16

Az alábbiakban felsoroljuk a lefontosabb nevezetes diszkrét valószínségi változókat. 1.31. Definíció. A valószínségi változó binomiális eloszlású, ha lehetséges értékei a 0, 1, . . . , n számok és ezek közül a k-t a n k Pk = p (1 - p)n-k k

60

3. KÓDELMÉLET

valószínséggel veszi fel, ahol 0 < p < 1 az eloszlás paramétere. 1.32. Példa. Legyen 1 - p = 0, 15 annak a valószínsége, hogy egy kosár almából hibásat választunk ki. Visszatevéssel egyenként véletlenszeren válasszunk ki 20 darabot. Jelölje a hibátlan almák számát, tehát lehetséges értékei: 0, 1, . . . , 20, és binomiális eloszlású lesz p = 0, 85 paraméterrel. Ekkor annak a valószínsége, hogy mind a 20 alma hibátlan lesz: P ( = 20) = 20 · 0, 8520 · 0, 150 . 20

1.33. Definíció. A valószínségi változó hipergeometrikus eloszlású, ha lehetséges értékei a 0, 1, . . . , n számok és ezek közül a k-t a M k N -M n-k N n

P ( = k) = valószínséggel veszi fel.

1.34. Példa. N = 100-darab almából M = 20-darab férges. Visszatevés nélkül válasszunk ki n = 10-darabot. Ha jelöli ezek közül a férges almák számát, akkor hipergeometrikus eloszlású lesz, és annak a valószínsége, hogy 5-darab férges alma lesz: M k N -M n-k N n 20 5 100 10 80 5

P ( = 5) =

=

.

1.35. Példa. Annak a valószínsége, hogy egy lottószelvényen k-találatunk lesz: 5 85 k 5-k P ( = k) = . 90 5 1.36. Definíció. A valószínségi változót paraméter Poisson eloszlásúnak nevezzük, ha lehetséges értékei a 0, 1, 2, . . . számok, és ezek közül a k-val jelölt értéket a k - P ( = k) = ·e k! valószínséggel vesz fel.

2. BET SZERINTI KÓDOLÁS

61

2. Bet szerinti kódolás
Ebben a fejezetben röviden összefoglaljuk az információtovábbítás elméleti alapjait. Az els kódelméleti munkák az elmúlt század közepén jelentek meg (Claud Shannon (1948), Marcel Golay (1949), Richard Hamming (1950)). Az információtovábbítás három f eszközét különböztetjük meg: az adóberendezést, az információs csatornát és a vevberendezést. Mindenekeltt tekintsünk egy úgynevezett kimeneti ábécét, amely lehet a magyar ábécé betinek halmaza is. Jelölése: A = {a 1 , . . . , an }. 2.1. Definíció. Az A = {a1 , . . . , an } kimeneti ábécé jeleibl alkotott a i1 , . . . , aik sorozatokat elsdleges közlésnek nevezzük. 2.2. Megjegyzés. Az információs csatorna általában csak két különböz jeltipus továbbítását teszi lehetvé, és ezekhez a jelekhez a 0 és 1 számokat (az úgynevezett bináris kódokat) rendeljük hozzá. Az információtovábbítás folyamatában a következ lépéseket különböztetjük meg: 1. kódolás, vagyis az elsdleges közlés átalakítása bináris sorozattá, 2. modulálás, azaz a bináris sorozat átalakítása fizikai jelekké, 3. a fizikai jelek kiküldése az információs csatornára, 4. a fizikai jelek felfogása a vevberendezésen, 5. demodulálás, vagyis a fizikai jelek visszaformálása bináris sorozattá, 6. dekódolás, azaz az elsdleges közlés elállítása a bináris sorozatból. 2.3. Definíció. Legyen A = {a1 , . . . , an } tetszleges kimeneti ábécé, és legyen K = {1 , . . . , n } véges hosszúságú bináris sorozatoknak valamilyen n-elm halmaza. A kódolásnak azt a formáját, amelynél a kimeneti ábécé minden ai betjének egy i K bináris sorozatot feleltetünk meg, bet szerinti kódolásnak nevezzük. 2.4. Megjegyzés. Bet szerinti kódolásnál tetszleges a i1 ai2 . . . aik elsdleges közléshez egy i1 i2 . . . ik bináris sorozatot tudunk hozzárendelni. 2.5. Definíció. A K halmazt kódnak, az 1 , . . . , n elemeket kódszavaknak, a kódszavak tetszleges sorozatát pedig kódolt közlésnek nevezzük. A kódelméleti alapfogalmak és alaptételek tárgyalásánál alapvet munkaként használjuk az Irodalomjegyzék [3] könyvet. 2.6. Példa. Legyen A = {a, b, c, d} a kimeneti ábécé, K = {00, 01, 100, 101} pedig a kód. Ekkor a dac szó (elsdleges közlés) bet szerinti kódolása a 10100100 bináris sorozat.

62

3. KÓDELMÉLET

2.7. Megjegyzés. összefoglalva elmondhatjuk, hogy a kódolási eljárás egy függvény: H : A {0, 1} . (Itt -al jelöltük a megfelel halmazbeli elemek összes véges sorozatából álló halmazt.) A dekódoláshoz képezni kell a H -1 : {0, 1} A inverz függvényt. A H -1 függvény akkor és csak akkor létezik, ha H egy-egy értelm, azaz különböz A -beli szavakhoz különböz kódolt közléseket rendel. 2.8. Példa. Az A = {a, b, c, d} kimeneti ábécé esetén a K = {00, 01, 11, 0001} kód nem egy-egy értelm kódolást valósít meg, mivel az ab-hez és a d-hez ugyanaz a bináris sorozat tartozik.

3. Felbontható kódok
3.1. Definíció. A K = {1 , . . . , n } kódot felbonthatónak nevezzük, ha tetszleges bináris sorozat legfeljebb egyféleképpen bontható kódszavak sorozatára. 3.2. Megjegyzés. Ha a K-beli kódszavak hossza mind egyenl, akkor a K kód felbontható. (Egy kódszó hossza alatt a benne szerepl 0 és 1 számok számát értjük.) 3.3. Definíció. A K kódot prefix kódnak nevezzük, ha egyetlen kódszó sem valódi kezdszelete egy másik kódszónak. 3.4. Példa. Azok a kódok amelyek egyenl hosszúságú kódszavakból állnak prefix kódok. Prefix kód az A = {a, b, c, d} kimeneti ábécéhez tartozó K1 = {00, 01, 100, 101} kód is, de nem prefix kód a K = {00, 10, 100, 101}. 3.5. Tétel. Minden prefix kód felbontható. 3.6. Tétel. McMillan-egyenltlenség. Jelölje l 1 , . . . , ln rendre az 1 , . . . , n K-beli kódszavak hosszát. Ha a K = { 1 , . . . , n } kód felbontható, akkor
n i=1

2-li 1.

3.7. Megjegyzés. Ez a McMillan egyenltlenség csak szükséges feltétele a felbonthatóságnak. Meg lehet adni olyan nem felbontható kódot, amely eleget tesz a fenti egyenltlenségnek, például az A = {a, b, c, d} és K = {00, 01, 11, 0001} pár is ilyen. Igaz viszont a következ:
n

3.8. Tétel. Ha
i=1

2-li 1, akkor létezik olyan K = {1 , . . . , n } prefix

kód, melyben a kódszavak hossza l1 , . . . , ln .

4. OPTIMÁLIS KÓDOK

63

3.9. Definíció. Két kódot ekvivalensnek nevezünk, ha ugyanannyi kódszót tartalmaznak, és kódszavaik megfeleltethetk úgy egymásnak, hogy a hosszuk páronként megegyezik. 3.10. Következmény. Tetszleges felbontható kódhoz találhatunk vele ekvivalens prefix kódot.

4. Optimális kódok
Egy adott kimeneti ábécé esetén vannak olyan jelek, amelyek gyakrabban fordulnak el az információtovábbításban, így ezekhez célszer rövid kódszavakat hozzárendelni, míg a ritkábban elfordulókhoz hosszabb kódszavak is tartozhatnak. Legyen F egy jelforrás, amely az A = {a 1 , . . . , an } ábécé betit véletlenszeren bocsájtja ki, az egymás utáni jeleket egymástól függetlenül. Legyen p i annak a valószínsége, hogy az F által kibocsájtott jel a i . A valószínségekre
n

teljesülnek a következk: pi 0, (i = 1, . . . , n) és

pi = 1 . Így a pi
i=1

azt mutatja meg, hogy egy M számú jelbl álló jelsorozatot véve, a benne elforduló ai jelek száma közelítleg pi · M. Adjunk meg egy A = {a1 , . . . , an } ábécét és egy hozzá tartozó K = {1 , . . . , n } felbontható kódot. K-ban az 1 , . . . , n kódszavak hossza legyen l1 , . . . , ln . így az
n

l1 p1 M + · · · + l n pn M = M

pi li
i=1

képlet egy i1 i2 . . . iM kódolt közlés átlagos hosszát adja.
n

4.1. Definíció. Az L(K) = költségének nevezzük.
i=1

pi li számot a K kód F forrás melletti

4.2. Megjegyzés. Látható, hogy a költség és a kódszavak hossza összefügg. 4.3. Definíció. A K0 felbontható kódot az F jelforrásra nézve optimálisnak nevezzük, ha tetszleges K felbontható kód esetén az F mellett L(K 0 ) L(K). 4.4. Megjegyzés. Ez azt jelenti, hogy az optimális kódok a kódolt közlések átlagos hosszának csökkentésében játszanak szerepet. Igaz a következ:

64

3. KÓDELMÉLET

4.5. Tétel. Tetszleges F forráshoz létezik optimális prefix kód. 4.6. Definíció. Az F forrás entrópiájának nevezzük a
n

H(F ) =
i=1

pi log2

1 pi

számot. A költség és az entrópia kapcsolatát adja meg a következ két tétel: 4.7. Tétel (Claud Shannon tétele). Egy F jelforráshoz tartozó tetszleges K felbontható kódra teljesül, hogy: H(F ) L(K). 4.8. Tétel. Az F jelforráshoz tartozó K 0 optimális kód költségére teljesül, hogy L(K0 ) H(F ) + 1. 4.9. Következmény. Az F jelforráshoz tartozó K 0 optimális kódra igaz a következ becslés: H(F ) L(K0 ) H(F ) + 1.

5. Optimális kód konstrukciója
D. Huffmann amerikai matematikus 1951-ben adta meg az alábbi két tétel segítségével az optimális kódok egy lehetséges konstrukcióját. Ismeretes az elz fejezetbl, hogy tetszleges jelforráshoz létezik optimális kód. A következ eljárásnál tegyük fel, hogy egy F jelforrás A = {a1 , . . . , an } kimeneti ábécéjének betihez rendre a p 1 · · · pn valószínségek tartoznak. Optimális kódok meghatározásának Huffmann-féle algoritmusa a következ két tételen alapszik: 5.1. Tétel. Egy F jelforráshoz létezik legalább egy K = { 1 , . . . , n } optimális prefix kód, amelyre l1 · · · ln-1 = ln és az utóbbi két kódszó 0 és 1 alakú (tehát csak az utolsó jegyben térnek el). 5.2. Tétel. Legyen F jelforrás egy A = {a 1 , . . . , an } kimen ábécével, és az A elemeihez tartozó p1 · · · pn valószínségekkel, és legyen K = {1 , . . . , n } az elz tétel alapján létez optimális prefix kód F -hez. Tegyük fel, hogy pi = q 1 + q 2 és p1 · · · pi-1 pi+1 · · · pn q1 q2 .

5. OPTIMÁLIS KÓD KONSTRUKCIÓJA

65

Ekkor a

K = {1 , . . . , i-1 , i+1 , . . . , n , i 0, i 1}

kód optimális prefix kód lesz arra az F jelforrásra nézve, melynek kimen ábécéje A = {a1 , . . . , an , an+1 } és a hozzátartozó valószínségek p 1 , . . . , pi-1 , pi+1 , . . . , pn , q1 , q2 .

5.3. Megjegyzés. Ezen utóbbi két tétel segítségével minden n + 1 bet kibocsájtó jelforráshoz tartozó optimális kód meghatározását visszavezethetjük egy n-bets jelforrás esetére. A módszer a következ: Induljunk ki egy F jelforráshoz tartozó A = {a1 , . . . , an , an+1 } ábécébl, a betkhöz tartozó valószínségek pedig legyenek p 1 · · · pn pn+1 . Legyen továbbá F egy másik jelforrás, a hozzá tartozó kimen ábécé B = {b 1 , . . . , bn }, a valószínségek pedig p1 · · · pi-1 pn + pn+1 pi+1 · · · pn-1 . így ha K = {1 , . . . , n } optimális az F -re nézve, akkor a K = {1 , . . . , i-1 , i+1 , . . . , n , i 0, i 1} optimális lesz az F jelforrás esetén. Az algoritmus bemutatására alkalmazzuk a következ példát:

5.4. Példa. Legyen A = {a1 , a2 , a3 , a4 , a5 , a6 , a7 }, a valószínségek pedig {0, 2; 0, 2; 0, 19; 0, 12; 0, 11; 0, 09; 0, 09}. Ekkor az ábécé és a kódok redukálásának útja a következ: 0, 20 0, 20 0, 19 0, 12 0, 11 0, 09 0, 09 + 0, 20 0, 20 0, 19
E 0, 18 E 0, 23 E 0, 37 E 0, 40 E 0, 60

0, 20 0, 20 0, 19 + 0, 18 +

0, 23 0, 20 0, 20 +

0, 37 0, 23

+

0, 40

0, 12 0, 11

66

3. KÓDELMÉLET

10 11 000 010 011 0010 0011
E

10 11 000 001 010 011

E

01 10 11 000 001

E

00 01 10 11

E

1 00 01

E

0 1

így az ábécé betszámának csökkentésével eljutottunk egy kételem ábécéhez, amelyhez tartozó {0, 1} kód optimális. Visszafelé alkalmazva az eljárást növekv elemszámú ábécéhez nyerhetünk optimális kódot.

6. Hibajavító kódok zajos csatorna esetén
Ha az információs csatorna zajos, akkor a demodulátorból kapot kódolt közlés hibákat tartalmazhat. Ebben a fejezetben olyan eljárásokat ismertetünk, amelyek lehetvé teszik a hibák felismerését, és annak a javítását. Feltételezzük, hogy azonos hosszúságú kódszavakból álló bináris kódokkal történik az információközlés. 6.1. Definíció. A kódszavakat blokkoknak, a kódszavak hosszát blokkméretnek nevezzük. 6.2. Megjegyzés. Ezek a kódok felbonthatóak lesznek, mivel a blokkméretek egyenlk és a kódszavak különbözek. 6.3. Definíció. Legyen a K = {1 , . . . , m } kódhoz tartozó blokkméret n, és t( N) n. Azt mondjuk, hogy a (zajos) információs csatorna legfeljebb t hibát okoz, ha tetszleges blokkban legfeljebb t jel értéke változik meg az információtovábbítás során. 6.4. Példa. Hibafelismer kód egy hiba esetén: Legyen minden kódszó olyan, hogy az els fele és a második fele megegyezik. Ekkor az 1 hibát okozó zaj a kódszó egyik felét tudja megváltoztatni. Tehát ahol a két "félkódszó" különbözik, ott hiba van. 6.5. Példa. Hibafelismer és hibajavító kód egy hiba esetén: Legyen adva olyen kódolás, amelynél a kódszó els, második és harmadik

7. LINEÁRIS KÓDOK ÉS HAMMING KÓDOK

67

harmada megegyezik. Ekkor 1 hibát ki is tudunk javítani, mivel jó harmadoknak azokat tudjuk elfogadni, amelyek legalább kétszer szerepelnek egy kódszóban. 6.6. Definíció. Az n blokkméret bináris kódok halmazát jelöljük B n -nel. Ekkor az 1 , 2 B n kódszavak (vektorok) (1 , 2 ) Hamming távolságán azoknak a pozícióknak a számát értjük, amelyeken a kódszavak eltérnek egymástól. 6.7. Megjegyzés. A (1 , 2 ) távolság metrikát ad meg B n -en, mivel teljesülnek a metrika tulajdonságai (lásd els fejezet 2.16. megjegyzés): 1. (1 , 2 ) 0, és (1 , 2 ) = 0 1 = 2 , 2. (1 , 2 ) = (2 , 1 ), 3. (1 , 2 ) (1 , 3 ) + (3 , 2 ). 6.8. Definíció. Egy K B n kód esetén a d(K) = min{(1 , 2 ) | i , j K} számot a K kód kódtávolságának nevezzük. 6.9. Megjegyzés. A 6.4. példában a kódtávolság 2, a 6.5. példában pedig 3. 6.10. Példa. Paritásellenrz kód: Legyen B n olyan kód, amely olyan n hosszúságú kódszavakból áll, amelyekben páros számú egyes szerepel. Ekkor d(B n ) = 2. A hiba felismerése egyszer, meg kell számolni a beérkez 1-esek számát blokkonként. Ha ez páratlan, akkor hibás a kódszó. 6.11. Tétel. Tetszleges K kód akkor és csak akkor alkalmas t számú hiba felismerésére, ha d(K) t + 1. 6.12. Tétel. Egy K kóddal akkor és csak akkor lehet t számú hibát javítani, ha d(K) 2t + 1.

7. Lineáris kódok és Hamming kódok
7.1. Definíció. Legyenek = (a1 , . . . , an ) és = (b1 , . . . , bn ) B n bináris szám n-esek. Az és vektorok + összege alatt az + = (a 1 + b1 , . . . , an + bn ) szám n-est értjük, ahol az ai + bi összegnél a 2-vel való osztás maradékát értjük, azaz az összeget "modulo 2" kell venni.

68

3. KÓDELMÉLET

7.2. Definíció. Ha bináris konstans (azaz 0 vagy 1), akkor az = (a1 , . . . , an ) vektornak a skalárral való szorzata = (a 1 , . . . , an ), így 1 = és 0 = 0. 7.3. Definíció. Azt mondjuk, hogy a K kód lineáris, ha bármely , K esetén + K és bármely {0, 1} és K esetén K teljesül. 7.4. Definíció. Az = (a1 , . . . , an ) vektor w() súlya alatt az vektorban lév nem nulla elemek számát értjük. 7.5. Tétel. Egy K lineáris kód esetén (, ) = w( + ). 7.6. Definíció. Egy K kód w(K) súlya alatt a K-beli nem nulla szavak súlyának minimumát értjük. 7.7. Tétel. Ha K lineáris kód, akkor d(K) = w(K). 7.8. Megjegyzés. Látható, hogy egy K lineáris kód altere B n -nek egy kételem test felett, így a vektorterek elméletébl adódik a következ. 7.9. Tétel. Ha K B n bináris kód, akkor létezik egy olyan k n természetes szám, hogy tetszleges K-beli kódszó egyértelmen megadható, mint az i (i = 1, . . . , k) vektorok lineáris kombinációja, azaz = 1 1 + · · · + k k valamilyen i bináris konstansokkal. 7.10. Következmény. Az 1 , . . . , k vektorok a K egy bázisát alkotják, k pedig a K kód dimenziója. 7.11. Definíció. Legyen a K kód bázisa 1 , . . . , k , és legyenek a bázisvektorok koordinátái i = (ai1 , . . . , ain ), (i = 1, . . . , k). Ekkor a 1 a11 . . . a1n . . . .. . G= . = . . . . . k ak1 . . . akn mátrixot a kód generátormátrixának nevezzük. 7.12. Következmény. Egy adott kód egy tetszleges kódszava eláll a kód generátormátrixa sorainak lineáris kombinációjaként.

7. LINEÁRIS KÓDOK ÉS HAMMING KÓDOK

69

7.13. Definíció. Az és vektorok (, ) skaláris szorzata alatt az összeget értjük, az összeget "modulo 2" kell venni. (, ) = (a1 b1 + · · · + an bn )

7.14. Definíció. Az és vektorok merlegesek egymásra, ha (, ) = 0. Egy altér ortogonális komplementerének tulajdonságai miatt igaz a következ: 7.15. Tétel. Legyen K egy m-dimenziós kód. Ekkor léteznek 1 , . . . , n-m független vektorok úgy, hogy egy B n vektor akkor és csak akkor eleme K-nak, ha (, i ) = 0, (i = 1, . . . , n - m).

7.16. Definíció. A 1 , . . . , n-m bázisú K kódot a K kód duálisának nevezzük. 7.17. Következmény. A K kód független a bázis megválasztásától.

7.19. Következmény. Legyen a K kód ellenrz mátrixa H. Ekkor K akkor és csak akkor, ha HT = 0.

7.18. Definíció. A K kód ellenrz mátrixának nevezzük az alábbi mátrixot: b11 ... b1n . . . .. . H = 1 , . . . , n-m = . . . . bn-m,1 . . . bn-m,n

7.20. Megjegyzés. Mindezek alapján látható, hogy ha az K , = 0 kódszó súlya t, akkor a H mátrixban van t számú lineárisan függ oszlopvektor. Fordítva, ha a H-ban van t számú lineárisan függ oszlopvektor, akkor létezik K kódszó, amelyre w() = t. Tehát d(K) > t akkor és csak akkor teljesül, ha a K kód ellenrz mátrixából tetszleges t számú oszlopot kiválasztva lineárisan független oszlopvektorokat kapunk. így az elz fejezet két utolsó tétele alapján igaz a következ: 7.21. Tétel. Egy K lineáris kóddal akkor és csak akkor lehet t számú hibát javítani, ha a K ellenrz H mátrixában tetszlegesen kiválasztva 2t számú oszlopot lineárisan független oszlopvektorokat kapunk. 7.22. Megjegyzés. Ezen tétel alapján az 1 hibát javító, úgynevezett Hamming kódokat a következképpen adhatjuk meg: Legyen a blokkméret n = 2l - 1 alakú. Ha a H oszlopaiként az összes l hosszúságú nem nulla vektort tekintjük, akkor a H tetszleges két oszlopa lineárisan független. Tehát az így megadott kód kódtávolsága legalább három, azaz egy hibát tudunk vele javítani.

70

3. KÓDELMÉLET

7.23. Példa. Legyen l = 3, ekkor a blokkméret 2 l - 1 = 23 - 1 = 7. Ellenrz mátrixként tekinthetjük a következt: 0 0 0 1 1 1 1 H = 0 1 1 0 0 1 1 . 1 0 1 0 1 0 1 Legyen eleme a K Hamming kódnak. Ekkor H T = 0. Legyen továbbá a kimen jel, amelyet -ból úgy kapunk, hogy egy helyen megváltoztatjuk, például = (0, 0, 0, 1, 1, 1, 1) ; = (0, 0, 0, 0, 1, 1, 1). Ekkor = + , ahol = (0, 0, 0, 1, 0, 0, 0). így H T = H(T + T ) = HT + HT = HT , azaz 0 0 0 0 0 0 0 1 1 T H = H 1 + H 1 = 0 + 0 = 0 , 1 0 0 0 0 1 0 1 0

azaz a hibás kód, a negyedik helyen javítandó, mivel H T a H negyedik oszlopával megegyez oszlopvektor.

Irodalomjegyzék
[1] Andrásfalvi Béla: Gráfelmélet, folyamatok, mátrixok, Budapest, Akadémiai kiadó (1983). [2] Bélteky Károly: Analitikus geometria és lineáris algebra : I. éves nappali tanárszakos, matematikus és matematikus levelez hallgatók részére, Budapest, Tankönyvkiadó (1989). [3] Demetrovics János, Denev Jordan, Pavlov Padiszlav: A számítástudomány matematikai alapjai, Budapest, Tankönyvkiadó (1985). [4] Fazekas István: Valószinségszámítás, Debrecen, Kossuth Egyetemi K. (2003). [5] Gaál István, Kozma László: Lineáris algebra, Debrecen, Kossuth Egyetemi K. (2002). [6] Halmos Pál: Véges dimenziós vektorterek, Budapest, Müszaki Könyvkiadó (1984). [7] Kovács Zoltán: Geometria : az euklidészi geometria metrikus megalapozása, Debrecen, Kossuth Egyetemi K. (2002). [8] Szendrei Ágnes: Diszkrét matematika : logika, algebra, kombinatorika, Szeged, Polygon (1994).

71

Tárgymutató

, 21 , 53 A, 54 B n , 67 diam( ), 46 d(K), 67 (E, , C), 43 I, 53 L(K), 63 P (A), 55 (x, y), 21 w(), 68 kódok ekvivalenciája, 63 adjungált operátor, 33 báziselállítás, 9 bes szorzás, 21 Bessel egyenltlenség, 26, 31 bet szerinti kódolás, 61 bilineáris forma, 11, 18 bilineáris forma mátrixa, 11 bilineáris forma rangja, 13 bilineáris forma szimmetrikus, 13 blokk, 66 blokkméret, 66 Cauchy-Swarz-Bunyakowszky egyenltlenség, 22, 31 Claud Shannon tétele, 64 csúcs foka, 45 csúcsok távolsága, 46 definit, 16
73

Dirac tétel, 50 eloszlás binomiális, 59 hipergeometrikus, 60 Poisson, 60 eloszlásfüggvény, 58 elsdleges közlés, 61 elsfajú lineáris forma, 17, 18 entrópia, 64 erd, 47 esemény, 53 biztos, 53 elemi, 53, 54 ellentett, 53 lehetetlen, 53 eseményalgebra, 54 események összege, 54 események egyenlsége, 53 események függetlensége, 57 események szorzata, 54 eseménytér, 54 Euklideszi tér, 21 Euler-gráf, 49 Euler-vonal, 49 fminor-determináns, 16, 17 Ftengelytranszformációs tétel, 37 fa, 47 fedés, 49 feszítfa, 48 generátormátrix, 68 geomteriai valószínség, 58

74

TÁRGYMUTATÓ

gráf összefügg, 46 üres, 45 egyszer, 45 irányítattlan, 44 irányított, 43 komplementer, 48 páros, 47 súlyozott, 52 teljes, 48, 50 véges, 43 gráf átmérje, 46 gráf éle, 43 gráf csúcsa, 43 gráf csúcsmátrixa, 51 gráf izomorfia, 47 gráf mérete, 50 Gram-Schmidt-féle ortogonalizációs eljárás, 25 Gram-Schmidt-féle ortogonalizációs eljárás, 30 gyökér, 48 gyakoriság, 55 háromszög egyenltlenség, 22 Hamilton-út, 49 Hamilton-kör, 49 Hamming távolság, 67 Hermite-féle bilineáris forma, 19 Hermite-féle kvadratikus forma, 19 Hermite-féle operátor, 41 Hermite-szimmetria, 19 hossz, 21, 30 Huffmann-féle algoritmus, 64 hurokél, 44 indefinit, 16 inercia tétel, 16 irányított fa, 48 izometrikus izomorfia, 27 költség, 63 kör, 46 kód, 61 felbontható, 62 lineáris, 68 optimális, 63 paritásellenrz, 67

prefix, 62 kód duálisa, 69 kód súlya, 68 kódolt közlés, 61 kódszó, 61 kódtávolság, 67 kísérlet, 53 kanonikus alak, 14 kanonikus bázis, 14 komponens, 47 kvadratikus forma, 14 kvadratikus forma mátrixa, 14 kvadratikus forma rangja, 15 Legrövidebb út problémája, 52 lineáris forma, 9 lineáris funkcionál, 9 másodfajú lineáris forma, 17, 18 merleges vektorok, 24, 30 metrika, 24 metrikus tér, 24 minimális fedés, 49 Minkowski egyenltlenség, 22 Nagy számok Bernoulli-féle törvénye, 57 normál alak, 15 normális operátor, 42 normált tér, 23 normált vektor, 21 norma, 21, 30 Ore tétel, 50 ortogonális komplementer, 28 ortogonális rendszer, 24 ortogonális transzformáció, 37 ortogonális vektorok, 24, 30 ortonormált bázis, 25 ortonormált rendszer, 24, 30 önadjungált operátor, 35, 41 Parseval egyenlség, 26, 31 poláris forma, 14 Pythagoras tétel, 24 részgráf, 44 relatív gyakoriság, 55

TÁRGYMUTATÓ

75

súly, 52 skaláris szorzás, 21 Struktúratétel, 36 Sylvester-féle tehetetlenségi törvény, 16 szemidefinit, 16 szigorúan párhuzamos élek, 44 szimmetrikus operátor, 35 szomszédos csúcs, 50 töröttvonal, 46 távolság, 23, 29 teljes eseményrendszer, 55 Teljes valószínség tétele, 57 unitér operátor, 42 unitér tér, 29 út, 46 út hossza, 46 valószínség, 56 feltételes, 57 Valószínségek szorzástétele, 57 valószínségi algebra, 56 klasszikus, 56 véges, 56 valószínségi változó, 58 diszkrét, 58 folytonos, 58 vektor súlya, 68 vektorok szöge, 21



Hasonló témájú dokumentumok

Hozzászólások

18. század 2008 3. óra adatbiztonság anyagok dm függvényelemzés gazdasági magánjog génmódosítás házi hull humánbiosz gyak irodalomtudomány jogszabályok kefo keringés kisebbség korreláció költségszámítás középérték közigazgatástörténet lemez magánjog méhen belüli fejlődés neveléstörténet okj oktatási törvény preromán program pszichológia pszichoszexuális fejlődés radács román sql statisztika i. szte-btk dr. simon józsef technika természetföldrajz tételek tóth tudomány valszám várak erődök vésés vezetői vízlágyítás vizsga kérdések vizsgasor vörösmarty zrínyi