Yksikköetäisyysverkoista

Tiede ja teknologia

13.8.2026

Verkkojen teorian alkuna voidaan pitää Königsbergin siltaongelmaa, jonka Leonhard Euler esitti 1700-luvun alkupuolella. Seuraavalla vuosisadalla verkkoja tarkasteltiin ensisijaisesti topologisesti ja niitä käytettiin esimerkiksi molekyylirakenteiden kuvaamiseen. Verkkoteoria formalisoitiin 1900-luvulla ja sille löydettiin monia käytännön sovelluksia. Tällä vuosituhannella verkkojen merkitystä ovat lisänneet valtavasti monimutkaisten, miljoonista tai jopa miljardeista osasista ja niiden välisistä yhteyksistä koostuvien ilmiöiden mallintaminen monimutkaisilla verkoilla ja näitä verkkoja analysoivien algoritmien kehittyminen.

Verkko (engl. graph) rakentuu oliopareista tai graafisesti tarkastellen pisteistä ja niitä yhdistävistä viivoista (kuva 1). Käsitteiden nimet eivät ole vakiintuneet. Verkon osina pisteistä käytetään nimityksiä solmu tai kärki (engl. node, vertex) ja viivoista nimityksiä kaari, linkki, särmä tai väli (engl. edge, arc, line). Polku (engl. path) on kahta solmua yhdistävä viiva, joka voi rakentua useista peräkkäisistä kaarista. Verkkoja luokitellaan muun muassa sen mukaan, ovatko ne yhtenäisiä tai haarautuvia, kuinka paljon solmuja on (ääretön määrä mukaan lukien), onko jokaisesta solmusta kaari jokaiseen muuhun solmuun (täydellinen verkko) tai voiko jokin polun osa olla rengas (sykli) eli toisin sanoen palata lähtösolmuun kulkematta kahta kertaa saman solmun kautta jms.

Kuva 1: Esimerkkiverkkoja. Kaksi vasemmanpuolimmaista eivät ole haarautuvia. Toinen vasemmalta on epäyhtenäinen, muut yhtenäisiä. Toisessa oikealta on yksi sykli. Oikeanpuolimmaista nimitetään puuksi.

Tässä jutussa tarkastelen esimerkinomaisesti muutamia sellaisia verkkoja, joissa kaikki kaaret ovat yhden pituusyksikön mittaisia (engl. unit distance graph)^[1]. Suora käännös voisi olla yksikköetäisyysverkko. Niitä voisi nimittää myös tasakaarisiksi tasasivuisen kolmion nimen mallin mukaan, sillä verkon visuaalinen hahmo on samanlainen (kokoa lukuun ottamatta), olivatpa kaaret minkä pituisia tahansa, kunhan ne vain ovat keskenään yhtä pitkiä. – Verkkoteoriasta on kirjoitettu paljon, myös Dimensiossa^[2], mutta useinkaan yksikköetäisyysverkkoja ei edes mainita.

Tetraedri

Ensimmäinen esimerkki on säännöllisen tetraedrin mallintaminen verkolla (kuva 2). Yksiulotteisessa avaruudessa tetraedrin vastine on jana, siis kaksi kärkeä (solmua) ja yksi särmä (kaari). Kaksiulotteinen ”tetraedri” saadaan, kun etsitään piste, joka on yhtä kaukana, janan etäisyydellä sen päätepisteistä, siis tasasivuinen kolmio. Kolmiulotteinen säännöllinen tetraedri saadaan, kun etsitään kolmannen ulottuvuuden suunnasta piste, joka on yhtä kaukana tasasivuisen kolmion kärjistä. Neliulotteinen ”tetraedri”, hypertetraedri eli pentatooppi (engl. pentatope) saadaan, kun etsitään neljännen ulottuvuuden suunnasta piste, jotka on yhtä kaukana tetraedrin kärjistä. Pentatoopin verkkomallissa on viisi solmua ja kymmenen kaarta.

Tasakaarisen hypertetraedriverkon rakentuminen ulottuvuuksien määrän n mukaan on hyvin säännöllistä. Solmuja on n + 1. Kaarien lukumäärä saadaan kaavasta

tai rekursiivisesti: edellisen ulottuvuuden verkon kaarien lukumäärä + edellisen ulottuvuuden solmujen lukumäärä. Muutkin säännölliset monitahokkaat voidaan esittää tasakaarisina verkkoina, joiden solmut ovat monikulmion kärjet ja kaaret monikulmion särmät, esimerkiksi dodekaedri^[3] ja hyperkuutio^[4].

Erdösin otaksuma

Vuonna 1946 Paul Erdös kysyi, kuinka monta sellaista pisteparia, joiden etäisyys on tasan yksi, voi tasossa olla, kun pisteitä on n (Erdösin yksikköetäisyysongelma)^[5]. Hän otaksui, että pisteparien lukumäärä on asymptoottisesti rajoitettu ja kasvaa vain vähän nopeammin kuin pisteiden lukumäärä. Toukokuussa 2026 OpenAI julkaisi tiedon, että tekoäly on osoittanut, että Erdösin otaksuma ei pidä paikkaansa^[6]^{, ^[7], ^[8]}.

Tasakaarisuus ei ole verkkoa määrittävä ominaisuus, vaan liittyy verkon graafiseen esittämiseen. Esimerkiksi kolmiulotteinen Petersenin verkko^[9] voidaan esittää graafisesti useana erilaisena 2D-projektiona^[10] (kuva 3). Siinä on 10 solmua ja 15 kaarta. Pienuudestaan huolimatta se on teoreettisesti merkittävä. Vastaavia esimerkkejä ovat Möbius-Kantorin verkko^[11]. ja Sierpinskin matto -verkko^[12]

Kuva 3: Petersenin verkon graafisia esityksiä: kolme 2D-mallia ja yksi 3D-malli [13] (oikeanpuoleinen). Kahdessa oikeanpuolimmaisessa kaaret ovat tasapituiset. Kuvat lähteistä [10] ja [12].

Esimerkkitehtäviä

Puhuminen verkkoteoriasta ja moniulotteisista verkoista saattaa tuntua kovin abstraktilta, mutta tasakaarisista verkoista saa monenlaista ja -tasoista ongelmanratkaisua ja -asettelua sekä kouluun että vapaa-ajan mielenvirkistykseksi. Yksinkertaisimmillaan yksikköetäisyysverkkoja voi piirtää käsin ruutupaperille. Eikä tarvitse ratkaista vain seuraavien kaltaisia valmiiksi muotoiltuja tehtäviä, vaan voit keksiä itse uusia.

Esimerkiksi kuinka monta erilaista yksikköetäisyysverkkoa voidaan piirtää, kun pisteitä on kolme, neljä, viisi jne ja solmujen pitää olla kokonaislukupisteissä (tai ruutuvihon ruutujen kärjissä), kun kierto- ja peilaussymmetrisiä pidetään samoina. Kuinka monta väriä tarvitaan kunkin verkon solmujen värittämiseen, kun minkään kaaren päissä olevat solmut eivät saa olla samanväriset?

Toinen esimerkki: miten 3, 4, 5, … pistettä on sijoitettava koordinaatiston kokonaislukupisteisiin (tai ruutuvihon ruutujen kärkiin), jotta yhtenäisen yksikköetäisyysverkon pisin polku olisi mahdollisimman lyhyt. Muuttuuko ratkaisu, jos koordinaatisto on vinokulmainen?

Kolmas esimerkki: verkko viritetään säännöllisen monikulmion n = 3, 4, 5, … joidenkin kärkipisteiden varaan. Kuinka monta erilaista tasakaarista verkkoa saadaan kullakin n:n arvolla?

Neljäs esimerkki: säännöllisen monikulmion n = 5, 6, 7, …kärkipisteistä kaksi on kokonaislukupisteissä. Kuinka monta olennaisesti erilaista yksikköetäisyysverkkoa, voidaan piirtää, kun otetaan mukaan kaikki monikulmion sisällä olevat kokonaislukupisteet? Kierto- ja peilaussymmetrisiä verkkoja pidetään samoina.