„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés

31. sor:

TODO

===6. Feladat===

~~TODO~~

Egy irányítatlan, élsúlyozott gráf az alábbi éllistával adott (zárójelben az élsúlyok):

* (a) Mi lehet x és y értéke, ha tudjuk, hogy az élsúlyok egész számok, és azt is tudjuk, hogy a B csúcsból indított Prim algoritmus az alábbi sorrendben vette be az értékeket: BE, ED, BA, BC.

* (b) Mely éleket és milyen sorrendben választja ki a Kruskal algoritmus? (Ha több megoldás is van, akkor az összeset adja meg!)

{{Rejtett

|mutatott=<big>'''Megoldás'''</big>

|szöveg=

[[File:2013_06_06_V2_6.png]]

'''a)''' Prim algoritmus - Ugyebár úgy dolgozik, hogy az aktuális fához a vele szomszédos élek közül a legkisebb súlyút veszi be. Prim: BE → ED → BA → BC

# A fához hozzáadjuk a BE élt.

# Most az ED élt választottuk. Ez alapján x értéke csak 1 lehet, így <math>x = 1</math>. (Feladatból kihagyták, hogy pozitív egészekről van szó, amúgy <math>x \le 1</math> lehetne.)

# Most az AB élt adjuk hozzá, ez alapján <math>y \ge 1</math>.

# Most a BC élt adjuk hozzá, ez alapján <math>y \ge 3</math>, így végül <math>y \ge 3</math>.

'''b)''' Kruskal algoritmus - Éleket nagyság szerint sorrendbe rakjuk, és növekvő sorrendben felvesszük a fához az éleket, vigyázva, hogy ne csináljunk kört.

1 súlyú - AB, BE, ED

2 súlyú - AE

3 súlyú - BC, AD, EC (és DC, ha <math>y = 3</math>)

Az összes megoldás:

#Az 1 súlyú éleket <math>3! = 6</math> féleképpen veheti fel az algoritmus (nem lehet belőlük kört csinálni, így itt nincsen para).

#Utána megpróbálná felvenni az AE élt, de azzal egy kört kapna, így nem veszi fel. Az AD éllel szintén így járna (~ezeket kéne pirosra színezni, ha olyan lenne a feladat).

#Maradtak a BC, EC és DC oldalak.

##Ha <math>y = 3</math>, akkor ezeket szintén 6 féleképpen veheti fel, tehát összesen 36 féleképpen futhat az algoritmus.

##Ha <math>y \ge 3</math>, akkor a DC oldal kiesik, a maradék 2 élt 2 féleképpen veheti fel, így 12 féleképpen futhat az algoritmus.

}}

===7. Feladat===

TODO

===8. Feladat===

TODO

@@ 31. sor: / 31. sor: @@
 TODO
 ===6. Feladat===
-TODO
+Egy irányítatlan, élsúlyozott gráf az alábbi éllistával adott (zárójelben az élsúlyok):
+<math>A:B(1), D(3), E(2); B:A(1), C(3), D(y); D:A(3), C(y), E(x); E:A(2), B(1), D(x).</math>
+* (a) Mi lehet x és y értéke, ha tudjuk, hogy az élsúlyok egész számok, és azt is tudjuk, hogy a B csúcsból indított Prim algoritmus az alábbi sorrendben vette be az értékeket: BE, ED, BA, BC.
+* (b) Mely éleket és milyen sorrendben választja ki a Kruskal algoritmus? (Ha több megoldás is van, akkor az összeset adja meg!)
+{{Rejtett
+|mutatott=<big>'''Megoldás'''</big>
+|szöveg=
+[[File:2013_06_06_V2_6.png]]
+'''a)''' Prim algoritmus - Ugyebár úgy dolgozik, hogy az aktuális fához a vele szomszédos élek közül a legkisebb súlyút veszi be. Prim: BE → ED → BA → BC
+# A fához hozzáadjuk a BE élt.
+# Most az ED élt választottuk. Ez alapján x értéke csak 1 lehet, így <math>x = 1</math>. (Feladatból kihagyták, hogy pozitív egészekről van szó, amúgy <math>x \le 1</math> lehetne.)
+# Most az AB élt adjuk hozzá, ez alapján <math>y \ge 1</math>.
+# Most a BC élt adjuk hozzá, ez alapján <math>y \ge 3</math>, így végül <math>y \ge 3</math>.
+'''b)''' Kruskal algoritmus - Éleket nagyság szerint sorrendbe rakjuk, és növekvő sorrendben felvesszük a fához az éleket, vigyázva, hogy ne csináljunk kört.
+súlyú - AB, BE, ED
+súlyú - AE
+súlyú - BC, AD, EC (és DC, ha <math>y = 3</math>)
+Az összes megoldás:
+#Az 1 súlyú éleket <math>3! = 6</math> féleképpen veheti fel az algoritmus (nem lehet belőlük kört csinálni, így itt nincsen para).
+#Utána megpróbálná felvenni az AE élt, de azzal egy kört kapna, így nem veszi fel. Az AD éllel szintén így járna (~ezeket kéne pirosra színezni, ha olyan lenne a feladat).
+#Maradtak a BC, EC és DC oldalak.
+##Ha <math>y = 3</math>, akkor ezeket szintén 6 féleképpen veheti fel, tehát összesen 36 féleképpen futhat az algoritmus.
+##Ha <math>y \ge 3</math>, akkor a DC oldal kiesik, a maradék 2 élt 2 féleképpen veheti fel, így 12 féleképpen futhat az algoritmus.
+}}
 ===7. Feladat===
 TODO
 ===8. Feladat===
 TODO