Google Classroom
GeoGebraGeoGebra Classroom

Gráfok izomorfizmusa

http://index.hu/tudomany/2015/11/12/grafok_arthur_kiraly_udvaraban/ 2015.11.12. "Szenzációs magyar felfedezés forgatja fel a matematikát" olvashattuk a híradásokban Mi is ennek a felfedezésnek a lényege? Egy magyar kutató, a Chicagói Egyetemen tanító Babai László egy régi problémára, a gráfizomorfizmus-problémára (leegyszerűsítve: két gráf azonos-e) olyan új algoritmust alkotott, amely az eddigi megoldásoknál kevesebb lépéssel jut el a megoldásig. Most Eugene Luks megoldását használja a tudományos világ, algoritmusában a lépések száma majdnem exponenciálisan nő, Babai László algoritmusában azonban a lépések száma alig nő gyorsabban a polinominális időnél.