Primeri uporabe množice

Vaja

Sorodniki, prijatelji, sošolci, učitelji, sosedje, ... Gotovo poznaš vsaj kakih 100 ljudi. Sedaj pa si poskušaj predstavljati, koliko ljudi lahko »dosežeš« po dveh korakih; torej, kolikšno je skupno število znancev vseh tvojih znancev. Če ti to še ni dovolj, poskusi še s tretjim korakom, torej z znanci znancev znancev. Če bi tako nadaljeval, bi po kakih šestih ali sedmih korakih poznal že večino ljudi na svetu. V naslednji nalogi se bomo ukvarjali s podobnim problemom: zanimalo nas bo, katere osebe lahko podana oseba doseže po poljubnem številu korakov, če vemo, kateri ljudje se med sabo (neposredno) poznajo.

*Primer 3


Oglejmo si primer. Recimo, da velja n = 8 in da ima tabela poznanstva tako vsebino:

[ {1}, {0, 5, 7}, {4, 5}, {6},
  {2}, {1, 2, 7}, {3}, {1, 5} ]

To pomeni, da je edini znanec osebe 0 oseba 1, znanci osebe 1 so osebe 0, 5 in 7 itd.:

Množico oseb, dosegljivih od podane osebe (imenujmo jo dosegljive), gradimo postopoma. Ustvarimo jo kot prazno množico, nato vanjo dodamo podano osebo (dejansko njen indeks, a tega v nadaljevanju ne bomo več pisali), nato vse njene znance, nato vse znance njenih znancev itd. Postopek ponavljamo tako dolgo, dokler se množica dosegljive povečuje. Da se izognemo nenehnemu obravnavanju istih oseb, v vsakem koraku upoštevamo le tiste osebe, s katerimi smo množico dosegljive v prejšnjem koraku obogatili – torej osebe, ki jih pred prejšnjim korakom v množici še ni bilo. Oglejmo si postopek na primeru, ko nas zanima množica oseb, dosegljivih od osebe 0: