Polut ja kierrokset

Kaupungissa (ja varmaan maallakin) on miellyttävää ja hyödyllistä kuljeskella; kovin usein kuljeskelu on luonteeltaan päämäärätöntä tai muuten epämääräistä. Sellainenkin haahuilu on tarpeen, mutta epäilemättä miellyttävämpää (tai ainakin hauskempaa) liikunto on, jos sillä on selkeät tavoitteet — tai edes muoto. Tämä saitti yrittää tarjota kurinalaisia ja tavoitteellisia reittejä vaeltajille. Pääpaino on kävelyssä ja pyöräilyssä Helsingissä, sekä hengen- ja ruumiinravinnon hankkimisessa sanotussa kaupungissa.

Määritelmiä

6n-graf
Eräs suuntaamaton verkko (kuva: wikimedia)

Alla summittaiset määritelmät verkolle sekä erityisille poluille ja kierroksille.

  • Verkko eli graafi on kärkien (solmujen) ja niitä yhdistävien sivujen (kaarien, haarojen) joukko, jolle pätee että sivut ovat kärkien välisiä, yhdistävät kärkiä. Sivut voivat olla suunnistettuja; niitä pitkin saa “liikkua” vain toiseen suuntaan. Sivu, jonka kärjet yhtyvät, on silmukka.
  • Eulerin polku on sellainen polku, jossa verkon kaikki sivut esiintyvät tasan kerran, ja jokainen kärki vähintään kerran. Eulerin kierros on Eulerin polku, jonka alku- ja loppupäät yhtyvät eli ovat sama kärki.
  • Hamiltonin polku on sellainen polku, jossa verkon jokainen kärki esiintyy tasan kerran. Hamiltonin kierros on Hamiltonin polku, jonka alku- ja loppupäät yhtyvät (ovat sama kärki).

Leave a Reply

Your email address will not be published. Required fields are marked *