Označeni grafi

1. Definicija označenega grafa
2. Problem uravnoteženosti in razcepnosti
3. Napaka razvrstitve točk označenega grafa v dano število skupin
4. Iskanje razvrstitev z lokalno optimizacijo
5. Primeri

1. Iskanje čimboljših razvrstitev točk različnih označenih grafov v izbrano število skupin
   • sample66.net, sample2.net, sample9.net
   • Sampsonovi podatki: sam_aff2.net, sam_aff3.net, sam_aff4.net
   • Slovenske parlamentarne stranke 1993: stranke.net

1. Vsak študent dobi svoj označeni graf in v njem poišče razvrstitve točk v 1, 2,…n skupin (kjer je n število vseh točk v označenem grafu). Za vsako razvrstitev v dano število skupin izpiše skupno napako in število dobljenih rešitev s tako napako. Narišite še graf (napaka x število skupin) za vse tri izbrane tedne v Excelu.
   Za vsakega od treh tednov je potrebno izpisati razbitje (razvrstitev oseb v skupine), pri katerem dobimo najmanjšo skupno napako. Pravtako je treba narisati ustrezne preurejene matrike, ki prikazujejo najboljšo razvrstitev v skupine. Opis naloge

2. Interpretacija rezultatov v nekaj stavkih.