Múltérintő

Fotó: Profimedia

Ezzel a kérdéssel fordultak 1735-ben a poroszországi Königsberg (ma Kalinyingrád, Oroszország) előkelőségei a szentpétervári egyetem matematikaprofesszorához, Leonhard Eulerhez.

Válaszához Euler egyszerűsítette a város topográfiai ábrázolását: a város szigeteit pontokkal, a hidakat vonalakkal jelölte – megrajzolta a világ első gráfját. Így bizonyította be, hogy csak akkor volna lehetséges a Pregel folyó hídjait egy útvonalon bejárni és a kezdőállomásra visszaérkezni, ha a kijelölt pontok mindegyikének páros volna a fokszáma – csakhogy az egyik pontnak öt, a másik háromnak pedig három volt a fokszáma.

Haladjon végig egy vonallal, a toll felemelése nélkül az alábbi gráfokon! Egy csúcsponton többször is átmehet, de az éleket csak egyszer érintheti. Melyik gráf esetében sikerül visszajutni a kiindulópontba?

Mi hát a gráf? Olyan ábra, amelyben a véges számú pontok közül egyeseket vonalak, más néven élek kötnek össze, méghozzá úgy, hogy minden élre legalább egy, legfeljebb két pont illeszkedik. Fokszámnak pedig az egy pontba összefutó élek számát nevezzük. A hálózatkutatók szerint voltaképpen a Facebook is gráfok konglomerátuma, ha a résztvevőket csúcsoknak, a köztük lévő kapcsolatokat pedig éleknek tekintjük. Klikkesedésre utal, ha a hálózaton belül olyan kisebb csoportokat találunk, amelyek tagjaira igaz, hogy minden csomópont minden más csoportbeli csomóponttal összeköttetésben áll. „Valamely csomópont fontosságát mutatja például, hogy hány olyan útvonal halad át rajta, amely legrövidebbként köt össze két másik csomópontot – mutat rá Péli Gábor szervezetszociológus, a hollandiai Utrecht város egyetemének tanára.

Csak a jobb oldali ábrán lehet visszajutni a kiindulópontba.