Algoritmien teoria, kevät 1999
Harjoitus 5, 22.2. klo 10-12 sali MaD380

1. Todista seuraavat yhtenäisen suuntaamattoman verkon G artikulaatiopisteitä ja 2-yhtenäisiä komponentteja koskevat väitteet (luentomuistiinpanojen s. 186):
   1. Kaaret ja kuuluvat G:n samaan 2-yhtenäiseen komponenttiin, jos ja vain jos tai G:ssä on sykli joka sisältää molemmat kaaret.
   2. Kahdella G:n 2-yhtenäisellä komponentilla on enintään yksi yhteinen solmu.
   3. G:n artikulaatiopisteet ovat täsmälleen sen 2-yhtenäisten komponenttien leikkaussolmut.
2. Määritä alla olevan verkon 2-yhtenäiset komponentit luennolla esitetyllä algoritmilla (muistiinpanojen s. 189a). Oletetaan, että solmut ovat vieruslistoissa aakkosjärjestyksessä ja että algoritmi aloittaa verkon tutkimisen solmusta a.

   

3. Laadi algoritmi, joka tutkii onko syötteenä annettu suuntaamaton verkko kaksijakoinen. Algoritmin tulee toimia verkon kaarien määrän suhteen lineaarisessa ajassa. (Syöteverkon solmuista ei siis ole valmiiksi sanottu, mitkä ovat jaon ``vasemmalla'' ja mitkä ``oikealla'' puolella. Huomaa kuitenkin, että kaksijakoisuusehdon mukaan ``vasemman puolen'' solmuista voi olla kaaria vain ``oikean puolen'' solmuihin ja päinvastoin.)
4. Binäärinen De Bruijnin jono on -bittinen binäärijono , joka syklisesti luettaessa sisältää kaikki k-bittiset binäärijonot osajonoinaan. (Esimerkiksi 00010111 on eräs De Bruijnin jono, missä k = 3.) Luonnostele algoritmi, joka tuottaa n-bittisen De Bruijnin jonon, missä n on muotoa , n:n suhteen lineaarisessa ajassa. (Vihje: Tarkastele suunnattua verkkoa , jonka solmut vastaavat kaikkia mahdollisia k-1-bittisiä binäärijonoja, ja solmusta on symboleilla 0 ja 1 nimetyt suunnatut kaaret solmuihin ja .)
5. Tarkastellaan seuraavaa ``edustajien valinta''-ongelmaa. Syötteenä annetaan kokoelma perusjoukon osajoukkoja . Tehtävänä on valita kustakin joukosta alkio siten, että , kun . Hahmottele algoritmi edustajien valintaan. (Vihje: Kaksijakoisten verkkojen pariutus.)