Katona Gyula

Hogyan lett "magyar matematika" a kombinatorika?

II. Mennyi Madonna Latabár-száma?

De lehet a világ összes emberét egy-egy ponttal ábrázolni, s kettőt összekötni, ha legalább egyikük arcról ismeri a másikat (3. ábra).

1. ábra

2. ábra

3. ábra

Két ember távolságának azt nevezzük, hogy hány lépésben lehet a gráfban az egyiktől a másikig eljutni. Azaz akik össze vannak kötve, azok távolsága egy. Ha kettő nincs összekötve, de van közös ismerősük, akkor távolságuk kettő s így tovább (4. ábra). Itt már bátran feltehetünk egy kérdést is: mi a legnagyobb távolság az emberek között? A mai világban valószínűleg 2! Ugyanis bizonyára mindenki ismeri Bill Clintont. Na jó, ha nem szokott tévét nézni, akkor ismer valakit, aki szokott. Akkor is legfeljebb 4 lépésben el lehet jutni egyik embertől a másikig (5. ábra).

4. ábra

5. ábra

Egy tréfás változat, amit matematikusok találtak ki maguknak, a következő. A pontok matematikusokat jelentenek, két ilyen pont össze van kötve, ha az illető matematikusoknak van közös tudományos publikációjuk (cikkük). Ezt arra találták ki, hogy megállapítsák az ún. Erdős-számot, ami azt jelenti, hogy ebben a gráfban hány lépés van Erdős Páltól az illetőig.

A következő animáción ennek a gráfnak egy részletét láthatjuk. A legbüszkébbek azok, akiknek az Erdős-számuk 1, azaz van közös cikkük Erdőssel. Íme néhány nevezetes Erdős-út (a zárójelben az Erdős-számok szerepelnek):
Erdős Pál (0) - P. Hell (1) - Xiao Tie Deng (2) - C. H. Papadimitriou (3) - Bill Gates (4)
Erdős Pál (0) - E. Straus (1) - Albert Einstein (2)
Erdős Pál (0) - Csiszár Imre (1) - Katona Gyula (2)

Animáció: Erdős Pál társszerzői hálózata

6. ábra

link