A piros részekre mozgatva a kurzort megjelenik egy amolyan "saját szavaimmal" magyarázat. Remélem segít a megértésben, és egy kicsit összefogja az előzőleg tanultakat. Néhova szúrok be csak úgy megjegyzéseket is.

Forrásaim: Fülöp Ágnes .pdf diasora, Nagy Gábor .pdf diasora (C szakirányos), Wikipedia, ez az oldal, saját jegyzet.

Ha valahol valami hibás, vagy nem korrekt, kérlek jelezd a shando@vipmail.hu címre!


Gráf alapok

Fa és komplementer

Irányított gráf

Gráf mátrixok, agoritmusok

Homomorfizmusok

Először egy kis filler. Egy grupoidban, vagy valami más algebrai struktúrában, van legalább egy műveletünk, hogy ha két elemre vesszük, akkor az eredmény is a halmaz eleme. Mondjuk a pozitív egész számok és összeadás. Mert 3 és 5 is az, 3+5=8 is az. Ekkor az a halmaz zárt az adott műveletre, mert az "nem vezet ki belőle". De mondjuk pozitív egész számok és kivonás már rossz, mert 3-5 = -2, és az nem pozitív egész.

Egy Ł : G → G′ művelettartó leképezést homomorfizmusnak fogunk nevezni, és azt mondjuk, hogy Ł(G) a G homomorf képe. Ha a leképezés injektív, akkor monomorfizmus; ha szürjektív, akkor epimorfizmus; ha bijektív, akkor izomorfizmus.

Egy izomorfizmus esetén G és G' közt igazából nem lehet algebrailag különbséget tenni. Például két halmaz ami teljesen ekvivalens, annak fel tudjuk sorolni más és más sorrendben az elemeit, de mindig ugyanazokat soroljuk fel. Vagy egy gráfot fel tudunk rajzolni máshogy is, de mindig ugyanazoakt a csúcsokat kötjük össze.

Fontos példánk egységelemes félcsoportra egy tetszőleges X halmaz önmagába való leképezéseinek halmaza a függvényösszetétellel, mint művelettel. Ha egy félcsoportnak egy ilyen leképezés-félcsoportba való homomorfizmusát tekintjük, akkor a félcsoport reprezentációjáról, magyarul ábrázolásról beszélünk. Ha a reprezentáció izomorfizmus, akkor hű reprezentációról beszélünk.

Részfélcsoport, részcsoport

Egy G grupoid egy H részhalmazát részgrupoidnak nevezzük, ha maga is grupoid a G-beli műveletet csak H elemei között tekintve. Ha H a G-beli műveletet csak H elemei között tekintve félcsoport, csoport, stb., akkor részfélcsoportnak, részcsoportnak, stb. nevezzük.

A rész(fél)csoportokat szokták komplexusnak is nevezni. Illetve ha így "leszűkítettem" egy (fél)csoportot egy rész(fél)csoportra (komplexursa), akkor ugye már kevesebb dolgon értelmezem az adott műveletet. A művelet ilyen "leszűkítését/megszorítását" komplexusműveletnek hívjuk. Eléggé értelemszerű igazából. A halmazon művelet, a komplexuson komplexusművelet.

Egy nem üres G csoportnak legyen H nem üres részcsoportja. Ekkor ugye (ha valódi) akkor kevesebb elemet fog tartalmazni. De ez trükkös tud lenni, mert nem vághatok ki csak úgy egy darabot, mintha halmazokról lenne szó. Csak olyan "szeletet" vehetek ki, hogy az még csoportként viselkedjen. Így a művelettel is történnek furcsa dolgok, amiket azért nem árt átérezni. Néhány:

Szóval mi is történik itt? Ránézésre HH valami nagyobb dolognak néz ki, mint H, akkor hogy lehet a részcsoportja? Haladjunk sorban. H−1 elemei ugye csak a balinverzek. Szóval ez már kevesebb elem, oké akkor nyilván részcsoportja, mert ugyanaz a művelet de kevesebb elemre. A HH "alakú" elemek olyanok, amik másik kettő "szorzataként" állnak elő. Ilyen is valszeg kevesebb lesz. Az utolsó eset pedig igazából a "két elem 'szorzata'" leszűkítése csak a balinverzekkel való "szorzásra". Szóval ez megint még kevesebb elemű lesz. A jobboldali inverzre is ezt fel lehetne írni, de egymásból nem következnek, mert mi van ha nem kommutatív a művelet?

Generátum és ciklikus csoport

Legyen G egy csoport és K ⊂ G. A K halmaz < K > generátuma a G összes, K-t tartalmazó részcsoportjának metszete.

Volt például az, hogy egy H (fél)csoportnak rész(fél)csoportját alkotják a HH alakú elemek, mert azok két másik elem "szorzatának" eredményei. Ennek speciális esete volt a balinverzekkel való "szorzás". Vagyis vannak rész(fél)csoportok, amik szűkebbek mint más rész(fél)csoportok. Ha van egy olyan K részcsoportom, ami több másikban bennevan, akkor < K > (vagyis K generátuma) az összes olyan elem, ami ezekben a másik részcsoportokban van. Persze ebbe K elemei is beletartoznak. Ha ez az egész eredeti halmazt visszaadja, akkor K neve generátorrendszer.

Ha egy csoportnak létezik egyelemű generátorrendszere, akkor ciklikusnak nevezzük, az elemet pedig egy generátorának.

Például ha a szokásos szorzás műveletnél és a pozitív egész számoknál maradunk, akkor mondjuk 2 poztív egész hatványai ciklikus csoportot fognak alkotni, mert 2 és a szozás művelet mindet előállítja (2, 2*2, 2*2*2, stb.). Nagy általánosságban az ilyen hatványozásra kell gondolni ha arról beszélünk, hogy egy ciklikus csoportot generál egy elem. De ez kicsit érdekesen hangzik, mikor additív műveletről beszélünk, ami ugye a szokásos összeadásra hajaz. Ilyenkor a hatványozás igazából egymás utáni összeadások sorozata. Így például 1 generálja a pozitív egész számokat. Sőt, inverzet véve (ami ugye az ellentett) még a negatívokat is.

Mellékosztályok és normálosztó

Legyen G egy csoport és legyen H a G egy részcsoportja. Vezessük be az a ∼ b, ha ab−1 ∈ H relációt. Ez ekvivalenciareláció. Vizsgáljuk meg az ekvivalenciaosztályokat. Azt állítjuk, hogy a ∈ G ekvivalenciaosztálya a Ha halmaz. Ha b ∈ Ha, akkor b = ha valamely h ∈ H-ra. Innen ba−1 = h, azaz ab−1 = h−1 ∈ H. Megfordítva, ha a ∼ b, akkor ab−1 = h ∈ H, ahonnan b = h−1a ∈ H−1a ⊂ Ha. Ha most az a ∼ b, ha b−1a ∈ H ekvivalenciarelációt vezetjük be, akkor hasonlóan számolva kapjuk, hogy az a ekvivalenciaosztálya az aH halmaz. Az előző ekvivalenciaosztályokat a G csoport H szerinti jobb oldali mellékosztályainak, az utóbbiakat pedig bal oldali mellékosztályainak nevezzük.

Ugye az ekvivalenciareláció amit felveszünk, az olyan, hogy a halmaz két eleme akkor van ilyen relációban, ha az egyikkel balról "szorozva" a másik inverzét, akkor az eredmény még a részhalmaz eleme. Azt, amivel így szorozgatok a csoportból veszem. Ez kb nekünk most annyit jelent, hogy attól függően, hogy melyik elemet veszem ki a csoportból, valszeg más és más eredményeket kapok a "szorzás" után. Mondjuk a csoportból vett elem legyen a, a részcsoport meg H. Ekkor az ilyen eredmények halmaza a Ha halmaz. A különböző Ha halmazok egy osztályozást fognak megadni, mert uniójuk visszaadja az egész részcsoportot. Ez azért van, mert bármilyen "szorzás" eredménye is H eleme kellett legyen, hiszen már ez volt a grupoidság alapfeltétele is, mi meg (rész)csoportban vagyunk, ami sokkal több mint grupoid. Ez az, hogy ha b Ha eleme, akkor van olyan H beli h, hogy b = h * a. Így lesz Ha a jobboldali mellékosztályok halmaza, aH pedig a baloldali mellékosztlyok halmaza, arra a részcsoportra nézve.

Gondoljunk bele, már csak akkor is más ilyen osztályozásoakt kaphatunk, ha szűkebb részcsoportot nézünk. Akár különböző számú osztályok is lehetnek. Ezt a számot hívjük a csoport indexének, ha az véges (különben végtelen). Na ilyenkor ha G volt a csoportom, és H a részcsoportbom, akkor a jobboldali mellékosztályok száma [ G : H ] jelöléssel írt "H G-beli indexe".

Lagrange tétele szerint: Ha H a G véges csoport részcsoportja, akkor a H rendjének és indexének a szorzata G rendje.

Ez azért van, mert H rendje pont H elemeinek száma, H indexe meg a jobboldali mellékosztályok száma, amit G elemeivel képeztem. Minden H beli elemet annyiféleképpen sorolhatok be, ahány G elem van.

Egy G csoport egy N részcsoportja szerint mellékosztályok között a (komplexus) szorzás nem feltétlenül kompatibilis az osztályozással: NaNb nem biztos hogy egyenlő Nab-vel vagy egyáltalán egy jobboldali mellékosztállyal.

Ha N részcsoportja G-nek és minden a ∈ G-re aN = Na, akkor N-et normálosztónak vagy normális részcsoportnak vagy invariáns részcsoportnak nevezzük.

Lényegében a mellékosztályok nem részcsoportok, és általában nem is várjuk el tólük. Ez egyfajta osztályozás, egyfajta kategorizálása a csoport elemeinek. Nem valószínű, hogy művelettartó (mármint a részcsoport műveletére, ami az eredeti műveletnek már így is egy leszűkítése (komplexusművelet)) lenne, és megtartaná a csoportság tulajdonságait. Ha mégis, akkor azt a mellékosztályt hívjuk normálosztónak (a jövőben sokszor invariánsnak is fogjuk).

Faktorcsoport

Egy G csoportnak egy N normálosztó szerinti mellékosztályai a (komplexus)szorzásra nézve csoportot alkotnak.

A G csoport N normálosztó szerinti faktorcsoportjának (vagy hányadoscsoportjának) nevezzük és G/N-el jelöljük. Ha G rendje véges, akkor G/N rendje [G : N].

Ha G valamilyen normálosztóját nézzük, ami ugye egy olyan mellékosztály ami valami csoda folytán részcsoport is (lásd előző fejezet), akkor aszerint is tudok mellékosztályokat képezni. A normálosztót is már ugye egy részcsoportból képeztük, és a részcsoporton az eredeti művelet egy leszűkítése volt. Na a normálosztóval képzett mellékosztályok is csoportok, vagyis normálosztók (a részcsoportnak, nem az eredeti csoportnak) lesznek erre a leszűkített műveletre. Szóval ezt tudnánk elég sokáig iterálni, mindig egy "réteggel beljebb" menni.

Homomorfizmus magja, Homomorfizmus-tétel

Egy G csoportnak egy G′ csoportba való Ł homomorfizmusánál a homomorfizmus magja-n a G' csoport e′ egységelemének a teljes inverz képét értjük. A Ł magját ker(Ł)-vel jelöljük.

Szóval az olyan elemek lesznek a mag (kernel), amik a G-ből G' egységelemére képződtek le. Ezek normálosztót fognak alkotni (lásd előző fejezet).

Részgyűrű, résztest

Ideál

Gauss-gyűrű, Euklideszi-gyűrű

Polinomok

Irreducibilis polinom és testbővítés

Legyen F test, és f ∈ F[x] egy n-ed fokú (n ∈ ℕn) irreducibilis főpolinom.

Ekkor F = F[x]/(f) test; ez következik abból, hogy az (f) főideál maximális ideál,

de közvetlenül is belátható: ha g ∉ (f ), azaz f nem osztja g-t,

akkor alkalmazva a bővített euklideszi algoritmust, olyan u és v polinomokat kapunk,

amelyekre d = fu + gv, ahol d az f és g egyik legnagyobb közösosztója, egy nullad fokú polinom.

Innen d osztálya az egységelem F-ban, v osztály pedig g osztályának az inverze.

Minden mellékosztályban a legalacsonyabb fokú polinom fokszáma kisebb, mint n

és csak egy n-nél alacsonyabb fokú polinom van;