http://wiki.math.bme.hu/history/Informatika1-2012/HF5?feed=atom&Informatika1-2012/HF5 - Laptörténet2024-03-28T10:34:16ZAz oldal laptörténete a wikibenMediaWiki 1.18.1http://wiki.math.bme.hu/index.php?title=Informatika1-2012/HF5&diff=8043&oldid=prevRpalovics, 2012. október 23., 10:03-n2012-10-23T10:03:36Z<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">←Régebbi változat</td>
<td colspan='2' style="background-color: white; color:black;">A lap 2012. október 23., 10:03-kori változata</td>
</tr><tr><td colspan="2" class="diff-lineno">18. sor:</td>
<td colspan="2" class="diff-lineno">18. sor:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>*** colors[i]=0, ha az i. csúcs a B halmazba tartozik.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>*** colors[i]=0, ha az i. csúcs a B halmazba tartozik.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>* A függvény legyen képes '''nem összefüggő''' gráfok kezelésére is!</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>* A függvény legyen képes '''nem összefüggő''' gráfok kezelésére is!</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* A házit most is a következőképp küldjétek: A sage worksheetet a szokásos konvenció alapján (T2_HF5_kovacspisti) nevezzétek el, majd osszátok meg a sage szerveren palovics felhasználóval.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* <ins class="diffchange diffchange-inline">'''</ins>A házit most is a következőképp küldjétek:<ins class="diffchange diffchange-inline">''' </ins>A sage worksheetet a szokásos konvenció alapján (T2_HF5_kovacspisti) nevezzétek el, majd osszátok meg a sage szerveren palovics felhasználóval.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Segítség:</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Segítség:</div></td></tr>
</table>Rpalovicshttp://wiki.math.bme.hu/index.php?title=Informatika1-2012/HF5&diff=8042&oldid=prevRpalovics, 2012. október 23., 10:03-n2012-10-23T10:03:24Z<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">←Régebbi változat</td>
<td colspan='2' style="background-color: white; color:black;">A lap 2012. október 23., 10:03-kori változata</td>
</tr><tr><td colspan="2" class="diff-lineno">12. sor:</td>
<td colspan="2" class="diff-lineno">12. sor:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** A csúcsok száma a gráfban '''N''', a csúcsok indexelése: '''0..N-1'''</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** A csúcsok száma a gráfban '''N''', a csúcsok indexelése: '''0..N-1'''</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** Ha a gráf páros, akkor a csúcsai kettéoszthatók '''A''' és '''B''' diszjunkt halmazokra úgy, hogy csak ezen két halmaz között vannak élek.  </div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** Ha a gráf páros, akkor a csúcsai kettéoszthatók '''A''' és '''B''' diszjunkt halmazokra úgy, hogy csak ezen két halmaz között vannak élek.  </div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* A <del class="diffchange diffchange-inline">program </del>minden esetben adjon vissza ('''"return"''') egy listát ('''colors'''):</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* A <ins class="diffchange diffchange-inline">függvény </ins>minden esetben adjon vissza ('''"return"''') egy listát ('''colors'''):</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** Ha a gráf '''nem''' páros, akkor ez egy '''üres''' lista legyen.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** Ha a gráf '''nem''' páros, akkor ez egy '''üres''' lista legyen.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>**Ha a gráf páros, akkor ez a lista legyen '''N hosszúságú''', és colors[i] adja meg az i-edik csúcs "színét":</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>**Ha a gráf páros, akkor ez a lista legyen '''N hosszúságú''', és colors[i] adja meg az i-edik csúcs "színét":</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>*** colors[i]=1, ha az i. csúcs az A halmazba tartozik.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>*** colors[i]=1, ha az i. csúcs az A halmazba tartozik.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>*** colors[i]=0, ha az i. csúcs a B halmazba tartozik.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>*** colors[i]=0, ha az i. csúcs a B halmazba tartozik.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* A <del class="diffchange diffchange-inline">program </del>legyen képes '''nem összefüggő''' gráfok kezelésére is!</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* A <ins class="diffchange diffchange-inline">függvény </ins>legyen képes '''nem összefüggő''' gráfok kezelésére is!</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* A házit most is a következőképp küldjétek: A sage worksheetet a szokásos konvenció alapján (T2_HF5_kovacspisti) nevezzétek el, majd osszátok meg a sage szerveren palovics felhasználóval.</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Segítség:</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Segítség:</div></td></tr>
</table>Rpalovicshttp://wiki.math.bme.hu/index.php?title=Informatika1-2012/HF5&diff=8033&oldid=prevRpalovics, 2012. október 23., 09:16-n2012-10-23T09:16:26Z<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">←Régebbi változat</td>
<td colspan='2' style="background-color: white; color:black;">A lap 2012. október 23., 09:16-kori változata</td>
</tr><tr><td colspan="2" class="diff-lineno">1. sor:</td>
<td colspan="2" class="diff-lineno">1. sor:</td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>'''5. Házi Feladat'''</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">====</ins>'''5. Házi Feladat'''<ins class="diffchange diffchange-inline">====</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>(kitűző/javító: Pálovics Róbert)</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>(kitűző/javító: Pálovics Róbert)</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
</table>Rpalovicshttp://wiki.math.bme.hu/index.php?title=Informatika1-2012/HF5&diff=8031&oldid=prevRpalovics, 2012. október 23., 09:06-n2012-10-23T09:06:20Z<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">←Régebbi változat</td>
<td colspan='2' style="background-color: white; color:black;">A lap 2012. október 23., 09:06-kori változata</td>
</tr><tr><td colspan="2" class="diff-lineno">28. sor:</td>
<td colspan="2" class="diff-lineno">28. sor:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** 0. lépés: minden csúcsra colors[i]=-1, egyik csúcs sem "színes"</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** 0. lépés: minden csúcsra colors[i]=-1, egyik csúcs sem "színes"</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** 1. lépés: A BFS elindul a 0. csúcsból, elkezd színezni: colors[0]=0, colors[1]=1, colors[2]=1. Ezt azért teheti meg, mert a 0,1,2 csúcsok közül még egyik sem "színes".</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** 1. lépés: A BFS elindul a 0. csúcsból, elkezd színezni: colors[0]=0, colors[1]=1, colors[2]=1. Ezt azért teheti meg, mert a 0,1,2 csúcsok közül még egyik sem "színes".</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>** 2. lépés: a BFS ezután megvizsgálja az 1. csúcsot. Mivel colors[1]=1, ezért colors[2]=0 és colors[3]=0 kéne legyen. Azonban a 2. csúcs már az 1. lépés miatt színes: colors[2]=1 ellentétes színű, mint amilyenre most kéne színezni --> az <del class="diffchange diffchange-inline">elgoritmus </del>leáll, ez a gráf nem lehet páros gráf.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>** 2. lépés: a BFS ezután megvizsgálja az 1. csúcsot. Mivel colors[1]=1, ezért colors[2]=0 és colors[3]=0 kéne legyen. Azonban a 2. csúcs már az 1. lépés miatt színes: colors[2]=1 ellentétes színű, mint amilyenre most kéne színezni --> az <ins class="diffchange diffchange-inline">algoritmus </ins>leáll, ez a gráf nem lehet páros gráf.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>* A fentitől eltérő, egyéb megoldásokat is elfogadok, mindez csak segítség.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>* A fentitől eltérő, egyéb megoldásokat is elfogadok, mindez csak segítség.</div></td></tr>
</table>Rpalovicshttp://wiki.math.bme.hu/index.php?title=Informatika1-2012/HF5&diff=8030&oldid=prevRpalovics, 2012. október 23., 09:05-n2012-10-23T09:05:39Z<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">←Régebbi változat</td>
<td colspan='2' style="background-color: white; color:black;">A lap 2012. október 23., 09:05-kori változata</td>
</tr><tr><td colspan="2" class="diff-lineno">25. sor:</td>
<td colspan="2" class="diff-lineno">25. sor:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>* A szomszédoknak mindig ellentétes színűeknek kell lennie, mint a vizsgált csúcsnak.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>* A szomszédoknak mindig ellentétes színűeknek kell lennie, mint a vizsgált csúcsnak.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>* A nem összefüggő gráfok esetén a BFS algoritmust mindig újra kell indítani, legyen ez mindig a colors[] listában az első olyan csúcs, aki még nincs benne egyik halmazban sem.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>* A nem összefüggő gráfok esetén a BFS algoritmust mindig újra kell indítani, legyen ez mindig a colors[] listában az első olyan csúcs, aki még nincs benne egyik halmazban sem.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* Példa: A gráf: {0:[1,2], 1:[2,3]}</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* Példa: A gráf: {0:[1,2], 1:[2,3]}<ins class="diffchange diffchange-inline">, az algoritmus lépései:</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** 0. lépés: minden csúcsra colors[i]=-1, egyik csúcs sem "színes"</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** 0. lépés: minden csúcsra colors[i]=-1, egyik csúcs sem "színes"</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** 1. lépés: A BFS elindul a 0. csúcsból, elkezd színezni: colors[0]=0, colors[1]=1, colors[2]=1. Ezt azért teheti meg, mert a 0,1,2 csúcsok közül még egyik sem "színes".</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** 1. lépés: A BFS elindul a 0. csúcsból, elkezd színezni: colors[0]=0, colors[1]=1, colors[2]=1. Ezt azért teheti meg, mert a 0,1,2 csúcsok közül még egyik sem "színes".</div></td></tr>
</table>Rpalovicshttp://wiki.math.bme.hu/index.php?title=Informatika1-2012/HF5&diff=8029&oldid=prevRpalovics, 2012. október 23., 09:05-n2012-10-23T09:05:07Z<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">←Régebbi változat</td>
<td colspan='2' style="background-color: white; color:black;">A lap 2012. október 23., 09:05-kori változata</td>
</tr><tr><td colspan="2" class="diff-lineno">3. sor:</td>
<td colspan="2" class="diff-lineno">3. sor:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Döntsd el egy '''tetszőleges, irányítatlan gráfról''', hogy páros gráf-e, vagy nem. Segítség, instrukciók:</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Döntsd el egy '''tetszőleges, irányítatlan gráfról''', hogy páros gráf-e, vagy nem. Segítség, instrukciók:</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">Instrukciók:</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>* A feladat egy SAGE-ben írt függvény megírása, mely képes válaszolni a fenti kérdésre.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>* A feladat egy SAGE-ben írt függvény megírása, mely képes válaszolni a fenti kérdésre.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>* A függvény '''bemenete''' egy tetszőleges, irányítatlan (Graph) gráf.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>* A függvény '''bemenete''' egy tetszőleges, irányítatlan (Graph) gráf.</div></td></tr>
<tr><td colspan="2" class="diff-lineno">9. sor:</td>
<td colspan="2" class="diff-lineno">12. sor:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** A csúcsok száma a gráfban '''N''', a csúcsok indexelése: '''0..N-1'''</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** A csúcsok száma a gráfban '''N''', a csúcsok indexelése: '''0..N-1'''</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** Ha a gráf páros, akkor a csúcsai kettéoszthatók '''A''' és '''B''' diszjunkt halmazokra úgy, hogy csak ezen két halmaz között vannak élek.  </div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** Ha a gráf páros, akkor a csúcsai kettéoszthatók '''A''' és '''B''' diszjunkt halmazokra úgy, hogy csak ezen két halmaz között vannak élek.  </div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* A program minden esetben adjon vissza ('''return''') egy listát ('''colors'''):</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* A program minden esetben adjon vissza ('''<ins class="diffchange diffchange-inline">"</ins>return<ins class="diffchange diffchange-inline">"</ins>''') egy listát ('''colors'''):</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** Ha a gráf '''nem''' páros, akkor ez egy '''üres''' lista legyen.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>** Ha a gráf '''nem''' páros, akkor ez egy '''üres''' lista legyen.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>**Ha a gráf páros, akkor ez a lista legyen '''N hosszúságú''', és colors[i] adja meg az i-edik csúcs "színét":</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>**Ha a gráf páros, akkor ez a lista legyen '''N hosszúságú''', és colors[i] adja meg az i-edik csúcs "színét":</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>*** colors[i]=1, ha az i. csúcs az A halmazba tartozik.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>*** colors[i]=1, ha az i. csúcs az A halmazba tartozik.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>*** colors[i]=0, ha az i. csúcs a B halmazba tartozik.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>*** colors[i]=0, ha az i. csúcs a B halmazba tartozik.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">* A program legyen képes '''nem összefüggő''' gráfok kezelésére is!</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">Segítség:</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">* A megoldáshoz az egyszerű, irányított gráf paritását meghatározó algoritmust, és a szélességi keresés algoritmusát kell végiggondolni.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">* Kezdetben mindenki színe legyen -1, azaz minden i esetén colors[i]=-1</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">* A szomszédoknak mindig ellentétes színűeknek kell lennie, mint a vizsgált csúcsnak.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">* A nem összefüggő gráfok esetén a BFS algoritmust mindig újra kell indítani, legyen ez mindig a colors[] listában az első olyan csúcs, aki még nincs benne egyik halmazban sem.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">* Példa: A gráf: {0:[1,2], 1:[2,3]}</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">** 0. lépés: minden csúcsra colors[i]=-1, egyik csúcs sem "színes"</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">** 1. lépés: A BFS elindul a 0. csúcsból, elkezd színezni: colors[0]=0, colors[1]=1, colors[2]=1. Ezt azért teheti meg, mert a 0,1,2 csúcsok közül még egyik sem "színes".</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">** 2. lépés: a BFS ezután megvizsgálja az 1. csúcsot. Mivel colors[1]=1, ezért colors[2]=0 és colors[3]=0 kéne legyen. Azonban a 2. csúcs már az 1. lépés miatt színes: colors[2]=1 ellentétes színű, mint amilyenre most kéne színezni --> az elgoritmus leáll, ez a gráf nem lehet páros gráf.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">* A fentitől eltérő, egyéb megoldásokat is elfogadok, mindez csak segítség.</ins></div></td></tr>
</table>Rpalovicshttp://wiki.math.bme.hu/index.php?title=Informatika1-2012/HF5&diff=8028&oldid=prevRpalovics: Új oldal, tartalma: „'''5. Házi Feladat''' (kitűző/javító: Pálovics Róbert) Döntsd el egy '''tetszőleges, irányítatlan gráfról''', hogy páros gráf-e, vagy nem. Segítség, i…”2012-10-23T08:42:50Z<p>Új oldal, tartalma: „'''5. Házi Feladat''' (kitűző/javító: Pálovics Róbert) Döntsd el egy '''tetszőleges, irányítatlan gráfról''', hogy páros gráf-e, vagy nem. Segítség, i…”</p>
<p><b>Új lap</b></p><div>'''5. Házi Feladat'''<br />
(kitűző/javító: Pálovics Róbert)<br />
<br />
Döntsd el egy '''tetszőleges, irányítatlan gráfról''', hogy páros gráf-e, vagy nem. Segítség, instrukciók:<br />
* A feladat egy SAGE-ben írt függvény megírása, mely képes válaszolni a fenti kérdésre.<br />
* A függvény '''bemenete''' egy tetszőleges, irányítatlan (Graph) gráf.<br />
* A program '''"print"''' függvénnyel írja ki a kimenetre a gráf párosságát ('''"A gráf páros"''', vagy '''"A gráf nem páros gráf"''').<br />
* Jelölés a továbbiakhoz:<br />
** A csúcsok száma a gráfban '''N''', a csúcsok indexelése: '''0..N-1'''<br />
** Ha a gráf páros, akkor a csúcsai kettéoszthatók '''A''' és '''B''' diszjunkt halmazokra úgy, hogy csak ezen két halmaz között vannak élek. <br />
* A program minden esetben adjon vissza ('''return''') egy listát ('''colors'''):<br />
** Ha a gráf '''nem''' páros, akkor ez egy '''üres''' lista legyen.<br />
**Ha a gráf páros, akkor ez a lista legyen '''N hosszúságú''', és colors[i] adja meg az i-edik csúcs "színét":<br />
*** colors[i]=1, ha az i. csúcs az A halmazba tartozik.<br />
*** colors[i]=0, ha az i. csúcs a B halmazba tartozik.</div>Rpalovics