Feladatok és végeredmények a Bevezető fejezetek a matematikába tárgy II. félévéhez Összeállította: Láng Csabáné Budapest, 2004. január
Tartalomjegyzék 1. Feladatok.................................................................................................................................... 2 1.1. Gráfelmélet.............................................................................................................................. 2 1.1.1 Alapfogalmak.................................................................................................................... 2 1.1.2 Euler-gráf .......................................................................................................................... 4 1.1.3 Hamilton-út, Hamilton-kör ............................................................................................... 4 1.1.4 Síkbeli gráfok.................................................................................................................... 4 1.1.5 Vegyes feladatok............................................................................................................... 5 1.2. Csoportok ................................................................................................................................ 6 1.2.1 Félcsoportok, csoportok.................................................................................................... 6 1.2.2 Részcsoport, elem rendje, ciklikus csoport....................................................................... 7 1.2.3 Mellékosztályok, Lagrange-tétel, invariáns részcsoport, homomorf leképezések, faktorcsoport .............................................................................................................................. 8 1.2.4 Vegyes feladatok............................................................................................................... 9 1.3. Gyűrű, test............................................................................................................................. 12 1.3.1 Gyűrű, test, integritási tartomány, nullosztó................................................................... 12 1.3.2 Karakterisztika ................................................................................................................ 13 1.3.3 Oszthatóság, osztók, egységek, felbonthatatlan, prím .................................................... 13 1.3.4 Euklideszi gyűrű ............................................................................................................. 14 1.3.5 Részgyűrű, ideál, faktorgyűrű......................................................................................... 14 1.3.6 Vegyes feladatok............................................................................................................. 15 2. Végeredmények ........................................................................................................................... 16 2.1. Gráfelmélet............................................................................................................................ 16 2.1.1 Alapfogalmak.................................................................................................................. 16 2.1.2 Euler-gráf ........................................................................................................................ 17 2.1.3 Hamilton-út, kör.............................................................................................................. 17 2.1.4 Síkbeli gráfok.................................................................................................................. 17 2.1.5 Vegyes feladatok............................................................................................................. 17 2.2. Csoportok .............................................................................................................................. 17 2.2.1 Félcsoportok, csoportok.................................................................................................. 17 2.2.2 Részcsoport, elem rendje, ciklikus csoport..................................................................... 18 2.2.3 Mellékosztályok, Lagrange-tétel, invariáns részcsoport, homomorf leképezések, faktorcsoport ............................................................................................................................ 18 2.2.4 Vegyes feladatok............................................................................................................. 18 2.3. Gyűrű, test............................................................................................................................. 19 2.3.1 Gyűrű, test, integritási tartomány, nullosztó................................................................... 19 2.3.2 Karakterisztika ................................................................................................................ 19 2.3.3 Oszthatóság, osztók, egységek, felbonthatatlan, prím .................................................... 19 2.3.4 Euklideszi gyűrű ............................................................................................................. 19 2.3.5 Részgyűrű, ideál, faktorgyűrű......................................................................................... 19 2.3.6 Vegyes feladatok............................................................................................................. 19 1
1. Feladatok 1.1. Gráfelmélet 1.1.1 Alapfogalmak 1. Van-e olyan 9 pontú egyszerű gráf, amelyben a pontok fokai rendre a következők: a. 7, 7, 7, 6, 6, 6, 5, 5, 5;
b. 6, 6, 5, 4, 4, 3, 2, 2, 1.
2. Van-e olyan 8 pontú egyszerű gráf, amelyben a fokszámok 6, 6, 6, 6, 3, 3, 2, 2. 3. Van-e olyan (legalább két pontú) egyszerű gráf, amiben minden pont foka különböző? 4.
a. A V(G)={1, 2, …, n} halmazon hány egyszerű gráf adható meg? b. Ezek között hány m élű gráf van?
5. Egy k-reguláris egyszerű gráfnak hány pontja lehet? 6. Legyen G=(V, E) egyszerű gráf, melyre v(G)≤2n+1 (n∈N). Lássuk be, hogy ha minden v∈V esetén d(v)≥n, akkor G összefüggő. 7. Legyen G=(V, E) egyszerű gráf, melyre v(G)≤2n+1, és minden v∈V esetén d(v)≥n–1. Igaz-e, hogy a gráf összefüggő? 8. Lássuk be, hogy egy G gráf vagy a komplementere összefüggő. 9. Mutassuk meg, hogy ha egy egyszerű gráf minden pontja legalább másodfokú, akkor a gráfban van kör. 10. Igazoljuk, hogy ha egy egyszerű gráfban minden pont foka legalább k (k≥2), akkor van a gráfban olyan kör, amely k+1, vagy több pontú. 11. Mutassuk meg, hogy az összefüggő G gráfból elhagyva egy körének egyik élét, a gráf továbbra is összefüggő marad. 12. Az alábbiakban egy-egy egyszerű gráfot definiálunk. Rajzoljuk le ezeket. i. A gráf pontjai egy tetraéder csúcsai. Két pont a gráfban össze van kötve, ha a tetraéderben a megfelelő csúcsok között van él. ii. A gráf pontjai egy kocka csúcsai. Két pont a gráfban össze van kötve, ha a kockában a megfelelő csúcsok között van él.
5 iii. Egy kör kerületén vegyünk fel öt pontot. Gráfunk csúcsai a pontok által meghatározott húr 2 lesz. Két csúcsot a gráfban akkor kötünk össze, ha a megfelelő húroknak nincs közös végpontjuk. 13. Adjuk meg az összes 4, illetve 5 pontú gráfot, amelyek izomorfak komplementerükkel. 14. Hat versenyző körmérkőzést játszik. Bizonyítsuk be, hogy bármely időpontban van három olyan
versenyző, akik már mind játszottak egymással, vagy három olyan, akik egyike sem játszott a másik kettővel. 15. Lássuk be, hogy az előző állítás nem igaz 5 résztvevő esetére. 16. a. Bizonyítsuk be, hogy n szögpontú, n+1 élű gráfban van olyan pont, amely legalább harmadfokú. b. Mutassuk meg, hogy ha az élek száma n, akkor nincs mindig legalább harmadfokú pont.
2
17. Van-e olyan nem összefüggő gráf, amelynek nincs 6-nál több pontja, és minden pontja másodfokú? 18. Lássuk be, hogy ha egy n szögpontú gráfnak legalább n éle van, akkor van a gráfban kör. 19. Jelöljük egy fagráf elsőfokú pontjainak számát f1-gyel, a 2-nél nagyobb fokú pontjainak számát pedig c-
vel. Bizonyítsuk be, hogy ha a pontok száma legalább 2, akkor f1≥c+2. 20. Mutassuk meg, hogy összefüggő gráf bármely két leghosszabb útjának van közös pontja. (A lehető
legtöbb élt tartalmazó utakról van szó.) 21. Igazoljuk, hogy bármely fában az összes leghosszabb út egy ponton megy át. 22. Bizonyítsuk be, hogy ha egy gráf nem tartalmaz hurokélt, és minden pontjának a foka legalább 3, akkor
van a gráfban páros hosszúságú kör. 23. Bizonyítsuk be, hogy egy legalább két pontú összefüggő gráfból mindig elhagyható egy pont (a belőle
induló élekkel együtt), úgy, hogy összefüggő maradjon. 24. Igazoljuk, hogy bármely, legalább 5 pontú gráfban, vagy a komplementerében van kör. 25. a. Legfeljebb hány szeparáló él van egy n(∈N)-pontú gráfban? Adjuk meg az olyan gráfokat,
amelyekben pontosan ennyi szeparáló él van. b. Legfeljebb hány szeparáló csúcs van egy n(∈N)-pontú gráfban? Adjuk meg az olyan gráfokat,
amelyekben pontosan ennyi szeparáló csúcs van. 26.
a. Igaz-e, hogy minden szeparáló pont illeszkedik legalább egy szeparáló élre? b. Mi a válasz az előző kérdésre akkor, ha minden csúcs foka legalább három?
27. Igaz-e, hogy egy gráfban a. minden él legalább egy vágásnak eleme, b. minden csillag élhalmaza vágás (csillag egy csúcs a belőle kiinduló élekkel, és azok végpontjaival). 28. a. Lássuk be, hogy hibás a következő okoskodás.
Állítás: Ha egy n pontú egyszerű gráf éleinek száma: e ≥ "Megoldás":
(n − 1)(n − 2) + 1 , akkor összefüggő. 2
(n − 1)(n − 2) n − 1 egy n-1 pontú teljes gráf éleinek száma. Ha ehhez még egy élt = 2 2
hozzáveszünk, mely egy eredeti pontból az n-edikbe fut, összefüggő gráfot kapunk. Hol a hiba? b. Bizonyítsuk be az állítást. 29. Rajzoljuk fel az összes 3, 4, 5 pontú fát (az izomorfokat csak egyszer). 30. Legalább hány kör van egy 10-csúcsú, 16 élt tartalmazó összefüggő gráfban? 31. Legyen n∈N. Az n-csúcsú teljes gráf egy alapkörrendszere hány körből áll? 32. Legyen G v-csúcsú egyszerű gráf, ahol v természetes szám. Milyen lehet G, ha a. a rangja a lehető legnagyobb,
b. a nullitása a lehető legkisebb.
33. Jelöljük A-val egy gráf tetszőlegesen kiválasztott pontjainak halmazát, és k-val a gráf azon éleinek
számát, melyek egyik végpontja A-ba tartozik, a másik pedig nem. Bizonyítsuk be: k páros, illetve
3
páratlan aszerint, hogy az A-ba tartozó páratlan fokú csúcsok száma páros illetve páratlan. 34. Igazoljuk, hogy ha egy gráf minden pontjának foka legalább 3, akkor nincs olyan 2-nél nagyobb egész
szám, amellyel a gráf minden körének hossza osztható.
1.1.2 Euler-gráf 35. Van-e olyan Euler-gráf, amelynek páros számú pontja és páratlan számú éle van? 36. Igazoljuk, hogy ha egy gráf minden pontjának foka 4, akkor élei megszínezhetők piros és kék színekkel
úgy, hogy minden szögponthoz két piros és két kék él illeszkedjék. 37. Legyen G egy olyan gráf, amelynek bármely két pontja között vezet út. Legyen S egy olyan élsorozat,
amely az összes élt tartalmazza, és minimális hosszú. Bizonyítsuk be, hogy S egyetlen élen sem halad át kettőnél többször.
1.1.3 Hamilton-út, Hamilton-kör 38. Rajzoljunk olyan összefüggő gráfot, amelyben minden pont legalább másodfokú és nem tartalmaz
Hamilton-kört. 39. Adjunk meg olyan gráfot, amelyben minden pont foka k (k≥3), és van olyan pontja, amelyen nem halad
át kör. 40. Igazoljuk a következőket. a. Ha a G gráfban létezik k darab pont, amelyeket törölve G több mint k komponensre esik szét, akkor
G-nek nincs Hamilton-köre. b. Ha a G gráfban létezik k darab pont, amelyeket elhagyva G még k+1-nél is több komponensre esik
szét, akkor Hamilton-útja sincs. 41. Mutassuk meg, hogy egy ping-pong körmérkőzés résztvevői sorbaállíthatók úgy, hogy mindenki
legyőzte a közvetlenül mögötte állót. (Azt nem követeljük meg, hogy az összes mögötte állót le kellett volna győznie.) (Más szóval lássuk be, hogy ha teljes gráfból irányított gráfot készítünk, abban mindig van irányított Hamilton-út.) 42. Mutassuk meg, hogy egy legalább 2 pontú teljes gráfból egyetlen élének törlése révén nyert gráfot lehet
úgy irányítani, hogy ne legyen irányított Hamilton-útja. 43. Bizonyítsuk be, hogy ha egy összefüggő gráf K köréből egy élt eltörölve a gráf egy leghosszabb útját
kapjuk, akkor K Hamilton-köre a gráfnak.
1.1.4 Síkbeli gráfok 44. A Petersen-gráf síkbarajzolható-e? 45. i. Bizonyítsuk be, hogy ha egy G gráf pontszáma legalább 11, akkor vagy G, vagy G komplementere nem
síkgráf. ii. Adjunk meg 8 pontú síkgráfot úgy, hogy komplementere is síkgráf legyen.
4
46. Hány éle van egy n pontú összefüggő síkgráfnak, ha minden tartománya (a külső is) háromszög?
1.1.5 Vegyes feladatok 47. Melyek azok a gráfok, amelyekben bármely két élnek van közös pontja? 48. Milyen komponensekből állhat egy gráf, ha minden pontjának foka legfeljebb kettő? 49. Lássuk be, hogy ha egy n pontú (n>1) összefüggő gráfnak kevesebb éle van, mint csúcsa, akkor van
elsőfokú csúcsa. 50. Lássuk be, hogy n csúcsú összefüggő gráfnak legalább n-1 éle van. 51. Mutassuk meg, hogy egy véges összefüggő gráfban található olyan élsorozat, amely valamennyi élét
tartalmazza. 52. Egy fagráf összefüggő G1 és G2 részgráfjának van közös éle. Jelöljük G3-mal azt a gráfot, amelynek élei
G1 és G2 közös élei, pontjai pedig a közös élek végpontjai. Igazoljuk, hogy G3 összefüggő gráf. 53. Lássuk be, hogy hibás a következő okoskodás.
Állítás: n pontú fának n-1 éle van. Megoldás: indukció n szerint. a. n=1 vagy 2-re triviális. b. Tegyük fel, hogy n pontú fákra igaz az állítás. Vegyünk hozzá egy n pontú fához egy új élt, melynek egyik végpontja az eredeti fában van, a másik végpontja új, egy n+1-edik pont. Így nyilván összefüggő körmentes gráfhoz, tehát fához jutunk. Az induló feltétel szerint az n pontú fának n-1 éle volt. Ehhez vettünk hozzá még egyet, n+1 pontú n=(n+1)-1 élű fához jutottunk. Hol a hiba? 54. Az alábbiakban egy-egy egyszerű gráfot definiálunk. Rajzoljuk le ezeket. a. Gráfunk 4! csúcsa négy ember lehetséges sorba állításait reprezentálja. Két csúcs össze van kötve,
ha az egyik sorba állításából két szomszédos ember felcserélésével a másik megkapható. b. A gráf csúcsai Magyarország megyéi. Két csúcs össze van kötve, ha a megfelelő megyék
szomszédosak. 55. Egy sakkversenyen n nő és 2n férfi vett részt. Mindenki mindenkivel pontosan egyszer játszott. Nem volt
döntetlen, és a nők által megnyert játszmák száma úgy aránylik a férfiak által megnyert játszmák számához, mint 7:5. Mekkora lehet az n? 56. Bizonyítsuk be, hogy egy 2n élű fa élhalmaza felbontható n darab diszjunkt párra, ahol egy párban
szomszédos elemek szerepelnek. 57. Lássuk be, hogy egy összefüggő gráfban bármely feszítő fának van legalább egy közös éle egy
tetszőleges szétvágó halmazzal. (G=(V, E) összefüggő gráfban X ⊆ E szétvágó halmaz, ha ∃ V1, V2, V1∪V2=V, V1∩V2=∅ oly módon, hogy X a V1 és V2 között futó élekből áll.) 58. Bizonyítsuk be, hogy a G=(V, E) összefüggő gráfban az F szétvágó halmaz akkor és csak akkor vágás, ha
a G'=(V, E-F) részgráfnak pontosan két komponense van. (Szétvágó halmazt lásd az előbbi példánál.)
5
1.2. Csoportok 1.2.1 Félcsoportok, csoportok 1. Az alábbi struktúrák közül válasszuk ki a félcsoportokat, illetve csoportokat: a. A természetes számok halmaza az összeadásra nézve. b. A páros számok halmaza az összeadásra nézve. c. A páratlan számok halmaza a szorzásra nézve. d. Az egész számok halmaza az összeadásra nézve. e. Az egész számok halmaza a szorzásra nézve. f. A nemnegatív racionális számok halmaza a szorzásra nézve. g. A pozitív racionális számok halmaza a szorzásra nézve. h. A nullától különböző valós számok halmaza a szorzásra nézve. i.
({a mod 35 | 35 /| a }, .) , ahol a művelet a maradékosztályok szorzása.
2. Vizsgáljuk meg a következő struktúrát:
(Z, o ), ha a o b=(a+b)/2, a, b∈Z.
3. Vizsgáljuk meg a következő struktúrát:
(Q, o ), ha a o b=(a+b)/2, a, b∈Q.
4. Vizsgáljuk meg a következő struktúrát:
és
(f o g)(x):=max ( f (x ), g ( x) ) .
5. Vizsgáljuk meg a következő struktúrát:
(A, o ), ha A a [0, 1]-en értelmezett valós függvények halmaza
(N0, o ), ha a o b= lnko(a,b), a, b∈N0.
6. Definiáljuk az R valós számok halmazán a o műveletet az alábbi módon: a o b:=a+b+ab. a. A o művelet kommutatív-e? b. A o művelet asszociatív-e? c. Van-e neutrális eleme (egységeleme) a struktúrának? d. Igazoljuk, hogy a o művelet invertálható az S:=R\{-1} halmazon. 7. Bizonyítsuk be, hogy ha egy csoport minden elemének inverze önmaga, akkor a csoport kommutatív. 8. Csoportot alkotnak-e az alábbiak? a. A (mod 35) maradékosztályok közül az A={0, 5, 10, 15, 20, 25, 30} által reprezentáltak az
összeadásra. b. A (mod 35) maradékosztályok közül A={0, 5, 10, 15, 20, 25, 30} által reprezentáltak a szorzásra. c. A (mod 35) maradékosztályok közül az A\{0} által reprezentáltak a szorzásra. d. A (mod 25) maradékosztályok közül a B={5, 10, 15, 20} által reprezentáltak a szorzásra. 9. Legyen (G, ⋅) csoport, u∈G rögzített elem. Definiáljunk G-n egy új o műveletet a o b:=a⋅u⋅b segítségével.
Csoport lesz-e (G, o )? 10. Vizsgáljuk meg a következő struktúrát: (R, osztás). 11. Vizsgáljuk meg a következő struktúrát: ( R*, osztás), ahol R*= R\{0}. 12. Vizsgáljuk meg a következő struktúrát: (Páros számok, o ), a o b:=(a, b)=lnko(a, b), (a, b páros szám).
6
13. A H={a, b, c} halmazon definiáljuk a ∗ műveletet a következő táblázattal:
∗
a
b
c
a
b
a
c
b
c
b
a
c
a
c
b
Állapítsuk meg, hogy a ∗ művelet
a. asszociatív-e,
b. invertálható-e,
c. reguláris-e.
14. Az alábbi struktúrák közül válasszuk ki a félcsoportokat, illetve csoportokat: a. A sík vektorainak halmaza az összeadásra nézve. b. A komplex számok halmaza az összeadásra nézve. c. Rögzített n természetes számra az n-edik egységgyökök halmaza a szorzásra nézve. d. Az összes komplex egységgyökök halmaza a szorzásra nézve. e. A valós elemű n-ed rendű mátrixok halmaza a szorzásra nézve. (n rögzített természetes szám.) f. A valós elemű n-ed rendű nem szinguláris (n rangú) mátrixok halmaza a szorzásra nézve. 15. Bizonyítsuk be, hogy ha a (G; ⋅) csoport minden a, b elempárjára (ab)2=a2b2, akkor a csoport
kommutatív.
1.2.2 Részcsoport, elem rendje, ciklikus csoport 16. A 8-adik komplex egységgyökök multiplikatív csoportjában határozzuk meg az egyes elemek rendjét,
generátumát. Ciklikus-e ez a csoport? 17. Adott egy sík és abban egy szabályos háromszög. Tekintsük azon síkbeli egybevágósági transzformációk
G halmazát, amelyek a szabályos háromszöget önmagába viszik át. A G halmazon értelmezzük a műveletet a transzformációk egymás utáni végrehajtásával (függvénykompozícióként). ( D3 diédercsoport.) a. Bizonyítsuk be, hogy G csoportot alkot. b. Határozzuk meg a G csoport rendjét. c. Jelölje ϕ a szabályos háromszög középpontja körüli pozitív irányú 120°-os elforgatást, τ pedig egy
magasságvonalra vonatkozó tükrözést. Határozzuk meg a {ϕ}, a {τ}, illetve a {ϕ, τ} halmazok által generált csoportokat. d. Határozzuk meg az egyes elemek rendjét. 18. A hatodik egységgyökök multiplikatív csoportjában határozzuk meg a generátorelemeket. 19. A komplex n-edik egységgyökök között milyen k érték esetén lesz εk= ε 1k generátorelem? 20. Bizonyítsuk be, hogy tetszőleges (G, ⋅) csoportban a és a-1 rendje egyenlő. 21. Bizonyítsuk be, hogy tetszőleges (G, ⋅) csoportban az a és b-1ab elemek rendje egyenlő. 22. Bizonyítsuk be, hogy ha a G csoport egyetlen másodrendű elemet tartalmaz, akkor ez az elem G minden
elemével felcserélhető. 23. Vizsgáljuk meg, hogy a következő algebrai struktúrák csoportot alkotnak-e? Ha igen, adjuk meg a
7
csoport rendjét. A csoportok közül melyek ciklikusak? a. Az m-mel osztható egész számok az összeadásra nézve. (m pozitív egész.) b. A mod m redukált maradékosztályok a szorzásra nézve. c. A mod m vett maradékosztályok a szorzásra nézve. d. Az egész számok halmaza az a o b:=a+b+1 műveletre nézve. 24. Bizonyítsuk be, hogy ha csoportban |c| =n és ck=e, akkor nk. (e az egységelem.)
[
]
25.Bizonyítsuk be, hogy kommutatív csoportban o(ab) o(a ), o(b) . 26. Lehet-e csoportban két véges rendű elem szorzata végtelen rendű? 27. Legyen G véges, párosrendű csoport. Bizonyítsuk be, hogy G-nek van olyan az egységelemtől különböző
eleme, amelynek az inverze önmaga.
1.2.3 Mellékosztályok, Lagrange-tétel, invariáns részcsoport, homomorf leképezések, faktorcsoport 28. Tekintsük a 17. feladatban szereplő G csoportot (síkbeli, szabályos háromszöget önmagába vivő
egybevágósági transzformációk). Jelölje H a τ által generált részcsoportot, K pedig a ϕ által generált részcsoportot. a. Határozzuk meg G összes részcsoportját. b. Határozzuk meg G-nek a H szerinti bal, illetve jobb oldali mellékosztályait. c. Határozzuk meg G-nek a K szerinti bal, illetve jobb oldali mellékosztályait. 29. Bizonyítsuk be, hogy ha G véges multiplikativ csoport, akkor minden a∈G-re a |G | = e (e a csoport
egységeleme). 30. Bizonyítsuk be az Euler-féle kongruencia-tételt csoportelméleti eszközökkel. 31. Egy csoport c elemére c100=e és c1999=e. Határozzuk meg c-t. 32. Legyen G csoport. Melyik igaz az alábbi állítások közül: a. Ha G-ben van másodrendű elem, akkor 2|G|. b. Ha 2|G|, akkor G-ben van másodrendű elem. c. Ha G-ben van negyedrendű elem, akkor 4|G|. d. Ha 4|G| akkor G-ben van negyedrendű elem. 33. Legyen G csoport. Melyik igaz az alábbi állítások közül: a. Ha |G|=81 és van olyan g∈G, amelyre g29≠g2, akkor G ciklikus. b. Ha |G|=54 és ∃ g∈G, melyre g29 ≠ g2, akkor G ciklikus. c. Ha |G|=81 és ∃ g∈G, amelyre g29=g2, akkor G nem ciklikus. 34. Tegyük fel, hogy G csoport, |G|=6k-1 (k∈N), G nem kommutatív, c∈G és c, c2, ..., ck mind különböző
elemek. Mennyi a
részcsoport szerinti bal oldali mellékosztályok száma? 35. Bizonyítsuk be, hogy ha egy G csoportnak van az egységelemtől különböző véges rendű eleme, akkor
van prímrendű eleme is.
8
36. Tekintsük a 17. és 28. feladatban szereplő G csoportot. A H és K részcsoportok invariánsak-e a szabályos
háromszögeket önmagába átvivő transzformációk G csoportjában? 37. Jelölje H valamely G csoportnak egy részcsoportját. Bizonyítsuk be, hogy ha |G:H|=2, akkor H invariáns
részcsoportja a G csoportnak. (H < G.) 38. Bizonyítsuk be, hogy ha H és K normálosztója a G csoportnak, akkor H∩K is normálosztója G-nek. 39. Legyen H az a elem által generált, K pedig a b elem által generált ciklikus csoport, és |a|=10, |b|=4. a. Létezik-e ϕ: H →K epimorf leképezés? b. Létezik-e ϕ: H →K homomorf leképezés?
Ha nem, akkor indokoljuk meg, hogy miért, ha igen, adjunk meg ilyen leképezéseket.
{
}
40. Legyen G = C \ {0} , H: = a a ∈ R, a ≠ 0 ∪ bi b ∈ R, b ≠ 0, i 2 = −1 , K := {x x ∈ C, x = 1}.
{
}
a. Lássuk be, hogy G, H, K a szorzásra nézve csoportot alkotnak. b. Lássuk be, hogy G /H ≅K. 41. Az alábbi struktúrák közül melyek izomorfak egymással? a. A valós számok az összeadásra (R, +). b. A pozitív valós számok a szorzásra (R+, ⋅). c. A nem nulla valós számok a szorzásra (R*, ⋅). 1 0 , c ∈ R mátrixok a szorzásra. d. Az 0 1 a a , a ≠ 0, a ∈ R mátrixok a szorzásra. e. Az a a f. A racionális számok az összeadásra (Q, +). 42. Az alábbi csoportok közül melyek izomorfak? a. A mod 15 redukált maradékosztályok a szorzásra. b. A mod 24 redukált maradékosztályok a szorzásra. c. A nyolcadik komplex egységgyökök a szorzásra. d. A négyzet szimmetriacsoportja (D4 diédercsoport). 43. Legyen G csoport A≤G, B≤G, |A|=6, |B|=15. I. Ha |G|=60, lehet-e
a. |A∩B|=1,
b. |A∩B|=3.
II. Ha |G|=90, lehet-e
a. |A∩B|=1,
b. |A∩B|=3.
1.2.4 Vegyes feladatok 44. Egy n elemű halmazon hány művelet értelmezhető? Ezek közül hány lesz kommutatív? Hánynak lesz egységeleme? A műveletek összeszámolásánál két műveletet akkor is különbözőnek tekintünk, ha az elemek alkalmas permutálásával egymásba vihetők (ezek tulajdonképpen "ugyanolyan" műveletek, csak a halmaz elemei másképpen vannak indexezve — a kétféle művelet által létrehozott algebrai
9
struktúra izomorf). 45. Melyek igazak az alábbi állítások közül? a. Ha van olyan a,b∈H, amelyre ab=ba=b, akkor a egységelem. b. Ha a művelet egységelemes, és valamely a,b∈H elempárra ab=ba=b, akkor a az egységelem. c. Ha a művelet egységelemes, valamely a,b∈H elempárra ab=ba=b, és b-nek van inverze, akkor a az egységelem. d. Ha a művelet asszociatív, egységelemes, valamely a,b∈H elempárra ab=ba=b, és b-nek van inverze, akkor a az egységelem. 46. Jelölje S a rendezett valós számpárok halmazát, azaz legyen S:={(a, b)a, b∈R}. Definiáljuk a ∗ műveletet az (a, b)∗(c, d):=(ac+2bd, ad+bc) módon. a. Igazoljuk, hogy a ∗ művelet asszociatív és kommutatív. b. Invertálható-e a ∗ művelet? c. Van-e egységelem? d. Lássuk be, hogy a QxQ\{(0,0)} halmazon a fenti művelet csoportot alkot. 47. Vizsgáljuk meg a következő struktúrákat: a. a∗b:=a+ab+b,
a, b∈C.
b. a o b=a-ab+b,
a, b∈C.
a b 2 2 , a +b =1 alakú mátrixok halmaza a szorzásra nézve 48. Vizsgálja meg, hogy a valós elemű − b a csoportot alkot-e? Ha igen, adja meg a csoport rendjét. 49. A G:={a, b, c, d} halmaz valamilyen o műveletre nézve csoportot alkot. Tudjuk, hogy a o b=c és b o d=a. Készítsük el a csoport művelettáblázatát. Melyik ismert csoporttal izomorf ez a csoport? 50. Lássuk be, hogy az összes negyedrendű csoport kommutatív. (Melyek a negyedrendű csoportok?) 51. Bizonyítsuk be, hogy ha a (G; ⋅) csoportban az a, b elemek kielégítik a következő feltételeket: a3=e, aba-1=b4 (e az egységelem), akkor a b elem rendje véges. 52. Adott egy sík és abban egy négyzet. Tekintsük azoknak a síkbeli egybevágósági transzformációknak a G halmazát, amelyek az adott négyzetet önmagába viszik át. A G halmazon értelmezzük a műveletet a transzformációk egymás utáni végrehajtásával (függvénykompozícióként). ( D4 diédercsoport.) a. Bizonyítsuk be, hogy G az adott műveletre nézve csoportot alkot. b. Határozzuk meg G rendjét. c. Határozzuk meg az egyes elemek rendjét. d. Jelölje ϕ a négyzet középpontja körüli pozitív irányú 90°-os elforgarást, τ pedig az egyik átlóra vonatkozó tükrözést. Határozzuk meg a {ϕ}, {τ}, {ϕ, τ},
{ϕ , τ} 2
halmazok által generált
részcsoportokat. 53. Tekintsünk egy szabályos tetraédert. Jelölje G a mozgás-transzformációknak (irányítás tartó
10
egybevágósági transzformációknak) a halmazát. Művelet legyen két transzformáció egymás utáni végrehajtása (függvénykompozíció). a. Bizonyítsuk be, hogy G csoport. b. Határozzuk meg G rendjét. c. Határozzuk meg az egyes elemek rendjét. 54. Bizonyítsuk be, hogy ha G csoport és H≤G, N < G, akkor H∩N < H. 55. Bizonyítsuk be, hogy csoportban az ab és ba elemek rendje megegyezik. 56. Lássuk be, hogy ha egy véges csoport minden egyes eleme másodrendű, akkor a csoport rendje 2 hatványa. 57. Igazoljuk, hogy az alábbi struktúrák csoportok. a. (Z, ∗), a∗b=a+b+5. b. (Z, o ), a o b=a+b–5. Állapítsuk meg, hogy az alábbi leképezések izomorfizmust létesítenek-e közöttük? i. a a –a,
ii. a a a+10,
iii. a a 2a+15.
{
}
58. Adjuk meg (Z4, +) és ( Z ∗5 , ⋅) között az összes izomorfizmusokat. ( Z ∗5 = 1 , 2, 3, 4, 5 mod 5 ). 59. A komplex számok C halmazában a ∗ és o műveleteket az alábbi módon értelmezzük: a∗b:=a+b+1, a o b:=a+b+i.
a. Igazoljuk, hogy a (C; ∗) és a (C; o ) struktúrák csoportok. b. Igazoljuk, hogy az a a ai leképezés izomorfizmust létesít a (C; ∗) és a (C; o ) csoportok között. 60. Lássuk be, hogy csoportban a. |ak|=|a|/lnko(k, |a|). b. Ha a⋅b=b⋅a, akkor |ab|lkkt(|a|, |b|). c. Ha a⋅b=ba és (|a|, |b|)=1, akkor |ab|=|a|⋅|b|. 61. Legyen a, b két véges rendű elem egy G Abel-csoportban. Igazoljuk, hogy van olyan c∈G, amelyre |c|=lkkt (|a|, |b|).
62. Lássuk be, hogy véges Abel-csoportban a legnagyobb elemrend minden elem rendjének többszöröse. 63. Bizonyítsuk be, hogy H csoport akkor és csak akkor epimorf képe a G véges ciklikus csoportnak, ha H ciklikus és rendje osztója G rendjének.
64. Legyen G=, H=, |G|=n, |H|=k. Melyek az összes ϕ:G→H homomorf leképezések, ha a. k=n,
b. n=6 és k=18.
11
1.3. Gyűrű, test 1.3.1 Gyűrű, test, integritási tartomány, nullosztó 1. Vizsgáljuk meg, hogy gyűrűt alkotnak-e az alábbi kétműveletes struktúrák: a. egész számok az összeadásra és szorzásra nézve; b. a páros számok az összeadásra és szorzásra nézve; c. adott n egész szám többszörösei az összeadásra és szorzásra nézve (az n=0 esetet külön nézzük meg);
{
}
d. a + b 2 a, b ∈ Z az összeadásra és szorzásra nézve;
f. {a + bi a, b ∈ Z} az összeadásra és szorzásra nézve (Gauss-egészek); g. az n-edrendű (nxn-es) egész elemű mátrixok a mátrix összeadásra és szorzásra nézve; h. az n-edrendű valós elemű mátrixok a mátrix összeadásra és szorzásra nézve. i. (Z m ,+,⋅) , a modulo m tekintett maradékosztályok a maradékosztály összeadásra és szorzásra. 2. Jelöljön (S; +) egy Abel-csoportot. Definiáljuk a o műveletet az alábbi módon: a o b:=0. 0 az (S; +) egységeleme. Bizonyítsuk be, hogy az (S; +, o ) struktúra gyűrű. (Ezt nevezzük zérógyűrűnek.)
3. Teljesüljenek az (R; +, ⋅) struktúrában a következő tulajdonságok: a. (R; +) csoport, b. (R; ⋅) egységelemes félcsoport, c. A szorzás az összeadásra nézve disztributív. Bizonyítsuk be, hogy (R; +, ⋅) gyűrű.
4. Bizonyítsuk be, hogy ha az (R; +, ⋅) egységelemes gyűrű minden elemének van multiplikatív inverze, akkor a gyűrűnek csak egyetlen eleme van.
{
}
5. Testet alkotnak-e a mod 2m maradékosztályok közül a párosak, 0 ,2 ,4 , 6 , ... 2 m − 2 a maradékosztályok közötti összeadásra és szorzásra, ha
a. 2m=10, b. 2m=20. 6. Bizonyítsuk be, hogy ha (T, +, ⋅) véges, legalább két elemet tartalmazó integritási tartomány, akkor test. 7. Milyen m értékre ismerünk m elemű gyűrűt, illetve testet? 8. Határozzuk meg a modulo 12 maradékosztályok gyűrűjében a nullosztókat. 9. Legyen (R,+,⋅) egységelemes gyűrű. Jelölje a nullelemet 0, az egységelemet e. Bizonyítsuk be, hogy ha az a∈R elemre fennáll az an=0 valamilyen n∈N-re (a nilpotens elem), akkor az e–a elemnek van inverze.
10. Mutassuk meg, hogy egy gyűrű egységeleme nem lehet két nilpotens elem összege. (Lásd előző példa) 11. Vizsgáljuk meg, hogy gyűrűt alkotnak-e az alábbi kétműveletes struktúrák:
{
}
a. a + b 3 a, b ∈ Z az összeadásra és szorzásra nézve. b. A [-1, 1] intervallumon értelmezett valós függvények a függvények összeadására és szorzására nézve. (Az f és g függvények összegét (f+g)(x)=f(x)+g(x), a szorzatát pedig az (f⋅g)(x)=f(x)g(x),
12
x∈[-1, 1] hozzárendeléssel definiáljuk.) a b , a, b ∈ R mátrixok a mátrix összeadásra és szorzásra. c. Az 2b a
{
}
12. Vizsgáljuk meg, hogy testet alkot-e az a + b 2 a, b ∈ Q halmaz az összeadásra és szorzásra nézve. 13. Végezzük el a kijelölt műveleteket a Z17 maradékosztály testben. a. (5 )
−1
b. 9 − 11 ,
,
(
)
c. 15 + 10 (3 + 5 )
−1
,
d. 1 ⋅ 2 ⋅ 3 ⋅ K ⋅ 16 .
14. Bizonyítsuk be, hogy ha egy (R; +, ⋅) egységelemes gyűrű a elemének van bal oldali multiplikativ inverze, akkor az a elem nem lehet a gyűrű bal oldali nullosztója.
{
}
15. Legyen D = x x ∈ Q, x = m ⋅ 2 k , m, k ∈ Z a véges diadikus törtek halmaza. Lássuk be, hogy a véges diadikus törtek az összeadásra és szorzásra integritási tartományt alkotnak, de nem alkotnak testet.
16.
a1. Tekintsük a Z10 maradékosztály-gyűrűt. Írjuk fel ebben minden elem (minden maradékosztály) osztóit.
a2. Mik az egységek, és mik a nullosztók? b. Legyen a a Z m maradékosztály-gyűrű egy maradékosztálya. Adjunk szükséges és elégséges feltételt arra, hogy mikor osztható minden maradékosztály a-val — vagyis hogy az a maradékosztály mikor egység.
1.3.2 Karakterisztika 17. Mutassuk meg, hogy ha egy R gyűrű minden a elemére a2=a teljesül, akkor R karakterisztikája 2 és kommutatív. (Boole-gyűrű.)
18. Legyen H halmaz, R={P(H), o , ∩}, ahol ( A o B = (A ∩ B ) ∪ (A ∩ B ) = ( A \ B ) ∪ ( B \ A) , a szimmetrikus differencia.) Lássuk be, hogy R gyűrű, keressük meg a nullelemét, és az egységelemét. Lássuk be, hogy R Boole-gyűrű. Keressünk benne nullosztót.
1.3.3 Oszthatóság, osztók, egységek, felbonthatatlan, prím 19. Ha valamely kommutatív gyűrűben a=a⋅e teljesül, következik-e ebből, hogy e egységelem? 20. a. Felbonthatatlan-e Z10-ben 5 ?
b. Prím-e Z10-ben 5 ?
21. Mely számok osztói az 1-nek a véges diadikus számok gyűrűjében? Mik az egységek? Adjunk egyszerű feltételt arra, hogy ebben a gyűrűben egy szám oszt egy másikat.
22. A véges diadikus számok gyűrűjében hány osztója van egy számnak. Lehet-e egy számnak nála nagyobb osztója is?
23. A véges diadikus számok gyűrűjében mely elemeknek van végtelen sok lényegesen különböző osztója? (Vagyis olyanok, amelyek nem csak egységszorzóban különböznek egymástól.)
24. A véges diadikus számok gyűrűjében felbonthatatlan-e a 12? 25. Melyek a felbonthatatlanok és melyek a prímek a véges diadikus számok gyűrűjében?
13
26. Legyen G:= {a + bi a, b ∈ Z} az összeadásra és szorzásra nézve (Gauss-egészek). Legyen ϕ(a+bi)=(a+bi)(a–bi)=a2+b2. Bizonyítsuk be ennek a leképezésnek a felhasználásával, hogy a Gauss-egészek körében az egységek 1, –1, i, –i.
1.3.4 Euklideszi gyűrű 27. A (páros számok, +, ⋅) integritási tartományt képeznek. Euklideszi gyűrű-e?
{
}
28. Legyen L:= a + bi 5 a, b ∈ Z a szokásos összeadással és szorzással. (L egészek.) a. Bizonyítsuk be, hogy az (L, +, ⋅) struktúra egységelemes integritási tartomány. b. Bizonyítsuk be, hogy az L egészek körében két egység van, ezek 1 és –1. 29. Lássuk be, hogy ha integritási tartományban létezik prím, akkor létezik egységelem.
{
}
30. Legyen L:= a + bi 5 a, b ∈ Z a szokásos összeadással és szorzással. a. Bizonyítsuk be, hogy az L egészek körében 1+i 5 , 1–i 5 , 2, 3, felbonthatatlan elemek, de nem prímelemek.
b. Bizonyítsuk be, hogy az (L, +, ⋅) gyűrű nem euklideszi gyűrű. 31. Igaz-e hogy ha érvényes az egyértelmű felbontás tétele valamely gyűrűben, akkor az euklideszi gyűrű?
{
}
32. Legyen H2:= a + b 2 a, b ∈ Z az összeadásra és szorzásra nézve, és ϕ(a+b 2 )=(a+b 2 )(a–b 2 )=a2–2b2. Bizonyítsuk be, hogy a (H2, +, ⋅) struktúra euklideszi
gyűrű.
33. Mik az egységek a 32. példabeli euklideszi gyűrűben.
1.3.5 Részgyűrű, ideál, faktorgyűrű 34. Melyek (Z4,+,⋅) részgyűrűi. Van-e köztük ideál? (Z4 a mod 4 maradékosztályok halmaza.) 35. Legyen R véges gyűrű, I ideál R-ben, és I≠R. Bizonyítsuk be, hogy I minden a nullelemtől különböző eleme nullosztó R-ben.
36. Határozzuk meg a (T, +, ⋅) test ideáljait. (Lássuk be, hogy testben nincs nem triviális ideál.) 37. Tekintsük a racionális számok (Q, +, ⋅) gyűrűjét. Bizonyítsuk be, hogy a páros egészek a racionális számok gyűrűjének részgyűrűjét alkotják, de nem ideálját.
38. Bizonyítsuk be, hogy az egész számok részgyűrűt képeznek a racionális számok gyűrűjében, de nem ideált.
39. Jelölje M a valós számtest feletti 2∗2-es mátrixok halmazát, a 0 a b , a, b ∈ R , illetve L= , a, b ∈ R . K= b 0 0 0
a. Igazoljuk, hogy (K, +, ⋅) bal oldali ideálja (M, +, ⋅)-nek de nem jobb oldali ideálja. b. Igazoljuk, hogy (L, +, ⋅) jobb oldali ideálja (M, +, ⋅)-nek, de nem bal oldali ideálja. 40.
a. Lássuk be, hogy a páros számok (P) az egészek részgyűrűjét, sőt ideálját alkotják.
14
b. Határozzuk meg a Z/P maradékosztály gyűrűt. a b a b a, b, c, d ∈ Z , és I= a, b, c, d ∈ 2Z 41. Legyen R= c d c d
a. Mutassuk meg, hogy I ideál R-ben.
b. Hány elemű az R/I faktorgyűrű?
42. Jelöljük N-nel az R kommutatív gyűrűben a nullosztók és a 0 által alkotott halmazt. a. Lehet-e, hogy N nem részgyűrű? b. Lehet-e, hogy N részgyűrű, de nem ideál? c. Bizonyítsuk be, hogy ha N ideál, akkor R/N nullosztómentes. d. Mely m-ekre igaz, hogy a mod m maradékosztály-gyűrűben N ideál? a b , a, b ∈ Z . Bizonyítsuk be, hogy az (M;+,⋅) struktúra izomorf az 43. Legyen M= 2b a
({a + b
} )
2 a, b ∈ Z ,+,⋅ gyűrűvel.
{
}
{
}
44. Izomorfak-e a G = a + b 2 a , b ∈ Z , + , ⋅) és K = a + b 3 a , b ∈ Z , + , ⋅) gyűrűk.
1.3.6 Vegyes feladatok 45. Bizonyítsuk be, hogy ha egy gyűrűben pontosan egy balegységelem van, akkor az szükségképpen egységelem.
46. Igazoljuk, hogy ha egy gyűrűben az 1–ab elemnek van inverze, akkor az 1–ba elemnek is van. 47. Írjuk fel a Z12 maradékosztály-gyűrűben minden elem osztóit! a b , a, b ∈ R . 48. Jelölje M a valós számtest feletti 2∗2-es mátrixok halmazát, valamint K= − b a
a. Igazoljuk, hogy (K, +, ⋅) részgyűrűje az (M, +, ⋅) gyűrűnek. b. Ideálja-e K az M-nek? a b , a, b ∈ R . Bizonyítsuk be, hogy a (K, +, ⋅) struktúra izomorf a komplex számok 49. Legyen K= − b a
testével.
15
2. Végeredmények 2.1. Gráfelmélet 2.1.1 Alapfogalmak 1. a. Igen.
b. Nincs.
2. Nincs. 3. Nincs. 4. a. 2
n 2
.
n b. 2 . m
5. A k+1≤n és 2nk feltételeket kielégítő k esetén van k-reguláris egyszerű gráf. 7. Nem. Egy n és egy n+1 pontú teljes gráf egyesítése az ellenpélda. 12. iii. A megoldás a Petersen-gráf.
13. 15. Ellenpélda:
G
G
16. b. Ellenpélda:
17. Van, például:
25. a. Legfeljebb n–1. Fák 26.
b. Legfeljebb n–2. Utak.
a. Nem. Például: b. Nem. Például:
27. a. Hurokél nem, egyébként igaz.
b.
Igen.
29.
16
30. 7. 31.
n( n − 1) 2
n − n + 1 = ( n − 1) − 1 . 2
32. a. c(G)=1, tehát G összefüggő. b. e(G)=v(G)–c(G), tehát G erdő.
2.1.2 Euler-gráf 35. Van:
2.1.3 Hamilton-út, kör 38.
39.
2.1.4 Síkbeli gráfok 44. Nem. 46. e (G ) =3v (G ) -6.
2.1.5 Vegyes feladatok 47. Háromszög vagy csillag, és akárhány izolált csúcs. 48. Út, kör, izolált csúcs. 55. n=3.
2.2. Csoportok 2.2.1 Félcsoportok, csoportok 1. a. félcsoport. b. csoport. c. egységelemes félcsoport. d. csoport. e. egységelemes félcsoport. f. egységelemes félcsoport. g. csoport. h. csoport. 2. nem művelet. 3. nem asszociatív, kommutatív, invertálható. 4. félcsoport, nincs egységelem, kommutatív, nem invertálható. 5. félcsoport, kommutatív, egységelem a 0, nem invertálható. 6. a. kommutatív. b. asszociatív. c. egységelem a 0.
17
8. a. csoport. b. egységelemes félcsoport. c. csoport. d. nem művelet. 9. csoport. 10. nem művelet. 11. nem asszociatív, jobb oldali egységelem az 1, bal oldali egységelem nincs. 12. félcsoport, kommutatív, egységelem a 0, nem invertálható. 13. a. nem asszociatív. b. invertálható. c. reguláris. Nem csoport! 14. e. egységelemes félcsoport, a többi csoport.
2.2.2 Részcsoport, elem rendje, ciklikus csoport 16. ciklikus. 17. b. G rendje 6. 18. ε1 és ε 5 . 19. (n, k ) = 1 esetén. 23. a. ciklikus csoport, m generálja. b. csoport, általában nem ciklikus. 26. Lehet.
2.2.3 Mellékosztályok, Lagrange-tétel, invariáns részcsoport, homomorf leképezések, faktorcsoport 31. c az egységelem. 32. d. nem igaz, a többi igen. 33. a. igaz, a többi nem. 34. 5. 36. H invariáns, K nem. 39. a. nem létezik, b. létezik. 41. a ≅ b ≅ d, c ≅ e. 42. egyik sem izomorf a másikkal. 43. I. a. nem lehet, b. lehet, II. a. lehet, b. lehet.
2.2.4 Vegyes feladatok 44. Műveletek száma n n , kommutatív műveletek száma n n(n +1) / 2 , egységelemes műveletek száma 2
2 n n − 2n + 2 .
45. csak d. igaz. 48. végtelen rendű csoport. 49. ciklikus csoport. 52. b. G rendje 8. 53. b. 12. 57. i. és ii. izomorfizmusok, iii. nem izomorfizmus.
18
2.3. Gyűrű, test 2.3.1 Gyűrű, test, integritási tartomány, nullosztó 1. Mindegyik gyűrű. 5. a. test, b. nem test. 7. Z m gyűrű, ha m pozitív egész szám. Z m test, ha m pozitív prímszám. 8. Nullosztópárok: (2,6), (3,4), (6,10), (6,8), (4,9). 11. Mindegyik gyűrű. 12. Test. 13. a. 7 , b. 15 , c. 1 , d. − 1 .
2.3.2 Karakterisztika 18. nullelem az üres halmaz, egységelem H. Bármely két diszjunkt halmaz nullosztó párt alkot.
2.3.3 Oszthatóság, osztók, egységek, felbonthatatlan, prím 19. Nem. 20. a. Nem. b. Igen. 21. 1 osztói ±2s ∀s∈Z -re. Ezek egyúttal az egységek is. (Végtelen sok egység.) 22. Végtelen sok, de nem végtetelen sok lényegesen különböző. Lehet egy számnak nála nagyobb osztója is. 23. Nincs. 24. Igen.
2.3.4 Euklideszi gyűrű 27. Nem euklideszi gyűrű. 31. Nem.
{} { } {
}
2.3.5 Részgyűrű, ideál, faktorgyűrű
34. 0 , 0, 2 , 0,1, 2, 3 . Mindegyik ideál is. 41. b. 16. 42. a. Lehet. b. Nem lehet. d. Ha m prímhatvány. 44. Nem.
2.3.6 Vegyes feladatok 48. b. Nem ideál.
19
