09 декември 2019
Категории
  •  Космос
  •  Физика
  •  Науки за земята
  •  Биология
  •  Медицина
  •  Говорят медиците
  •  Математика
  •  Научни дискусии
  •  Разни
FACEBOOK

Нов алгоритъм обещава да опрости проблема за "изоморфизма на графите"

| ПОСЛЕДНА ПРОМЯНА 17 ноември 2015 в 10:0673560
Два изоморфни графа. Снимка: wikipedia

Известният американски математик от Университета в Чикаго Ласло Бабай (László Babai) миналата седмица прочете поредица от лекции, посветени на решаването на така наречения проблем на "изоморфизма на графите", съобщава сайтът на MIT Technology Review.

Очаква се математикът в близко бъдеще да публикува заключенията си в научно списание.

Проблемът за "изоморфизма на графите" днес е един от крайъгълните камъни на теоретичната информатика.

Теорията на графите е дял от на дискретната математика (разглеждаща крайни обекти), която изучава свойствата на графите. Общо взето, един граф е съвкупност от върхове (възли), свързани с ребра.

Една от прочутите задачи за графи е формулираната от математика Леонард Ойлер за седемте моста на Кьонигсберг, които трябва да се преминат, без да се мине два пъти по някой от тях, което в случая е невъзможно.

Най-вляво - схема на Кьонигсбергските мостове, след това схема на графа на мостовете.

Теорията графите намира приложение, например, в геоинформационните системи (ГИС). В проектирането съоръжения, квартали, сгради, станции и т. н. разглеждат се както връховете, а съединяващите ги пътища, инженерни мрежи, линии на електропреносната, пътната и водопроводната мрежа и т. н. - като ребра. Различните изчисления, които се прилагат на такъв граф, позволяват, например, да се намери най-краткия обходен път или най-близкия пункт, да се планира оптималния маршрут.

Теорията на графите има голямо количество нерешени проблеми и недоказани хипотези.

Проблемът за "изоморфизма на графите" се състои в това, да се намери начин да се установи дали два графа са идентични, с една и съща структура или, как казват математиците, са "изоморфни. Традиционно тази задача се счита за доста трудна, тъй като се отнася към задачите, в които рязко се увеличава броят на операциите, необходими за решението, с увеличаване на броя на върховете и връзките.

С увеличаване на броя на възлите изоморфността на графите става все по-малко очевидна. 

Това свойство, се използва в най-популярните днес методи за криптиране на данните с използване на фактори, когато, вместо едно или друго число или група числа при предаване на информацията се предават тези фактори. Тъй като "изоморфизмът на графите" е трудна задача, да се разшифрова предаваната информация е също практически невъзможно.

Но, според Ласло Бабай, задачата за установяването на "изоморфизма на графите", не е много трудна. Съгласно предложения алгоритъм, може на много по-малки стъпки - в сравнение с използваните понастоящем методи - установи, че два графа са всъщност, едни и същи. За съжаление, няма конкретна информация за това как работи алгоритъмът, няма. Но математикът обещава да го разкрие в близко бъдеще. Ако предположение му се потвърди, това не само ще позволи по-бързо да се оперира с огромни масиви данни, натрупани в областта на природните науки, но също така може да доведе до преосмисляне на принципите на криптиране на данните като съществено се опрости процеса декриптиране на данните.


Препоръчани материали

Няма коментари към тази новина !

 
Още от : Новини
5 изненадващи факта за Коледа
5 изненадващи факта за Коледа
24 декември 2019 в 00:135428
Всички текстове и изображения публикувани в OffNews.bg са собственост на "Офф Медия" АД и са под закрила на "Закона за авторското право и сродните им права". Използването и публикуването на част или цялото съдържание на сайта без разрешение на "Офф Медия" АД е забранено.