13  Verkot

13.2 Perusidea

Tutkitaan seuraavia tilanteita:

• Jotkin ihmiset ovat ystävyksiä keskenään.
• Jotkin tieto­koneet ovat yhteydessä toisiinsa.
• Joistakin kaupungeista on teitä toisiinsa.
• Jotkin jalka­pallo­joukkueet pelaavat toisiaan vastaan.

Pelkistettynä jokaisessa tilanteessa on kyse asioista, joiden välillä on yhteyksiä. Tällaisia tilanteita voidaan kuvata verkoilla. Alla on esimerkki verkosta.

Kuvan verkossa on viisi solmua (numeroitu $1, 2, 3, 4, 5$). Niiden välisiä yhteyksiä on havainnollistettu kuvissa janoilla. Näitä janoja kutsutaan verkon kaariksi. Kuvan 13.1 verkossa on kuusi kaarta.

Verkkojen piirtäminen on hyvä tapa visualisoida tehtävissä esiintyviä tilanteita. Piirtäessä ei ole väliä, mihin paikkoihin solmut piirtää. Oleellista on vain, mitkä solmut on yhdistetty toisiinsa kaarella. (Eli solmut kannattaa piirtää sellaisiin paikkoihin, että kuva on selkeä.)

13.3 Esimerkki­tehtäviä

Tehtävää voisi olla vaikea tunnistaa verkko­tehtäväksi, ellei se esiintyisi verkkoja käsittelevässä tekstissä. Ideana on yhdistää kaksi lukua kaarella, jos niiden tulo on neliö­luku. Tästä saadaan verkko, jonka kautta tehtävää on helpompi hahmottaa. Pienen työn jälkeen saadaan aikaan seuraava verkko:

Huomaa, että ensimmäisessä verkon ”osassa” (puhutaan verkon komponenteista) on neliö­luvut, toisessa luvut muotoa ”kaksi kertaa neliö­luku”, seuraavassa luvut muotoa ”kolme kertaa neliö­luku” ja niin edelleen.

Nyt tehtävä on aivan helppo! Emme saa valita kahta lukua, joita vastaavat solmut on yhdistetty toisiinsa kaarella. Tämä tarkoittaa, että kustakin komponentista voidaan valita enintään yksi solmu. Muuten voimme valita lukuja miten haluamme.

Komponentteja on $12$ kappaletta, joten vastaus tehtävään on $12$. (Yksi tapa valita luvut on ottaa joka komponentista komponentin pienin luku, jolloin saadaan luvut $1, 2, 3, 5, 7, 10, 11, 13, 14, 15, 17$ ja $19$.)

Tutkitaan tilannetta verkkona ja piirretään kahden solmun välille punainen kaari, jos kyseiset henkilöt tuntevat toisensa ja sininen kaari, jos he eivät tunne toisiaan. Haluamme osoittaa, että verkosta löytyy punainen tai sininen kolmio.

Tutkitaan solmusta $1$ lähteviä kaaria.

Koska värejä on kaksi ja kaaria on viisi, on kaarien joukossa (laatikko­periaatteen nojalla) vähintään kolme saman­väristä kaarta. Symmetrian vuoksi voidaan olettaa, että nämä kaaret ovat punaisia. Tutkitaan näitä kaaria vastaavia solmuja (kuvan 13.3 esimerkissä solmuja $2, 3$ ja $6$). Jos solmuista jotkin kaksi on yhdistetty punaisella kaarella toisiinsa, muodostavat nämä kaksi solmua punaisen kolmion yhdessä solmun $1$ kanssa. Muussa tapauksessa solmut muodostavat keskenään sinisen kolmion. Olemme valmiit.

Tehtävään esitetään kaksi erilaista ratkaisua.

Ratkaisu 1 (suora päättely). Tutkitaan tilannetta verkkona, jossa on sinisiä ja punaisia kaaria. Jos siniset kaaret toteuttavat tehtävän­annon väitteen, olemme valmiit. Tutkitaan tapausta, jossa näin ei ole.

Mitä tämä tarkoittaa? Tämä tarkoittaa, että solmut voidaan jakaa vähintään kahteen erilliseen osaan niin, ettei niiden välillä ole sinisiä kaaria. Esimerkiksi yllä olevassa kuvassa solmut $1, 3, 4, 5$ muodostavat yhden osan ja solmu $2$ omansa. Alla on vielä kuva toisenlaisesta tilanteesta.

Tämä tarkoittaa, että punaisia kaaria on jossain mielessä paljon. Todistus on aika helppo saada maaliin. Otetaan jotkin kaksi solmua $A$ ja $B$. Osoitetaan, että niistä pääsee punaisia kaaria pitkin toisiinsa. Tutkitaan kahta tapausta.

Tapaus 1: $A$:sta ja $B$:stä ei pääse sinisiä kaaria pitkin toisiinsa. Tällöin erityisesti solmujen $A$ ja $B$ välinen kaari on punainen, ja olemme valmiit.

Tapaus 2: $A$:sta ja $B$:stä pääsee sinisiä kaaria pitkin toisiinsa. Tässä tapauksessa $A$ ja $B$ kuuluvat samaan verkon komponenttiin. Olkoon $C$ jonkin muun komponentin solmu. (Esimerkiksi jos kuvan 13.5 tilanteessa $A$ on solmu $1$ ja $B$ on solmu $4$, voidaan valita $C$ olemaan vaikkapa solmu $8$.) Koska $A$ ja $C$ ovat eri komponenteissa, niiden välillä on punainen kaari. Vastaavasti solmujen $B$ ja $C$ välillä on punainen kaari. Täten $A$:sta pääsee $B$:hen solmun $C$ kautta, ja olemme valmiit.

Ratkaisu 2 (induktiivinen päättely). Väite on selvä yhden, kahden ja kolmen kaupungin tapauksissa.

Oletetaan, että väite pätee $n$:n kaupungin tapauksessa. Tutkitaan tilannetta, jossa kaupunkeja on $n+1$. Numeroidaan kaupungit $1, 2, \ldots , n+1$.

Unohdetaan kaupunki $n+1$ hetkeksi. Tiedämme, että väite pätee kaupungeille $1, 2, \ldots , n$. Tutkitaan tapausta, jossa mistä tahansa näistä kaupungeista voi matkustaa toiseen kaupunkiin käyttämällä vain sinisiä yhteyksiä.

Nyt jos $n+1$ on yhdistetty sinisellä kaarella vähintään yhteen solmuista $1, 2, \ldots , n$, olemme valmiit: tällöin sinisillä yhteyksillä pääsee mihin tahansa solmuun.

Muussa tapauksessa solmu $n+1$ on yhdistetty kaikkiin muihin solmuihin punaisella kaarella. Tällöin matkustaminen onnistuu punaisten juna­yhteyksien avulla.

Eli induktiivisesti väite pätee aina yhtä suuremmilla kaupungeilla, joten väite pätee yleisesti.

13.4 Tehtäviä

Alla olevissa tehtävissä oletetaan, että ystävyys on molemminpuoleista (eli jos $A$ on henkilön $B$ ystävä, niin myös henkilö $B$ on henkilön $A$ ystävä). Lisäksi oletetaan, että henkilö ei ole ystävä itsensä kanssa.

Tehtävä 1. Kuuden henkilön ihmis­joukossa jotkut henkilöt ovat ystäviä keskenään. Onko mahdollista, että jokaisella henkilöllä on tasan neljä ystävää?

Tehtävä 2. Anna esimerkki viiden henkilön ihmis­joukosta ja niiden välisistä ystävyys­suhteista niin, että seuraavat ehdot toteutuvat:

• Jos valitaan mitkä tahansa kolme henkilöä, he eivät kaikki ole ystävyksiä keskenään
• Jos valitaan mitkä tahansa kolme henkilöä, heistä jotkin ovat ystäviä keskenään

Tehtävä 3. Viiden henkilön ihmis­joukossa jotkut henkilöt ovat ystäviä keskenään. Onko mahdollista, että jokaisella henkilöllä on pariton määrä ystäviä?

Tehtävä 4. Kuuden solmun verkosta tiedetään, että se on yhtenäinen, eli että mistä tahansa solmusta pääsee mihin tahansa toiseen solmuun kaaria pitkin. Kuinka monta kaarta verkossa voi vähimmillään olla?

Tehtävä 5. Kuuden solmun verkosta tiedetään, että se ei ole yhtenäinen. Kuinka monta kaarta verkossa voi enimmillään olla?

Tehtävä 6. Kuuden henkilön ihmis­joukossa jotkut henkilöt ovat ystäviä keskenään. Tiedetään, että jos valitaan mitkä tahansa kolme henkilöä, heistä jotkin kaksi eivät ole ystäviä keskenään. Kuinka monta ystävyys­suhdetta ihmisten vällilä voi enimmillään olla?

Tehtävä 7. Seuraavat kaksi verkkoa voivat nopealla vilkaisulla näyttää erilaisilta, mutta todellisuudessa ne ovat sama verkko. Verkot on vain piirretty ja solmut nimetty eri tavoilla. Solmu $1$ vastaa solmua $B$, solmu $2$ solmua $C$, solmu $3$ solmua $D$ ja solmu $4$ solmua $A$. Kaksi solmua ensimmäisessä verkossa ovat yhteydessä toisiinsa täsmälleen silloin, kun niitä vastaavat solmut toisessa verkossa on yhteydessä toisiinsa.

Kuinka monta neljän solmun verkkoa on olemassa, jotka ovat ”oikeasti erilaisia”, eli niitä ei ole saatu vain nimeämällä solmuja ja piirtämällä verkko eri tavalla? Esimerkiksi kolmella solmulla on olemassa neljä erilaista verkkoa: