Matematika | Diszkrét Matematika » Varga Sándor - 21 megoldott diszkrét matematika feladat

21 megoldott feladat Diszkrét Matematikához (Varga Sándor) 1. Az alábbi relációk közül melyek reflexívek, szimmetrikusak, antiszimmetrikusak, tranzitívak? Visszatekintés: Először nézzük meg, hogy az egyes fogalmak mit is takarnak. (A példákban a kifejtés az S={sík egyenesei}, és RS={(x,y): x egy pontban metszi y-t} állítást takarja) - - - - Reflexív: xRx , ha x ∈ S , ez azt jelenti, hogy egy reláció egyik állítása önmagával igaz. A fenti példa NEM REFLEXÍV. Megoldás: Helyettesítsünk y helyére x-et Ekkor az állítás: x egy pontban metszi x-et. Ez nem lehet igaz, mert x „minden pontban metszi” x-et. Szimmetrikus: minden x, y ∈ S -re teljesül, ha xRx, akkor yRx. Ez azt jelenti, hogyha az állítás igaz, akkor a fordítottja is. A fenti példa SZIMMETRIKUS Állítás: Ha x egy pontban metszi y-ont, akkor y egy pontban metszi x-et. Ez igaz Antisszimmetrikus: minden x, y ∈ S -re teljesül, ha xRy és yRx, akkor x=y. Ez azt jelenti,

hogyha az állítás igaz, és az állítás fordítottja is igaz, akkor a két állítás értékei egyenlőek. A fenti példa NEM ANTISZIMMETRIKUS Állítás: Ha x egy pontban metszi y-ont, és y egy pontban metszi x-et, akkor x=y. Ez nem igaz, a két egyenes nem egyenlő. Tranzitív: minden x, y, z ∈ S -re teljesül, ha xRy és yRz, akkor xRz. Ez azt jelenti, hogyha egy állítás igaz, és egy ahhoz kapcsolódó másik állítás is igaz, akkor az az állítás is igaz, mely a nem kapcsolódó értékekből következik. (Ha csak két értékünk van, akkor fel kell venni egy harmadikat!) A fenti példa NEM TARNZITÍV. Állítás: Ha x egy pontban metszi y-ont, és y egy pontban metszi z-t, akkor x egy pontban metszi z-t. Ez nem igaz, hiszen x és z lehetnek párhuzamosak Megismerve a fenti eljárást, a kérdéses feladatok megoldása: a. b. ≤ az R halmazon Reflexív, mert a ≤ a nem szimmetrikus, mert ha a ≤ b , akkor b ≤ a nem lehet igaz. Antiszimmetrikus, mert ha a

≤ b , és b ≤ a , akkor a=b. Tranzitív, mert ha a ≤ b , és b ≤ c , akkor a ≤ c . S=((a,b) : a2+b2=1) az R halmazon; Nem reflexív, mert a 2 + a 2 ≠ 1 . Szimmetrikus, mert ha a 2 + b 2 = 1 , akkor b 2 + a 2 = 1 . Nem antiszimmetrikus mert ha a 2 + b 2 = 1 , és b 2 + a 2 = 1 , attól még a ≠ b . Nem tranzitív, mert ha a 2 + b 2 = 1 , és b 2 + c 2 = 1 , attól még a2 + c2 ≠ 1. 21 megoldott feladat Diszkrét Matematikához (Varga Sándor) 2. Számoljuk ki az alábbi valós számokon értelmezett relációk szorzatát: Visszatekintés: A relációk szorzata úgy működik, hogy mindig az egyes relációknak vannak közös változóik. Először ki kell fejezni az első relációból a közös változót, majd azt behelyettesíteni a második reláció ugyanezen változójának helyére. Megoldás: a. S1 = (a, b) : b = a 2 és S 2 = (b, c) : c = 3b − 5 Adja meg S1 és S 2 szorzatát S1-ből, kijön a b értéke: b = a 2 Ezt behelyettesítve S2-be: c = 3a 2 − 5

. Ez a megoldás b. S1 = (a, b) : a = 3b − 5 és S 2 = (b, c) : c = b 2 − 3b Ezek szorzata: a+5 . 3 2  a +5 Ezt behelyettesítve S2-be: c =   − (a + 5) .  3  S1-ből kijön a b értéke: b = 3. Ez a feladat heccből nincs itt (me még nemtom megódani!) 21 megoldott feladat Diszkrét Matematikához (Varga Sándor) 4. Van-e olyan legalább kétpontú gráf, amelyben minden pont foka különböző? Van: Egyetlen ellenpélda  Ez elegendő a bizonyításhoz! 5. Van-e olyan 9 pontú gráf, melyben a pontok foka rendre: a. 7,7,7,6,6,6,5,5,5  VAN b. 6,6,5,5,4,4,3,2,2,1  VAN, de ez 10 db pont Tétel: Összefüggő gráfban a páratlan fokú pontok száma mindig páros. Ennek értelmében az „a” példát figyelembe véve a páratlan pontok (7,7,7,5,5,5) darabszáma 6, tehát van ilyen gráf. A „b” példát nézve a páratlan pontok száma (5,5,3,1) tehát van ilyen 10 pontú gráf. 6. Igaz-e, hogy bármely G gráfra vagy G vagy G komplementere

összefüggő? Visszatekintés: Definíció: G (V,E) egyszerű gráfban a G=(V,VxVE) a G komplementere. Jelentése: Egy gráf komplementerét úgy képezzük, hogy a gráfban azon helyekre, ahol eddig nem volt él teszünk élet, ahol eddig volt él, onnan elvesszük. Pl.: G G Megoldás: Ezek után kijelenthető, hogy ha G nem összefüggő, akkor van legalább 2 komponense. Ilyen például a bal oldali ábra. Azonban 2 komponens komplementere már egy lesz, és a gráf összefüggővé válik. 21 megoldott feladat Diszkrét Matematikához (Varga Sándor) 7. Bizonyítsd be, hogy minden összefüggő gráfból elhagyható egy pont, hogy a megmaradó gráf összefüggő. Ha az összefüggő gráfban van olyan pont, melynek fokszáma egy, akkor az hagyható el. (lásd bal oldali ábra) Ha nincs ilyen pontja, akkor mindenképp található benne kör. (Mivel a kör feltétele, hogy egy pont fokszáma 2 legyen) A kör bármely pontját elhagyva a gráf még mindig összefüggő

marad. (Persze egy gráfban lehet több kör is Ilyenkor azon kör azon pontja hagyható el, amelyiknek a fokszáma 2. Ez további 2, vagy 1 fokszámú pontokat fog eredményezni. Így tehát az egész gráf „leépíthető”) lásd jobb oldali ábra Ez elvehető. Ez is elvehető. A további lépésekben szintén elvehetőek elemek, és belátható, hogy bármelyik. A gráf a fenti módszert követve mindig összefüggő marad, egészen addig, amíg már csak egy pontja lesz. (Persze, ha jobban megnézzük, akkor azok a pontok is elvehetők kezdetben, melyeknek fokszáma 2, de biztosabb, ha a fenti algoritmust követjük!) 8. Igazold, hogy bármely legalább 5 pontú gráfban vagy a komplementerében van kör. Visszatekintés: Először tisztázzuk, hogy a teljes gráf éleinek száma: e=[n*(n-1)]/2. Ezt tétel bizonyítja Teljes gráf alatt pedig azt a gráfot értjük, melynek pontjai az összes lehetséges módon össze vannak kötve egymással. (Észre kell venni, hogy ha egy

gráfot és komplementerét egyesítjük, akkor teljes gráfot kapunk.) Például az 5 feladat gráfjainak esetében a teljes gráf: . A gráf éleinek száma úgy jön ki, hogy egy pontból az összes többibe húzunk élt, illetve az utolsónak maradó pontból, csak n-1 élt húzunk. Azonban ha egy pontból egy másikba már húztunk élt, akkor abból már nem kell visszahúzni az előző pontba, ezért kell 2-vel osztani. Így jön ki a fent említett e=[n*(n-1)/2]. Továbbiakban be kell látnunk, hogy ha egy n pontú gráfban van n darab él, akkor tartalmaz kört. (Például próbáljunk négy pont közé négy élt berajzolni úgy, hogy ne legyen kör Nem fog sikerülni. Ellenben három élt még be lehet úgy rajzolni, hogy ne legyen kör) Megoldás: Ha G gráf nem tartalmaz kört, akkor legfeljebb n-1 éle van, tehát ha egy gráfban nincs kör, akkor e<=n-1. Ha G komplementerében sincs kör, akkor ott is teljesülnie kell annak, hogy e<=n-1. 21 megoldott feladat

Diszkrét Matematikához (Varga Sándor) Ezeket összefoglalva: G -ben nincs kör, ekkor e(G ) ≤ n − 1 G -ben sincs kör, ekkor e(G ) ≤ n − 1 n(n − 1) , és felhasználva azt, hogy G ∪ G = n pontú teljes gráf, valamint eme teljes gráf 2 éleinek száma, ahhoz, hogy ne legyen benne teljes kör: e(G ∪ G ) = 2(n − 1) . (Ez a fenti két képlet egyesítéséből keletkezik.) És most a két egyenletünk közös oldalát (az „e”-t, azaz az élek számát) egymással egyenlővé téve: e= n(n − 1) , és ezt megoldva következik, hogy n ≤ 4 . Azaz ha a pontok száma kisebb 2 vagy egyenlő néggyel, akkor nincs benne kör (sem pedig a komplementerében). Azaz, ha az élek száma legalább 5, akkor G-ben, vagy G komplementerében lesz kör. 2(n − 1) ≥ 9. Ha egy összefüggő gráf minden pontja másodfokú, akkor a gráf egyetlen körből áll. A bizonyítás egyszerű. Ha egy pontnak csak egy a fokszáma, akkor „nem lehet kijönni belőle”, azaz

végpont. Ha a gráfnak van végpontja, akkor nem lehet kör Ha pedig egy pontnak a fokszáma három vagy több, akkor a gráf több körből áll, hiszen „több helyen is ki lehet jönni belőle”. Ezzel a tételt bizonyítottuk 10. Igazold, hogy összefüggő gráf bármely két leghosszabb útjának van közös pontja. Három eset lehetséges: - a gráfban egyetlen pont van. Ebben az esetben a közös pont adott - A gráfban két pont van. Ebben az esetben a két pont egyben a legtávolabbi pontok is, tehát a megoldás adott. - A gráfban legalább három pont van. Ahhoz, hogy a gráf összefüggő legyen, szükséges, hogy minden pont valamilyen módon kapcsolatban álljon egy másikkal. Ilyenkor viszont az egyik „távoli pontból” el kell jutni a másik „távoli pontba”. Ha egy távoli pontból egy másik távoli pontba eljutunk úgy, hogy ne érintkezzünk legalább egy közös ponttal, akkor ez nem volt a leghosszabb út. Azaz a példát mutatva: Az első pontból

eljutva a másodikba, kereszteznünk kell a hármas számú pontot. Azonban ha úgy választanánk utat, hogy ne legyen közös pont (pl.: 2-3 pont közti élen), akkor az nem lenne leghosszabb. Ez pedig ellentmondana az állításnak. Azonban ezekkel a feladatot már be is bizonyítottuk. 21 megoldott feladat Diszkrét Matematikához (Varga Sándor) 11. Keressen az ábrán látható gráfban egy javító utat az s és t pont között, és végezzen el rajta egy javítást! (a számok a kapacitást, a karikázott számok a folyamértéket jelölik, ahol nem nulla). A lényeg, hogy keressünk egy olyan csatornát, ahol nincs még kihasználva a lehetséges kapacitás. Egy olyan csatornán, ahol nincs kihasználva a max. lehetséges kapacitás, oda lehet „pakolni” még valamennyit. Arra viszont vigyázni kell, hogy a csomópontok kapacitása úgymond „nulla”. Tehát egy csomópontba amennyi érték bemegy, annyinak ki is kell jönnie onnan. Ezek alapján egy lehetséges

megoldás: (vastaggal jelölve a változást) Figyeljük meg, hogy a változtatásnál a csomópontokra most igaz, hogy a bemenő értékek és a kimenő értékek összege 0-át ad. Ahhoz, hogy ezt elérjük csak arra kell odafigyelni, hogyha egy pontba menet a nyíl irányába növeltük a kapacitást, akkor egy másik nyílon csökkenteni kell. (Olyanon, amelyiknek az iránya a pontba mutat). A minimális vágás a maximális folyam. (Ezt a szaggatott vonal jelöli) 12. Az alábbi gráfban keressük meg Dijkstra algoritmusával a legrövidebb utakat az A pontból a többi pontba! 21 megoldott feladat Diszkrét Matematikához (Varga Sándor) A megoldás lépésekben történik. Először A-ból kiindulva elmegyünk az összes szomszédos pontokba. Majd ezekből kiindulva megint továbblépkedünk, úgy hogy az utak távolságát összeadogatjuk, és leírjuk a csomópontok fölé. Ha olyan helyre érünk, ahová egy másik útról már eljöttünk, akkor a kettő közül a

rövidebbet vesszük figyelembe. Ezek után a legrövidebb utakat képező utakat kiemeljük. Ezek alapján a megoldás: Látható, hogy bármilyen egyéb úton haladva az összutak száma nagyobb lesz mint a kijelölt, tehát ezek a legrövidebb utak. 13. a, Mennyi a K= (0011010; 1000110; 1000001) kód kódtávolsága? A kódtávolság az egyes kódok értékei közti különbség minimuma. Jelenleg 3 b. Tegyük fel, hogy minden üzenetben legfeljebb 2 hiba keletkezik Keletkezette hiba az üzenetben, ha az 1000110 üzenetet kaptuk meg? És ha az 1111111 üzenetet? Tehát 2 hibát még nem tudunk azonosítani. 1000110 benne van a kódtáblába, tehát nem hibás 1111111 a 0011010-tól 4 helyen, 1000110-tól is 4 helyen, 1000001-tól 5 helyen tér el. Tehát hibás. (Ha akárcsak az egyik helyen is 2 helyen térne el a kód, akkor elfogadható lenne, mert ezt adta meg a feladat szövege.) 14. Az alábbi gráfban keressünk maximális folyamot az s pontból a t pontba A maximális

folyam azt jelenti, hogyha az utakat csöveknek feltételezzük (melyek kapacitása adott), akkor az S pontot mennyi vizet lehet beönteni, hogy az mind eljusson T pontba. Tehát meg kell keresni azt az utat, melynek a legnagyobb az összkapacitása. Persze itt is érvényes, hogy egy csomópontba „amennyi víz befolyik, annyi ki is kell, hogy folyjék. Valójában a javító út kereséséhez hasonló a feladat, azonban itt a maximális kapacitáskihasználás a cél. Ezt akkor érjük el, ha már nincs több javító út. Tehát az összes lehetséges javító útak összessége a maximális folyam. Ezek alapján a feladat megoldása: 21 megoldott feladat Diszkrét Matematikához (Varga Sándor) A példában a karikázott számok a már megszokott módon a folyamértéket jelölik. Valójában az ábrán látható, hogy ez két javítható út, és ezek összessége (a vastag vonallal jelölt rész) a maximális folyam. Onnan is látszik, hogy ez a maximális folyam, hogy a

T-be menő összes csatorna kapacitása maximálisan kihasznált. Tehát, mindegy, hogy ezeken kívül hogy oszlik meg a kapacitás, a lényeg az, hogy T-be a lehető legtöbb „víz” jut. (Persze nem minden maximális út esetében tudjuk ennyire jól kihasználni a csatornákat, de a lehetőség szerint törekedni kell rá.) 15. Az F forrás az a, b, c, d, e, f, g betűket bocsátja ki 0,3; 0,3; 0,2; 0,05; 0,05; 0,05; 0,05 valószínűségekkel. b.Konstruáljunk meg egy optimális prefix kódot és számoljuk ki ennek költségét! Ez valójában a Huffmann kód. Felírjuk egymás alá az összes valószínűséget A két legutolsót összeadjuk, és felírjuk ismét az egész számsort, de úgy, hogy az összeadott értékeknek már csak az összege szerepeljen. (Természetesen a csökkenő sorrendre most is figyelni kell) Jelen esetben az alábbi számsort kell kapnunk: 0,3 0,3 0,2 0,05 0,05 0,05 0,05 0,3 0,3 0,2 0,1 0,05 0,05 0,3 0,3 0,2 0,1 0,1 0,3 0,3 0,2 0,2 0,4 0,3 0,3

0,6 0,4 Ha a végén kijövő két szám összege egy, akkor a leképezés jó! Következő lépésként visszafele járunk el. Leírjuk a 0-át és 1-et, majd a nyilakat megfordítva elkezdünk visszafele lépkedni. Leírjuk a fennmaradó számokat, majd a nyíl tövénél lévő számot két példányban a nyíl hegyéhez, és utánaírunk egy 1-est, és egy 0-át. Végeredménynek a prefix Huffmann kódot kapjuk. Az ábrán ugyanez: a. 00 01 11 1000 1001 1010 1011 00 01 11 101 1000 1001 00 01 11 100 101 00 01 10 11 1 00 01 0 1 Például a negyedik oszlop vastag betűs részei (melyekből nem jön ki nyíl) változatlanul le vannak írva a harmadik oszlopban, a nyilazott rész pedig egy 1-es és egy 0 kíséretében szintén a sor végére van téve. A nyilak egy az egyben a felső táblázat nyilazását követik. (Például a második oszlopban azért a negyedik sorból ágazik szét a nyíl, mert a bontásnál a negyedik sorba torkollott. 21 megoldott feladat

Diszkrét Matematikához (Varga Sándor) A. Mennyi a forrás H(F) entrópiája? n 1 , ahol a Pi értékei rendre a pi i =1 valószínűségek. (Tehát a 0,3; 0,3; 0,3; és így tovább) Az entrópiára van egy képlet. H ( F ) = ∑ pi * log 2 16. Az alábbi gráfról döntsük el, hogy Síkbarajzolható-e? Ha e ≤ 3n − 6 , akkor igen. (n a pontok, e az élek száma) Jelen esetben 13 él és 6 pont van, tehát nem rajzolható síkba. Van-e benne Euler-kör? Ha van páratlan fokszámú pont, akkor nem lehet a gráfban Euler kör. Jelen esetben tehát nincs benne Euler kör (ld Nyíllal jelölt rész) Van-e benne Hamilton kör? Hamilton körről beszélünk akkor, ha találunk olyan utat, mely minden pontot csak egyszer megy át. Van ilyen, méghozzá vastag vonallal jelölve. (Ha egy n pontú gráfban minden pont fokszáma legalább n/2, akkor a gráfban van Hamilton kör.) 17. Adja meg az alábbi szomszédsági mátrix alapján a gráfot! (Vagy a gráf alapján a szomszédsági

mátrixot.) P1 P 2 P3 P 4 P5 2 1 1 1 P1 1 0 1 2 1 P2 2 1 0 1 1 P3 1 2 1 1 2 P4 1 1 1 2 1 P5 1 Felvesszük az öt pontot. A mátrix sorai és oszlopai a gráf egyes pontjai közti élek számát adják meg. Egyszerűen fel kell rajzolni a gráfot (Fordított esetben a mátrixot kell felírni) 18. Adja meg az alábbi illeszkedési mátrix alapján a gráfot! 1él 2él 3él P1 1 0 1 P2 0 1 1 P3 1 1 0 Ilyenkor a mátrix azt adja meg, hogy egy él mely pontok között található. (Például jelen esetben az első él az első és 3. pont között húzódik, mivel ott van 1-es.) 21 megoldott feladat Diszkrét Matematikához (Varga Sándor) 19. Definiálja a síkbarajzolható gráf, Euler-kör, Hamilton-kör és a kromatikus szám fogalmát. Adja meg az alábbi mátrix Euler-körbejárását, kromatikus számát, szomszédsági mátrixát! Síkbarajzolható gráf: Egy G gráfot síkbarajzolhatónak nevezünk, ha le lehet rajzolni a síkba úgy, hogy az élei ne messék egymást. (A

képlethez lásd 15 feladat) Euler-kör: A G gráf Euler-körének nevezünk egy körsétát, ha minden élen pontosan egyszer megy át. Hamilton-kör: Hamilton körnek nevezünk egy olyan kört, ami mindegyik ponton pontosan egyszer megy át. Ezek a példagráffal: Az Euler-körbejárás a vastag vonallal jelölve. A szomszédsági gráf: A B C A B C 0 1 1 1 0 0 1 0 0 D E 0 1 1 1 0 1 F 1 1 0 D E F 0 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 20. Adjunk meg az alábbi gráfban egy minimális súlyú feszített fát! Mohó-algoritmus: Mindig vesszük azt a legolcsóbb élet, amit még lehet venni úgy, hogy ne keletkezzen kör. Például egy gráf feszítő fája: 21 megoldott feladat Diszkrét Matematikához (Varga Sándor) 21. a A következő három kód közül melyek felbonthatóak? Egy kód felbonthatósága azt jelenti, hogyha egy kódsorozatot állítunk elő a kód elemeinek segítségével, akkor abból szét-e tudjuk válogatni az eredeti kód elemeit. (Tehát tudjuk e

dekódolni.) Az alábbi példák a jobb megértésért: K1=(1110;0110;1101). Minden egyenlő szélességű kód felbontható (Pl: az alábbi kódot készítjük a kód elemeinek segítségével: 111011011110011011011110, ezt fel tudjuk bontani négyes csoportokra: (1110,1101,1110,0110,1101,1110), tehát dekódolható. K2=(10;101;111). Nem felbontható (Pl: Az alábbi kódot generáljuk az elemek segítségével: 101111 Ez most 10,111 vagy 101,11. és így tovább) K3=(01;011;0111). Felbontható (Pl: Az alábbi kódot generáljuk: 0101101011101011 Ezt fel tudjuk bontani. Minden kód 0-ával kezdődik, tehát tudjuk, hogyha 0-ával találkozunk, akkor az egy új kód. Így a dekódolás: 01,011,01,0111,01,011) b. Konstruáljunk olyan prefix kódot, melyben az egyes kódszavak hossza rendre (2,2,3,3,4,4,4)! Prefix kód: Minden kód pontosan elkülöníthető egymástól, egyik kód nem része egy másiknak. (Pl: nem prefix kód a 10,100 számpáros, hiszen az első két karaktert

megvizsgálva nem lehet megállapítani, hogy melyikről is van szó. Ellenben az 10,110 prefix kód, mert az első két karakterből meg lehet állapítani, hogy melyikről van szó.) Mindent binárisan kell számolni, ezek alapján néhány alapvető művelet: 0,001 + 0,001 = 0,01 2 −1 = 0,1 2 − 2 = 0,01 0,01 + 0,01 = 0,1 0,01 + 0,1 = 0,11 2 −3 = 0,001 Természetesen ezek az elemi matematika részét képezik. A kód generálásához bontsuk lépésekre a kódszavakat. Első lépés: 2 hosszú kódszó. Ez legyen 00 (Három hossz esetén 000 lenne) Második lépés: 2 hosszú kódszó. Felírjuk az alábbi műveletet: 2 −2 = 0,01 (A kitevő azért mínusz 2, mert 2 hosszúnak kell lennie a kódszónak) Ezután vesszük a vessző utáni két számot (azért kettőt, mert ilyen hosszúnak kell lennie a kódszónak.) Ez 01, ez a második kódszó Harmadik lépés: 3 hosszú a kódszó. Összeadjuk a kettő kitevőit, az előző kódszavak hosszának függvényében. Így tehát:

2 −2 + 2 −2 = 0,1 . Ezután vesszük a vessző utáni három számot (Azért ennyit, mert ilyen hosszúnak kell lennie a kódszónak) Ez 100, ez a harmadik kódszó. Negyedik lépés: Akárcsak az előző: 2 −2 + 2 −2 + 2 −3 = 0,01 + 0,01 + 0,001 = 0,101 . A vesző utáni három szám: 101 Ötödik lépés: 2 −2 + 2 −2 + 2 −3 + 2 −3 = 0,11 . A vessző utáni négy szám: 1100 Hatodik lépés: 2 −2 + 2 −2 + 2 −3 + 2 −3 + 2 −4 = 0,1101 . A vessző utáni négy szám: 1101 Hetedik lépés: 2 −2 + 2 −2 + 2 −3 + 2 −3 + 2 −4 + 2 −4 = 0,1110 . A vessző utáni négy szám: 1110 Tehát a kódok: 00,01,100,101,1100,1101,1110