Известният американски математик от Университета в Чикаго Ласло Бабай (László Babai) миналата седмица прочете поредица от лекции, посветени на решаването на така наречения проблем на "изоморфизма на графите", съобщава сайтът на MIT Technology Review.
Очаква се математикът в близко бъдеще да публикува заключенията си в научно списание.
Проблемът за "изоморфизма на графите" днес е един от крайъгълните камъни на теоретичната информатика.
Теорията на графите е дял от на дискретната математика (разглеждаща крайни обекти), която изучава свойствата на графите. Общо взето, един граф е съвкупност от върхове (възли), свързани с ребра.
Една от прочутите задачи за графи е формулираната от математика Леонард Ойлер за седемте моста на Кьонигсберг, които трябва да се преминат, без да се мине два пъти по някой от тях, което в случая е невъзможно.
Най-вляво - схема на Кьонигсбергските мостове, след това схема на графа на мостовете.
Теорията графите намира приложение, например, в геоинформационните системи (ГИС). В проектирането съоръжения, квартали, сгради, станции и т. н. разглеждат се както връховете, а съединяващите ги пътища, инженерни мрежи, линии на електропреносната, пътната и водопроводната мрежа и т. н. - като ребра. Различните изчисления, които се прилагат на такъв граф, позволяват, например, да се намери най-краткия обходен път или най-близкия пункт, да се планира оптималния маршрут.
Теорията на графите има голямо количество нерешени проблеми и недоказани хипотези.
Проблемът за "изоморфизма на графите" се състои в това, да се намери начин да се установи дали два графа са идентични, с една и съща структура или, как казват математиците, са "изоморфни. Традиционно тази задача се счита за доста трудна, тъй като се отнася към задачите, в които рязко се увеличава броят на операциите, необходими за решението, с увеличаване на броя на върховете и връзките.
 |
 |
С увеличаване на броя на възлите изоморфността на графите става все по-малко очевидна.
Това свойство, се използва в най-популярните днес методи за криптиране на данните с използване на фактори, когато, вместо едно или друго число или група числа при предаване на информацията се предават тези фактори. Тъй като "изоморфизмът на графите" е трудна задача, да се разшифрова предаваната информация е също практически невъзможно.
Но, според Ласло Бабай, задачата за установяването на "изоморфизма на графите", не е много трудна. Съгласно предложения алгоритъм, може на много по-малки стъпки - в сравнение с използваните понастоящем методи - установи, че два графа са всъщност, едни и същи. За съжаление, няма конкретна информация за това как работи алгоритъмът, няма. Но математикът обещава да го разкрие в близко бъдеще. Ако предположение му се потвърди, това не само ще позволи по-бързо да се оперира с огромни масиви данни, натрупани в областта на природните науки, но също така може да доведе до преосмисляне на принципите на криптиране на данните като съществено се опрости процеса декриптиране на данните.
Коментари
Моля, регистрирайте се от TУК!
Ако вече имате регистрация, натиснете ТУК!
Няма коментари към тази новина !
Последни коментари