21 megoldottf feladat diszkrét matematikához - Varga Sándor

Országok listájaHungaryMiskolci EgyetemGépészmérnöki és Informatikai KarProgramtervező informatikusDiszkrét MatematikaJegyzetek21 megoldottf 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:
ElQszö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:  EMBED Equation.3 , ha  EMBED Equation.3 , 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  EMBED Equation.3 -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  EMBED Equation.3 -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 egyenlQek. 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 egyenlQ.
Tranzitív: minden  EMBED Equation.3 -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ékekbQl 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.  EMBED Equation.3  az R halmazon
Reflexív, mert  EMBED Equation.3 
nem szimmetrikus, mert ha  EMBED Equation.3 , akkor  EMBED Equation.3  nem lehet igaz.
Antiszimmetrikus, mert ha  EMBED Equation.3 , és  EMBED Equation.3 , akkor a=b.
Tranzitív, mert ha  EMBED Equation.3 , és  EMBED Equation.3 , akkor  EMBED Equation.3 .
S=((a,b) : a2+b2=1) az R halmazon;
Nem reflexív, mert  EMBED Equation.3 .
Szimmetrikus, mert ha  EMBED Equation.3 , akkor  EMBED Equation.3 .
Nem antiszimmetrikus mert ha  EMBED Equation.3 , és  EMBED Equation.3 , attól még  EMBED Equation.3 .
Nem tranzitív, mert ha  EMBED Equation.3 , és  EMBED Equation.3 , attól még
 EMBED Equation.3 .


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 mqködik, hogy mindig az egyes relációknak vannak közös változóik. ElQször ki kell fejezni az elsQ 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.  EMBED Equation.3 és  EMBED Equation.3  Adja meg  EMBED Equation.3  és  EMBED Equation.3  szorzatát.

S1-bQl, kijön a b értéke:  EMBED Equation.3 
Ezt behelyettesítve S2-be:  EMBED Equation.3 . Ez a megoldás.

b.  EMBED Equation.3 és  EMBED Equation.3 . Ezek szorzata:

S1-bQl kijön a b értéke:  EMBED Equation.3 .
Ezt behelyettesítve S2-be:  EMBED Equation.3 .

3. Ez a feladat heccbQl nincs itt (me még nemtom megódani!)



4. Van-e olyan legalább kétpontú gráf, amelyben minden pont foka különbözQ?

Van:

Egyetlen ellenpélda (
Ez elegendQ a bizo-
nyításhoz!




5. Van-e olyan 9 pontú gráf, melyben a pontok foka rendre:
7,7,7,6,6,6,5,5,5 ( VAN
6,6,5,5,4,4,3,2,2,1 ( VAN, de ez 10 db pont

Tétel: ÖsszefüggQ 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üggQ?

Visszatekintés:
Definíció: G (V,E) egyszerq gráfban a G=(V,VxV\E) 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 kijelenthetQ, hogy ha G nem összefüggQ, 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üggQvé válik.






7. Bizonyítsd be, hogy minden összefüggQ gráfból elhagyható egy pont, hogy a megmaradó gráf összefüggQ.

Ha az összefüggQ 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üggQ 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íthetQ ) lásd jobb oldali ábra.








Ez elvehetQ. Ez is elvehetQ.

A további lépésekben szintén elvehetQek elemek, és belátható, hogy bármelyik. A gráf a fenti módszert követve mindig összefüggQ marad, egészen addig, amíg már csak egy pontja lesz. (Persze, ha jobban megnézzük, akkor azok a pontok is elvehetQk 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:
ElQszö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:

.








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.

Ezeket összefoglalva:

 EMBED Equation.3 -ben nincs kör, ekkor  EMBED Equation.3 
 EMBED Equation.3 -ben sincs kör, ekkor  EMBED Equation.3 

 EMBED Equation.3  , és felhasználva azt, hogy  EMBED Equation.3 pontú teljes gráf, valamint eme teljes gráf éleinek száma, ahhoz, hogy ne legyen benne teljes kör:  EMBED Equation.3 . (Ez a fenti két képlet egyesítésébQl keletkezik.) És most a két egyenletünk közös oldalát (az e -t, azaz az élek számát) egymással egyenlQvé téve:

 EMBED Equation.3 , és ezt megoldva következik, hogy  EMBED Equation.3 . Azaz ha a pontok száma kisebb vagy egyenlQ 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.

9. Ha egy összefüggQ gráf minden pontja másodfokú, akkor a gráf egyetlen körbQl áll.

A bizonyítás egyszerq. Ha egy pontnak csak egy a fokszáma, akkor nem lehet kijönni belQle , 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örbQl áll, hiszen több helyen is ki lehet jönni belQle . Ezzel a tételt bizonyítottuk.

10. Igazold, hogy összefüggQ 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üggQ 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:








Azonban ezekkel a feladatot már be is bizonyítottuk.



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).
















Ezek alapján egy lehetséges megoldás: (vastaggal jelölve a változást)















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!












A megoldás lépésekben történik. ElQször A-ból kiindulva elmegyünk az összes szomszédos pontokba. Majd ezekbQl 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 kettQ közül a rövidebbet vesszük figyelembe. Ezek után a legrövidebb utakat képezQ 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. Keletkezett-e 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.


































15. Az F forrás az a, b, c, d, e, f, g betqket bocsátja ki 0,3; 0,3; 0,2; 0,05; 0,05; 0,05; 0,05 valószínqsé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ínqsé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ökkenQ sorrendre most is figyelni kell.) Jelen esetben az alábbi számsort kell kapnunk:











KövetkezQ 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évQ 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. Mennyi a forrás H(F) entrópiája?
Az entrópiára van egy képlet.  EMBED Equation.3 , ahol a Pi értékei rendre a valószínqségek. (Tehát a 0,3; 0,3; 0,3; és így tovább)

16. Az alábbi gráfról döntsük el, hogy

















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.)

 EMBED Equation.3 




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. Egyszerqen 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!

 EMBED Equation.3 



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:














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ítQ fája:




21. a. A következQ három kód közül melyek felbonthatóak?

Egy kód felbonthatósága azt jelenti, hogyha egy kódsorozatot állítunk elQ 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 egyenlQ szélességq 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 kezdQdik, 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íthetQ 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 elsQ két karaktert megvizsgálva nem lehet megállapítani, hogy melyikrQl is van szó. Ellenben az 10,110 prefix kód, mert az elsQ két karakterbQl meg lehet állapítani, hogy melyikrQl van szó.)
Mindent binárisan kell számolni, ezek alapján néhány alapvetQ mqvelet:
 EMBED Equation.3 
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.
ElsQ 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 mqveletet:
 EMBED Equation.3  (A kitevQ azért mínusz 2, mert 2 hosszúnak kell lennie a kódszónak)
Ezután vesszük a vesszQ utáni két számot (azért kettQt, 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 kettQ kitevQit, az elQzQ kódszavak hosszának függvényében. Így tehát:
 EMBED Equation.3 . Ezután vesszük a vesszQ 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 elQzQ:
 EMBED Equation.3 . A veszQ utáni három szám: 101.
Ötödik lépés:
 EMBED Equation.3 . A vesszQ utáni négy szám: 1100.
Hatodik lépés:
 EMBED Equation.3 . A vesszQ utáni négy szám: 1101.
Hetedik lépés:
 EMBED Equation.3 . A vesszQ utáni négy szám: 1110.
Tehát a kódok: 00,01,100,101,1100,1101,1110.
21 megoldott feladat Diszkrét Matematikához (Varga Sándor)


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 elQzQ pontba, ezért kell 2-vel osztani. Így jön ki a fent említett e=[n*(n-1)/2].

Az elsQ 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.

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.

Figyeljük meg, hogy a változtatásnál a csomópontokra most igaz, hogy a bemenQ értékek és a kimenQ é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).

 EMBED Equation.3 

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:

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 menQ ö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 lehetQ legtöbb víz jut. (Persze nem minden maximális út esetében tudjuk ennyire jól kihasználni a csatornákat, de a lehetQség szerint törekedni kell rá.)

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,6
0,4

0,3
0,3
0,2
0,1
0,1

0,3
0,3
0,2
0,2

0,4
0,3
0,3

Ha a végén kijövQ két szám összege egy, akkor a leképezés jó!

1
00
01

00
01
10
11

00
01
11
100
101

0
1

00
01
11
101
1000
1001

00
01
11
1000
1001
1010
1011

Például a negyedik oszlop vastag betqs részei (melyekbQl 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 felsQ 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.

Síkbarajzolható-e?
Ha  EMBED Equation.3 , 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örrQl 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.)

Ilyenkor a mátrix azt adja meg, hogy egy él mely pontok között található. (Például jelen esetben az elsQ él az elsQ és 3. pont között húzódik, mivel ott van 1-es.)

Az Euler-körbejárás a vastag vonallal jelölve. A szomszédsági gráf:

 EMBED Equation.3 

Hasonló témájú dokumentumok

Hozzászólások

11.05-2 2.zh 4.óra 8. adatbázis kezelés ágazati aszalós lászló biofizika biomérnöki citrátkör civilizáció dosztojevszkij elte épületfizika filológia forma formanyomtatvány földalatti tartály gazdasági glikolízis hallás házi doga ii. irodalomesztétika katalízis kérdések közigtöri linguistics média méretezés minőség munkaerőpiac oprendszerek orvosi kémia öko1 ökológiai antropológia öregedés politikatudomány prácser tamás reakció setting prices szerves szerződés szociolingvisztika tolsztoj tőke tőkeelmélet várak erődök vezgazd virológia