Nyt kun pandemiarajoitukset ovat helpottaneet, ihmiset ovat alkaneet tavata toisiaan jälleen kasvotusten. Mutta koska tapaamisesta on hetki, jos ystäväsi tarvitsevat jotain millä rikkoa jää, tässä on matemaattinen peli jota voi kokeilla.

Haasta kaikki kättelemään toisia ryhmässä, mutta vain parittoman määrän ihmisiä kanssa. (Kättely voi myös olla jokin muu kahdenvälinen tervehdys, esim. läpy.) Olettakaamme että ryhmässänne on sinä ja kuusi muuta ystävää.

Sanokaamme, että Anna ja Byron kättelevät toisiaan. Nyt kummallakin on yksi kättely.

Caitlin haluaa liittyä mukaan, joten hän kättelee Byronia kerran, joka on pariton luku. Mutta nyt Byronilla on kaksi kättelyä, joten hänen lukemansa on parillinen.

Demarr, Ernest ja Flora kättelevät myös kerran ja he muuttavat jokaisen parillisen määrän kätelleen parittomaksi ja parittoman parilliseksi.

Lopulta kuusi ystävää keksivät miten tämä ratkeaa, ja päätyvät hyväksyttävään ratkaisuun.

Mutta sinun pitää silti kätellä jotain toista, ja ylimääräinen kättely merkkaa. Kun kättelet jotain, jollain ystävälläsi on nyt parillinen lukumäärä kättelyitä. Ja näin peliä pitää jatkaa.

Ylläoleva kuva esittää pelin graafina — pisteiden joukkona (solmut) ja niiden välisinä viivoina (kaaret). Sinun dilemmasi toimii esimerkkinä yksinkertaisesta, mutta perustavanlaatuisesta ideasta graafiteoriassa, matematiikan alalla joka tutkii näiden representaatioiden ominaisuuksia. Vaikka monet graafiteorian tärkeät perusperiaatteet on keksitty jo satoja vuosia sitten, nykypäivän tieteilijät silti käyttävät niitä ymmärtääkseen paremmin sitä miten erilaiset järjestelmät kytkeytyvät toisiinsa, poliittisissa verkostoissa ja eläinten ekosysteemeissä ja internetin verkkosivuilla. Myös tätä peliä jota nyt pelaamme tutkitaan.

Oman pelimme graafissa ihmiset ovat solmuja ja kättelyt ovat kaaria. Numerot kuvaavat sitä miten monta kättelyä henkilöllä on, joka graafissa on tietyn solmun ”asteluku”: se on kunkin pisteeseen kytkeytyneiden kaarien lukumäärä.

Matemaatikkojen tutkimat graafit voivat muuttua suuriksi ja monimutkaisiksi, joten auttaa kun on joitain yksinkertaisia piirteitä, joita etsiä. Eräs tällainen piirre on graafin kaikkien astelukujen summa. Heti suoraan ”astelukusumma” kertoo meille, että seitsemällä pelaajalla pelimme on mahdotonta voittaa! Tarkastellaan hieman syytä.

Yksi tapa laskea graafin astelukusumma on listata kaikki yksittäiset asteluvut ja summata ne yhteen. Mutta toinen tapa nojaa välkkyyn kirjanpitoon kaarista. Koska jokainen kaari yhdistää kaksi solmua, sen kontribuutio kokonaissummaan on kaksi: yksi kummallekin solmulle joissa se on kiinni. Joten graafin astelukujen summaaminen on sama kuin laskisi jokaisen kaaren kaksi kertaa. Koska astelukusumma on kaksi kertaa kaarien määrä, mille tahansa graafille pätee, että summa on aina parillinen luku.

Näin pelimme on tuomittu epäonnistumaan. Mieti graafia, jonka me haluaisimme rakentaa voittaaksemme pelin: pitää olla seitsemän ihmistä ja seitsemän paritonta astelukua. Etsitään nyt astelukusumma: lisää ensimmäiset kaksi astelukua keskenään ja saamme parillisen luvun. Ja sen jälkeen seuraavaa summatessa saamme parittoman luvun. Ja sitten parillisen jne. Jos summaa parittoman määrän parittomia lukuja, summan on pakko olla pariton. Mutta koska minkä tahansa graafin astelukusumman pitää olla parillinen, me emme mitenkään voi rakentaa graafia, jolla olisi paritonta määrää parittomia kaaria. Peliämme ei voi voittaa.

Toisaalta, on mahdollista voittaa peli, jos on parillinen määrä pelaajia. Me näimme sen heti ensimmäisessä kättelyssä sinun vuorollasi.

Me itseasiassa näimme sen jo tuota ennen: heti kun ensimmäinen pari kätteli.

Jos peliä pelaa vain kaksi, silloin on mahdollista, että kumpikin heistä kättelee parittoman määrän muita käsiä. Voit ajatella tätä paria “parittomana aligraafina”, pienempänä graafina, joka on suuremman graafin sisällä, jonka kaikki kaaret ovat asteluvultaan parittomia.

Aligraafia rakentaessa valitset joukon solmuja ja tarkastelet ainoastaan näiden solmujen välisiä kaaria. Tämä tarkoittaa, että jätät huomiotta kaaret, jotka kytkeytyvät kaikkiin aligraafin ulkopuolisiin solmuihin.

Aligraafin muodostaminen leikkaa graafin kahtia, mitä graafiteoreetikot myös tekevät analysoidessaan graafeja: se voi auttaa heitä identifioimaan solmujen ryppäitä, jotka ovat kytkeytyneet toisiinsa erikoisin tavoin. Ja kun tietää, että aligraafi on joko parillinen tai pariton, se voi antaa lisätietoa graafin rakenteesta. Esimerkiksi, parillinen graafi, joka on “yhtenäinen” — mikä tarkoittaa, että aina löydät polun minkä tahansa kahden solmun välillä — on pakko sisältää “Eulerin piiri”, polku joka kulkee jokaisen kaaren kautta vain kerran.

Omasta seurapelistämme me tiedämme, että tietylle solmujoukolle ei ole aina mahdollista muodostaa paritonta graafia. Mutta aina on mahdollista muodostaa pariton aligraafi. Eräs tylsä tapa tämän saavuttamiseksi on juuri se mitä teimme yllä: valitse kaksi solmua, jotka ovat yhdistetty toisiinsa ja jätä huomiotta kaikki muut kaaret. Siitä syntyy pariton aligraafi, erittäin pieni sellainen. Onko se aina mahdollista löytää pariton aligraafi?

On jo tiedossa, että jokainen graafi sisältää suuren parillisen aligraafin. 1960-luvulla unkarilainen matemaatikko Tibor Gallai osoitti, että jokainen graafi voidaan osittaa kahdeksi parilliseksi aligraafiksi. Se jakaisi n solmun joukon kahdeksi alijoukoksi, ja yksi alijoukoista sisältäisi ainakin puolet kaarista. Tämä takaa sen, että jokaisella graafilla on parillinen aligraafi, joka on ainakin puolet alkuperäisen koosta.

Mutta miten suuri pariton aligraafi voi olla, se on ollut tutkimusten kohteena graafiteoriassa jo 60 vuoden ajan. Epäonnistuneen seurapelimme graafissa oli pariton aligraafi, jolla oli kuusi seitsemästä solmusta.

Tämä on varsin suuri verrattuna alkuperäiseen. Mutta tässä on toinen epäonnistunut yritys pelata pienemmällä maksimaalisen parittomalla aligraafilla, sellaisella joka käyttää vain neljää alkuperäisistä solmuista.

Etsittäessä suurinta mahdollista paritonta aligraafia, varhaiset onnistumiset ilmaisivat käytettyjen solmujen lukumäärän suhteessa alkuperäisen graafin kokoon. Esimerkiksi, 1990-luvulla matemaatikko Yair Caro näytti, että millä tahansa n solmun graafilla on oltava aligraafi, joka sisältää vähintään 1/(√n) kaikista solmuista. Tämä tarkoittaa, että 25 solmun graafilla on oltava pariton aligraafi, joka sisältää ainakin 1/5 kaikista solmuista, ja 100 solmun graafilla on oltava pariton aligraafi, joka sisältää vähintään 1/10 kaikista solmuista. Samanlaisia tuloksia saatiin muitakin, mutta matemaatikot etsivät Gallain löydöstä: yksittäistä suhdelukua, joka toimii parittomille aligraafeille sillä tavalla kuin 1/2 toimii parillisille aligraafeille.

Tällainen tulos saatiin viimein vuonna 2021, kun Asaf Ferber ja Michael Krivelevich osoittivat, että jokaisella graafilla on pariton aligraafi, joka käyttää ainakin 1/10000 solmua alkuperäisen graafin solmuista. Tämä voi olla aika alhainen raja, erityisesti kun jotkut ovat spekuloineet, että todellinen raja on jossain 2/7 tietämillä, mutta yksittäisen suhdeluvun löytäminen, joka toimii, mahdollistaa matemaatikkojen osoittaa, että sellainen suhdeluku on olemassa, joka parantaa jo olemassaolevaa suhdelukua. Yksi luku, niinkuin kättely, voi merkitä paljon.

Harjoituksia

1. Etsi suurin pariton aligraafi allaolevasta graafista.

2. Näytä miten osittaa allaoleva silmukka parittomaksi ja parilliseksi aligraafiksi.

3. Täydellinen n solmun graafi on graafi, jossa jokainen n solmusta on yhdistetty kaarella kaikkiin muihin solmuihin. Voiko täydellinen graafi olla pariton graafi?

4. 1960-luvulla Tibor Gallai osoitti, että aina on mahdollista osittaa graafi kahdeksi parittomaksi aligraafiksi. Perustuen siihen mitä tässä artikkelissa olet lukenut, osaatko osoittaa, että aina ei ole mahdollista osittaa graafia kahdeksi parittomaksi aligraafiksi? Mikä on syynä?

 

Artikkelin julkaissut Quanta Magazine (katso myös vastaukset harjoituksiin täältä)