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

Vaje

  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

Naloga

  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 * število skupin) za vse tri izbrane tedne v Excelu. Izpisati je potrebno še razbitje (razvrstitev oseb v skupine), pri katerem dobimo najmanjšo skupno napako. Opis naloge

  2. Interpretacija rezultatov v nekaj stavkih.


Prosojnice Pajek 2.05 (PDF)
Prosojnice - zadnja verzija Pajka (PDF)
Testna označena omrežja (ZIP)