Geef mij een willekeurige landkaart, en ik kleur de landen op de kaart met rood, geel, blauw en groen zo dat twee landen die aan elkaar grenzen nooit dezelfde kleur krijgen. De zogenaamde vierkleurenstelling, een wiskundige stelling die zegt dat je alle mogelijke landkaarten met maximaal 4 kleuren kan inkleuren, werd ruim 50 jaar geleden bewezen. De kleuring van netwerken in plaats van landkaarten is echter weer net anders en, gezien het scala aan toepassingen in bijvoorbeeld communicatienetwerken en roosterproblemen, ontzettend actueel. Twee Spaanse onderzoekers ontwikkelden onlangs een nieuw algoritme voor het kleuren van netwerken, waarin ze inspiratie ontleenden aan het roepgedrag van Japanse boomkikkers.

Japanse boomkikker-mannetjes roepen om vrouwtjes te lokken. Wanneer een vrouwtje echter teveel mannetjes tegelijk hoort roepen, is ze niet meer in staat nauwkeurig de locatie van een mannetje te bepalen. De boomkikker-mannetjes die dicht bij elkaar zitten hebben er dus baat bij om niet tegelijkertijd al te veel lawaai te maken, maar juist na elkaar te roepen.

Bekijk deze situatie schematisch, en we zien een netwerk (of graaf) van mannelijke boomkikkers op verschillende afstanden van elkaar. Boomkikkers die erg dicht bij elkaar zitten roepen niet tegelijkertijd, zoals ook landen op de landkaart die aan elkaar grenzen niet dezelfde kleur hebben. Het verschil is echter dat iemand die een landkaart inkleurt alvast de hele landkaart kan overzien voor hij begint. De boomkikkers hebben dit overzicht niet, en zien alleen hun naaste buren.

Juist dit lokale karakter maakt het voorbeeld van de boomkikkers interessant. Immers, zonder overzicht van het geheel is het een stuk moeilijker om een goede kleuring te bedenken. Vergelijk dit met het inkleuren van een kaart van Europa. Als je zomaar begint met kleuren heb je misschien wel de volgende verdeling: Duitsland – rood, Frankrijk – blauw, Italië – geel en Oostenrijk – groen. Er is dan geen geschikte kleur mee over voor Zwitserland, dat aan alle vier de landen grenst. Dat betekent dat de hele inkleuring van de kaart herzien moet worden – en dat maakt het algoritme inefficiënt.

Wetenschappers deden al eerder onderzoek naar het patroon achter het gedrag van de boomkikkers. Voor twee kikkers vonden ze zo’n patroon: beide kikkers verschuiven om te beginnen de tijdsduur tussen twee roepen met een vaste factor op. Daarnaast worden beide kikkers ook nog eens beïnvloed door het tijdsverschil met de roep van de andere kikker. Zo komen ze uiteindelijk in een stabiele situatie waarin de tijd tussen de roep van kikker A en die van kikker B zo lang mogelijk is.

Dit eerdere model werkte goed voor twee kikkers, maar nog niet voor meer. De Spanjaarden vonden een manier om het toe te passen op een graaf (of netwerk) van kikkers. Om het gehele netwerk tot een optimum te laten komen heeft iedere individuele kikker daarbij slechts informatie nodig over het roepen van zijn directe buurmannen.

Het Spaanse algoritme bootst niet alleen het roepen van de kikkers goed na, maar is ook goed toepasbaar op allerlei communicatienetwerken. Eén toepassing van zo’n graafkleuring is bijvoorbeeld de toewijzing van radiofrequenties in de ether. Een radiostation dat alleen in Limburg te ontvangen is, mag best dezelfde frequenties gebruiken als een radiostation in Groningen. Maar als zenders in dezelfde regio actief zijn moeten in ze natuurlijk verschillende frequenties toegewezen krijgen. Want zoals een boomkikker-vrouwtje in de war raakt als ze meer dan één kikker door elkaar hoort, zo horen wij het liefst één radiozender tegelijk.