Графи и мрежи: математиката на пътищата, интернет и социалните връзки
Графи и мрежи:
математиката на пътищата, интернет и социалните връзки
Когато през 1735 г. гражданите на Кьонигсберг изпращат до Леонхард Ойлер задача за своите седем моста, те не подозират, че така ще бъде положена основата на цяла нова област в математиката. Днес същата тази теория обяснява как Google подрежда резултати, как GPS намира най-краткия път, защо сме на шест стъпки от всеки друг човек на планетата и как се разпространяват вирусите.
Живеем в мрежи, без дори да го забелязваме. Всяка сутрин се придвижваме през транспортни мрежи, пишем съобщения в социални мрежи, търсим информация, която достига до нас чрез глобална мрежа от сървъри и кабели. Вирусите се движат в мрежа от контакти между хора. Невроните в мозъка ни формират мрежа. Молекулите във всяка клетка са свързани в мрежа от химични реакции.
Когато кажем „мрежа", обикновено имаме предвид нещо съвсем конкретно — Facebook, интернет, пътната мрежа. Но математикът вижда зад всички тези различни неща една и съща структура. Тази структура се нарича граф. И макар думата да звучи абстрактно, зад нея стои изненадващо проста идея: точки и линии, които ги свързват.
Колкото и елементарна да изглежда тази идея, тя се оказа достатъчно мощна, за да обясни работата на Google, навигацията в Google Maps, разпространението на COVID-19 и дори факта, че сте „на шест стъпки" от всеки друг човек на планетата. Всичко това започва в един прусашки град преди близо 290 години.
Кьонигсберг: раждането на една наука
През XVIII век Кьонигсберг (днес Калининград) е разположен около двата ръкава на река Прегел. Между бреговете и двата острова в реката били изградени седем моста. В неделните следобеди, когато времето е хубаво, гражданите обичали да се разхождат из града. Един от най-обсъжданите въпроси по време на тези разходки бил следният: възможно ли е да се мине през всички седем моста, без нито един да бъде повторен?
Схема на Кьонигсберг: седемте моста (номерирани 1–7) свързват четирите части суша — два острова (A, B) и двата бряга (C, D). Остров A е свързан с 5 моста; всеки от останалите три (B, C, D) — с 3 моста.
Задачата изглежда безобидна, почти детска. Но никой не успявал да намери такъв път. Дали защото е невъзможен, или защото просто не е правен достатъчно опит? През 1735 г. местни мислители се обръщат към най-известния математик на епохата — швейцареца Леонхард Ойлер.
Първоначалната реакция на Ойлер е пренебрежителна — той смята, че задачата има „малко общо с математиката". Но после се заема с нея, а през 1736 г. публикува в Санкт Петербург статията Solutio problematis ad geometriam situs pertinentis — „Решение на задача от геометрията на положението". Без да знае, в този момент той слага основите на цяла нова област в математиката.
Абстракцията на Ойлер
Ключовото прозрение на Ойлер е, че точната форма на града и дори дължината на мостовете нямат значение. Важно е само как са свързани частите суша помежду си. Всяка земна маса може да бъде сведена до точка, а всеки мост — до линия между две точки. Самата география изчезва, остава само структурата на свързаност.
Графът на Кьонигсберг: четири върха (A, B, C, D) и седем ребра — A–C (2 ребра), A–D (2 ребра), A–B, C–B и D–B. Всички върхове са с нечетна степен, което прави Ойлеров път невъзможен.
Така от една географска задача се ражда граф — структура от четири върха и седем ребра. Тук Ойлер доказва нещо изящно: ако искаме да преминем през всички ребра точно по веднъж (днес наричаме такъв маршрут Ойлеров път), почти всеки връх трябва да има четна степен. Аргументът е прост: всеки път, когато влизаме във връх, трябва и да излезем от него. Значи ребрата се спарват — едно за влизане, едно за излизане. Изключение правят само върховете, от които започваме и в които завършваме пътя.
В графа на Кьонигсберг обаче и четирите върха имат нечетна степен (три от тях със степен 3, централният остров със степен 5). Това е с два повече от максимално допустимото. Следователно такъв път не съществува — не защото гражданите на Кьонигсберг не са се старали достатъчно, а защото самата структура на моста го прави невъзможен.
Ойлеров срещу Хамилтонов път
Около век след Ойлер друг въпрос започва да занимава математиците. Ако Ойлеровият път минава през всяко ребро точно веднъж, какво бихме казали за път, който минава през всеки връх точно веднъж? Това звучи като сродна задача — всъщност се оказва много по-трудна.
Така наречените Хамилтонови пътища са кръстени на ирландския математик Уилям Роуън Хамилтон, който през 1850-те проектирал игра, наречена Icosian Game. Тя представлявала пъзел върху додекаедър, при който играчът трябвало да премине през всичките 20 върха точно по веднъж, следвайки ребрата. Идеята била игрова, но математическата задача зад нея се оказала изключително дълбока.
И тук е ключовият контраст: докато за Ойлеровите пътища имаме проста и елегантна характеристика (най-много два върха с нечетна степен), за Хамилтоновите пътища не познаваме такъв общ критерий.
• Хамилтонов път минава през всеки връх точно веднъж. Няма проста и ефективна характеризация. Проверката за съществуване на такъв път е сред най-трудните изчислителни задачи.
Учудващата трудност на Хамилтоновия път води до една от най-известните задачи в математиката и информатиката — задачата на търговския пътник.
Задачата на търговския пътник
Представете си следната ситуация: търговски пътник трябва да посети \(n\) града, разположени на картата. Между всеки две градове има известно разстояние (или цена за пътуване). Търговецът трябва да започне от собствения си град, да посети всеки останал град точно веднъж и да се върне у дома. Кой е най-евтиният възможен маршрут?
В графов език задачата на търговския пътник търси Хамилтонов цикъл с минимално общо тегло. Тоест тя е пряко продължение на задачата за Хамилтоновия път — само че вместо просто да се питаме дали такъв път съществува, вече търсим най-добрия от всички възможни.
Формулировката изглежда почти детска. В действителност това е една от най-известните и най-изследвани задачи в комбинаторната оптимизация и теоретичната информатика. Първите математически формулировки в този дух се появяват през 1930-те, включително известната „48-щатна задача" на Хаслер Уитни. През 1954 г. Джордж Дантциг, Делбър Фулкерсон и Селмър Джонсън от корпорацията RAND успяват да решат 48-градската задача чрез методите на линейното програмиране — постижение, което се счита за важен крайъгълен камък в комбинаторната оптимизация.
Защо е толкова трудна? Основната причина е количествена. Ако искаме да проверим всички възможни маршрути за \(n\) града, общият брой е \((n-1)!/2\) — расте фантастично бързо:
За голяма изненада на всички, през 1972 г. Ричард Карп доказва, че вариантът на задачата с отговор „да/не“ (съществува ли маршрут с дължина под дадена граница?) е NP-пълна, а оптимизационната версия (намери най-късия маршрут) е съответно NP-трудна. Това означава, че задачата принадлежи към семейство задачи, за които не се знае дали имат ефективен алгоритъм, и широко се смята, че нямат.
Цялата теория на изчислителната сложност, в която се класифицират задачите по трудност, стъпва върху абстрактните машини на Тюринг — теоретичния модел на изчисление, който Алън Тюринг въвежда през 1936 г. А самата трудност на задачата на търговския пътник е свързана с една от най-известните отворени задачи в математиката — прочутия проблем P срещу NP, за чието решение Clay Mathematics Institute предлага награда от 1 милион долара.
На практика днес се използват приближителни алгоритми, които не гарантират точен оптимум, но дават много добри решения. Класическият алгоритъм на най-близкия съсед просто отива към най-близкия непосетен град — бързо, но често далеч от оптималното. По-изтънчените методи (2-opt, симулирано охлаждане, генетични алгоритми) дават отлични решения за практически задачи с хиляди градове.
Езикът на мрежите: какво е граф?
Ойлеровото прозрение по същество ни казва: когато говорим за свързаност, геометрията не е важна. Важни са само два компонента:
- Върхове (nodes, vertices) — точки, които представляват обекти: хора, градове, уеб-страници, неврони, компютри.
- Ребра (edges) — линии, които свързват двойки върхове и представляват връзки: приятелства, пътища, хипервръзки, синапси, кабели.
Това е всичко. Всичко останало в теорията на графите е надстройка върху тази минимална структура. Самата дума „граф" в този смисъл е въведена в математиката от английския математик Джеймс Джоузеф Силвестър през 1878 г. Преди това Ойлер е говорил за „геометрия на положението" (geometria situs) — геометрия, в която не са важни дължини и ъгли, а само взаимните отношения. Това по-късно ще стане известно като топология. Така Ойлер не само слага началото на теорията на графите, но и поставя семена на още една фундаментална област на математиката.
• Път — последователност от свързани ребра, водеща от един връх до друг.
• Цикъл — път, който се връща обратно в началото.
• Тегло — число, присвоено на ребро (разстояние, време, цена).
• Свързан граф — такъв, в който от всеки връх може да се стигне до всеки друг.
• Насочен граф (digraph) — ребрата имат посока.
Забележително е как тези няколко понятия са достатъчни, за да се опишат изумителен набор от явления. Един и същ математически обект — графът — може да представлява пътна карта, роднинските връзки в едно семейство, структурата на една молекула, последователността на гени в ДНК, или топологията на интернет. Математиката не вижда разликата между тях.
Както обяснява математичката Мария Чудновска от Принстън в подкаста The Joy of Why на Quanta Magazine: теорията на графите е клон на математиката, който изучава двоични отношения — системи от обекти, в които някои двойки са свързани, а други не. Хора, от които някои са приятели, а други не. Или градове, някои от които са свързани с директен път, а други не. Щом има такова отношение, имаме граф.
Ключови моменти в развитието на теорията
Пътят от Ойлер до съвременния интернет е изпълнен с открития, всяко от които разширява приложимостта на теорията в нова посока. Ето някои от най-важните моменти в нейната история:
- Ойлер решава задачата за седемте моста на Кьонигсберг и публикува Solutio problematis ad geometriam situs pertinentis — смята се за първата статия в теорията на графите.
- Немският физик Густав Кирхоф, изучавайки електрически вериги, доказва матрично-дървесната теорема — изящен резултат, който свързва линейна алгебра и графи и позволява броене на дървета в мрежа.
- Франсис Гутри задава въпроса: стигат ли четири цвята, за да оцветим всяка карта така, че съседни области да нямат един и същи цвят? Появява се задачата за четирите цвята.
- Уилям Роуън Хамилтон проектира Icosian Game, давайки началото на изучаването на Хамилтонови пътища и цикли.
- Едсгер Дейкстра публикува алгоритъм за най-къс път в мрежа с положителни тегла. Днес той е в основата на GPS навигацията.
- Социалният психолог Стенли Милграм провежда експеримент за „малкия свят" — ражда се идеята за „шестте степени на разделение".
- Ричард Карп доказва, че решаващата версия на задачата на търговския пътник е NP-пълна, слагайки я сред най-трудните изчислителни задачи.
- Кенет Апел и Волфганг Хакен доказват теоремата за четирите цвята — първото голямо математическо твърдение, доказано с помощта на компютър.
- Данкан Уотс и Стивън Строгац публикуват модела на „малките светове" в Nature; Лари Пейдж и Сергей Брин разработват алгоритъма PageRank за бъдещата търсачка Google.
- Барабаши и Алберт откриват модела на „безмащабните мрежи" (scale-free networks) и идеята за предпочитателно прилепване.
Шестте степени на разделение: малкият свят
През 1967 г. социалният психолог Стенли Милграм провежда неочакван експеримент. В серия от експерименти той избира няколкостотин произволни хора в Омаха и Уичита и ги моли да предадат едно писмо до определен борсов брокер в Бостън — но с условие, че писмото трябва да мине от ръка на ръка само между хора, които лично се познават. Ако получателят не е ваш познат, трябва да предадете писмото на познат, който може да го доближи до целта.
Резултатът е изненадващ. От писмата, които стигат до получателя, средната дължина на веригата е около шест стъпки. Оттук идва известната фраза „шест степени на разделение". Важно е обаче да се уточни: това не бива да се възприема като строго доказан универсален закон за всеки двама души на планетата. Идеята идва от small-world изследванията и от експерименти върху вериги от познанства — тя е емпирична оценка, не математическа теорема.
Това звучи толкова невероятно, че дълго време се смята за фолклор. През 1990-те обаче двама математици — Данкан Уотс и Стивън Строгац — решават да разберат математически защо светът е толкова малък. Те публикуват през 1998 г. в списание Nature статия, която днес е сред най-цитираните в областта на мрежовата наука — с десетки хиляди цитирания, повече дори от статията на Уотсън и Крик за структурата на ДНК.
Идеята им е изящна. Започват с пръстен от хора, в който всеки познава само най-близките си съседи. Това е „голям свят": за да стигне съобщение от един край до другия, трябват много стъпки. После, малко по малко, те започват да пренасочват случайни ребра — сякаш някой се премества в друг град и запазва едно приятелство от старото място.
Ето изненадата: не трябват много такива дълги връзки, за да стане светът „малък". Дори малък процент случайно пренасочени ребра драматично намаляват средната дистанция, без съществено да променят локалната клъстеризация. Светът става едновременно „локално подреден" (приятелите ви са и помежду си приятели) и „глобално свързан" (всеки е близо до всеки).
Уотс и Строгац проверяват модела си на три напълно различни мрежи: мозъкът на червея C. elegans с неговите 282 неврона, електропреносната мрежа на западните САЩ, и мрежата на над 200 000 холивудски актьори, свързани чрез филми, в които са играли заедно. И трите се оказват „малки светове". Средното „число на Кевин Бейкън" — броят стъпки от случаен актьор до Кевин Бейкън — е приблизително 3.
По-късно подобен център става Пол Ердьош, един от най-плодовитите математици на XX век. „Числото на Ердьош" показва колко далеч е един математик от него в съавторството на статии. Забавно следствие: Алберт Айнщайн има число на Ердьош 2. Кевин Бейкън има както Ердьошово, така и Бейконово число — така се ражда идеята за Бейкън-Ердьошово число.
Безмащабните мрежи: богатите стават по-богати
Докато Уотс и Строгац изучавали „малките светове", физикът Алберт-Ласло Барабаши и неговата докторантка Река Алберт открили друго забележително свойство на много реални мрежи. През 1999 г. в Science те публикуват статията „Emergence of Scaling in Random Networks" — една от най-цитираните работи в мрежовата наука досега.
Тяхното откритие било, че в много реални мрежи разпределението на степените не е равномерно, а следва степенен закон (power law): броят на върховете със степен \(k\) намалява приблизително като \(P(k) \sim k^{-\gamma}\), с експонента обикновено между 2 и 3. С други думи, има малък брой „големи" върхове с много връзки (т.нар. хъбове) и много малки върхове с малко връзки.
Защо? Барабаши и Алберт предложили прост механизъм, който те нарекли предпочитателно прилепване (preferential attachment): когато нов връх се прибавя към мрежата, той се свързва с вероятност, пропорционална на броя вече съществуващи връзки на всеки възможен съсед. С други думи, богатите стават по-богати.
Когато се регистрирате в нова социална мрежа, по-вероятно е да последвате известни хора, отколкото напълно непознати профили. Когато се създава нов уебсайт, по-вероятно е той да сочи към популярни страници. Когато е нужно, нови въздушни линии се откриват първо между големи летища. Резултатът е мрежа, в която Google, Facebook, The New York Times или летището в Атланта се превръщат в изключително силно свързани възли.
Тъкмо наличието на такива хъбове прави безмащабните мрежи едновременно забележително устойчиви на случайни повреди — премахването на произволен връх почти сигурно засяга един от многото малки — и същевременно много уязвими при целенасочено премахване на най-свързаните възли. Именно тази асиметрия обяснява защо интернет продължава да работи при случайни откази на рутери, но защо атака срещу няколко ключови хъба би могла да го раздели на парчета.
Най-краткият път: алгоритъмът на Дейкстра и GPS-ът ви
Всеки път, когато Google Maps ви казва „завийте надясно след 200 метра", някъде в сървър работи алгоритъм, чиито корени стигат до една сутрин в Амстердам през 1956 г. Тогава 26-годишният холандски компютърен учен Едсгер Дейкстра седи на терасата на кафене с младата си годеница Рия, която също е математик и програмистка, изтощени от пазаруване. Докато отпиват кафе, на него му хрумва въпросът: как най-ефикасно да се намери най-краткият път между две точки в мрежа?
Както самият Дейкстра по-късно разказва в интервю с Филип Франа (август 2001 г., публикувано в Communications of the ACM през 2010 г.), алгоритъмът е „двадесетминутно изобретение". Той не го е записал с молив и хартия — и по собствените му думи именно затова е излязъл толкова елегантен:
Проектирах алгоритъма без молив и хартия. По-късно разбрах, че едно от предимствата на този подход е, че си почти принуден да избягваш всички възможни усложнения. — Едсгер Дейкстра (превод по смисъл на интервюто от 2001 г.)
Публикува го чак през 1959 г., три години след онази сутрин на терасата.
Самата причина Дейкстра да се занимае с тази задача е интересна. По това време Математическият център в Амстердам е в процес на завършване на новия си компютър ARMAC. За „празничното откриване" е необходима демонстрация, която неспециалисти да разберат — както формулировката, така и отговора. Дейкстра избира задачата за най-краткия път между две нидерландски градове, редуцирайки картата до 64 града (за да се кодират с 6 бита).
Идеята на Дейкстра е едновременно проста и мощна. Представете си, че стоите в началния връх и искате да намерите най-краткото разстояние до всеки друг връх в мрежа, в която ребрата имат тегла (разстояние, време, цена). Алгоритъмът работи стъпка по стъпка:
- Приписваме разстояние 0 на началния връх и \(\infty\) на всички останали.
- Избираме върха с най-малко текущо разстояние, който все още не е „посетен".
- Обновяваме разстоянията до всичките му съседи, ако сумата на текущото разстояние и теглото на реброто е по-малка от известното разстояние.
- Маркираме върха като посетен и повтаряме.
Красивото е, че когато алгоритъмът свърши, знаем не само най-краткото разстояние до всеки друг връх, но и самия маршрут. Той е в сърцевината на Google Maps, Waze, Uber и почти всяка GPS система. Управлява също интернет протоколи като OSPF (Open Shortest Path First) и IS-IS, с които рутерите избират оптимални пътища за пакетите данни.
Разбира се, в реалните приложения чистият алгоритъм на Дейкстра е твърде бавен за карта на цял континент. Съвременните навигационни системи използват различни усъвършенствания: двупосочен Дейкстра (търси едновременно от началото и от края), алгоритъм A* (използва евристика за посоката), йерархични алгоритми (групират пътуването по магистралите преди локалния обход) и contraction hierarchies. Но в сърцевината им остава същата идея от онази сутрин в Амстердам.
В същото интервю от 2001 г. Дейкстра отбелязва шеговито, че ако днес пътувате някъде с кола, която има GPS, и тя ви показва най-краткия маршрут — то всъщност тази сутрин сте използвали неговия алгоритъм.
PageRank: как Google чете мрежата на света
През 1998 г. двама докторанти в Станфорд — Лари Пейдж и Сергей Брин — стартират компания, наречена Google. По това време съществуват десетки търсачки — AltaVista, Yahoo, Lycos — и никой не чака нов конкурент. Пейдж и Брин обаче имат едно предимство: математическа идея, която ще се окаже решаваща.
Представете си интернет като огромен насочен граф, в който върховете са уеб-страници, а ребрата са хипервръзки (насочени — от страница А към страница Б). Въпросът е: как да подредим страниците по важност? Очевидното решение — да броим колко връзки сочат към всяка страница — е твърде лесно за манипулиране. Всеки може да създаде хиляди фалшиви страници, които сочат към своята.
Идеята на Пейдж и Брин е по-тънка: важността на една страница трябва да зависи от важността на страниците, които я сочат. Връзка от известна страница трябва да тежи повече от връзка от неизвестна. Но това звучи кръгово: как да знаем кои са важните страници, преди да знаем кои са важните страници, които ги сочат?
Математиката дава елегантен отговор. Ако означим с \(x_i\) важността на страница \(i\), условието е:
\[x_i = \sum_{j \to i} \frac{x_j}{d_j},\]където \(d_j\) е броят изходящи връзки от страница \(j\), а сумата е по всички страници, които сочат към \(i\). Това може да се запише матрично, с вектор \(\mathbf{x}\) и матрица на преходите \(M\), като:
\[M\mathbf{x} = \mathbf{x}.\]Тоест векторът на PageRank е собствен вектор (eigenvector) на матрицата \(M\), съответстващ на собствена стойност 1. Според една теорема от линейната алгебра — теоремата на Перон-Фробениус — такъв вектор съществува и е уникален, стига матрицата да има определени свойства. А за да са те изпълнени, Пейдж и Брин въвеждат още един трик.
На практика този собствен вектор не се намира с магия. Алгоритъмът (известен като степенна итерация) започва с равни оценки за всички страници, след което многократно прилага матрицата — стъпка след стъпка стойностите се преразпределят през мрежата от хипервръзки, докато се стабилизират. За интернет с милиарди страници това е изчислима задача само защото матрицата е изключително разредена: всяка страница има по няколко изходящи връзки, не по милиарди.
Наистина ли Google все още използва PageRank? Официалният отговор е, че това е само един от стотиците сигнали, които търсачката комбинира. Но математическата идея — че важността на един възел в мрежата се определя от важността на съседите му — е в основата на много други съвременни алгоритми: класиране на научни статии, откриване на ключови хора в социални мрежи, оценка на финансов риск, анализ на биологични мрежи. Всичко това е собствен вектор, изчислен в правилна матрица.
Централност: кои са най-важните възли?
PageRank е само един конкретен начин да се измери „важност" на възел в мрежа. Теорията на графите дава цяло семейство от такива мерки, известни като мерки за централност. Всяка от тях отговаря на различен въпрос:
- Централност по степен (degree centrality): кой възел има най-много директни съседи? Най-простата мярка — подходяща за „колко приятели имате във Facebook".
- Централност по близост (closeness centrality): кой възел е средно „най-близо" до всички останали? Важна за скоростта на разпространение — хора с висока близост бързо достигат до всеки друг.
- Централност по свързване (betweenness centrality): през колко най-къси пътища между други възли минава този възел? Това е „мостова" централност. Висока betweenness означава, че възелът е критично важен за свързаността на мрежата — ако го премахнем, мрежата се разделя.
- Собствена централност (eigenvector centrality): важността зависи от важността на съседите. Това е прякото обобщение, от което PageRank се получава като специален случай.
Интуицията е проста. В социална мрежа човек с много приятели може да има висока степен, но човек, който свързва две различни групи — например експерт по шах, който познава едновременно шахматисти и научни журналисти — може да има много по-висока betweenness и да бъде по-важен за разпространението на информация между тези групи.
В забележително изследване на уличните мрежи на 97 града по света, публикувано в Nature Communications през 2018 г. от Алек Къркли, Хуго Барбоза, Марк Бартелеми и Гурав Гошал, е открит изненадващ резултат: разпределението на betweenness в градската улична мрежа е почти инвариантно — независимо дали гледаме Париж, Токио или Ню Йорк, статистическата структура на най-натоварените кръстовища е забележително сходна.
В основата на това поведение стои разделение на мрежата на „дървовидна" сърцевина от критични възли с висока посредническа централност и фини локални контури, които дават алтернативни маршрути.
Тази математика има съвсем практически приложения. Градските планировачи използват мерки за централност, за да идентифицират кръстовища, в които задръстванията са най-вероятни, и да проектират заобиколки. Телекомуникационни компании ги използват, за да идентифицират възли с критично значение за техните мрежи. А социолозите — за да разпознаят „брокерите на информация" в организации и общности.
Графи и епидемиология: мрежи на зараза
Малко след като COVID-19 промени живота на всички ни, изследователи по целия свят се обърнаха към теорията на графите за отговори. Класическите епидемиологични модели, като SIR (Susceptible – Infected – Recovered), предполагат, че населението е хомогенно и всеки има еднаква вероятност да срещне всеки друг. Но това просто не е вярно. Ние живеем в структурирани мрежи от контакти — семейство, колеги, съученици, общност в квартала.
Мрежовите епидемиологични модели изоставят хомогенността. Те представят хората като върхове, а контактите — като ребра. В такъв модел заразата се разпространява по ребрата. И тук възниква въпросът: кои възли са най-критични за разпространението?
Едно от добрите изследвания в това направление е работата на К. Силва, П. Машадо, Р. Лейтау, С. Пинейро и В. Афрейшу от Университета в Авейро (Португалия), публикувана в Mathematical and Computational Applications през 2022 г. Те анализират разпространението на COVID-19 между общините на област Авейро и между възрастовите групи, използвайки мерки за централност.
Резултатите им са поучителни. Община Авейро (столицата на областта) има най-високи стойности по всички мерки за централност — тя е „мостът" между останалите общини. Що се отнася до възрастовите групи, групата 40–49 години е тази с най-висока betweenness и closeness централност. С други думи, хората в тази възраст са „мостът" между по-младите и по-възрастните в контактната мрежа. Не защото са най-заразни, а защото са най-свързващи — често живеят едновременно с деца и с възрастни родители.
Мрежовата епидемиология даде и по-добри идеи за реакция. Вместо общи карантини, математически изчислените стратегии могат да таргетират точно възлите с най-висока централност — „супер-разпространителите". Затваряне на училища, офиси или конкретни транспортни възли, където betweenness е най-висока, може да забави разпространението повече, отколкото пропорционално общо ограничение.
Четирите цвята: триумфът и провокацията
Една от най-популярните задачи в цялата теория на графите възниква през 1852 г., когато младият британец Франсис Гутри забелязва странен факт, докато оцветява графства в Англия: достатъчни ли са четири цвята, за да оцветим всяка карта така, че съседни области да нямат един и същи цвят?
Задачата изглежда невинна, но устоява на всички опити за решение в продължение на над 120 години. През 1879 г. Алфред Кемпе публикува „доказателство", което се оказва погрешно цели 11 години по-късно. През 1890 г. Пърси Хевуд доказва по-слабия вариант — петцветната теорема — но пълното твърдение остава отворено.
През 1976 г. Кенет Апел и Волфганг Хакен от Университета в Илинойс обявяват, че теоремата е доказана. Но как? С помощта на компютър. Те свеждат задачата до проверка на 1936 конкретни конфигурации и използват над 1200 часа компютърно време, за да ги анализират систематично.
Резултатът предизвиква бурен дебат. Това математическо доказателство ли е, ако никой човек не може да го провери цялото? Много математици са дълбоко разочаровани — елегантно „човешко" доказателство все още липсва и до днес. Но теоремата стои: всяка равнинна карта може да бъде оцветена с четири цвята.
През 1997 г. Робертсън, Сандърс, Сеймур и Томас публикуват по-просто компютърно-подпомогнато доказателство, свеждайки броя на конфигурациите до 633. А през 2005 г. Жорж Гонтие формално верифицира доказателството с теорем-доказваща програма.
Проблемът за четирите цвята е исторически важен и по друга причина: той е първият случай на компютърно-подпомогнато доказателство на голяма математическа теорема. Този епизод променя и разбирането за това каква роля могат да играят компютрите в математическото доказване — тема, която днес е още по-актуална с развитието на формалната верификация и инструментите с изкуствен интелект.
Още приложения: графи навсякъде
Списъкът на приложенията на теорията на графите е практически безкраен. Ето няколко от най-видимите, освен вече дискутираните:
- Логистика и доставки: DHL, FedEx, Amazon използват сложни комбинации от алгоритми за най-къс път и задача на търговския пътник, за да оптимизират милиони доставки дневно.
- Бази данни: графови бази данни като Neo4j и Amazon Neptune съхраняват данни като връзки между възли, което е идеално за социални мрежи, препоръчителни системи и анализ на измами.
- Изкуствен интелект: Graph Neural Networks (GNN) са ново поколение модели, които прилагат дълбоко обучение върху графови структури. Те се оказват особено полезни в откриването на нови лекарства — молекулите естествено се представят като графи (атомите са върхове, химичните връзки са ребра), а GNN често показват много добри резултати при предсказване на свойства, токсичност и взаимодействия на молекули.
- Биология и химия: метаболитните пътища са графи; филогенетичните дървета са графи. Анализът им дава основа на цялата съвременна биоинформатика.
- Компютърни мрежи и интернет: протоколи като OSPF и IS-IS (рутиране), както и алгоритми за детекция на измами в онлайн рекламата, се базират на анализ на графи.
- Финанси и икономика: финансови мрежи моделират връзки между банки и компании; централността помага да се идентифицират „твърде големи, за да фалират" институции.
- Лингвистика и формални езици: естествените езици могат да се моделират като графи на думи и асоциации, което помага за машинен превод и обработка на естествен език. Самите формални езици и граматики, стоящи в основата на всички програмни езици и компилатори, се представят чрез графови и дървовидни структури.
Математическата абстракция: силата на простотата
Когато погледнем назад към този дълъг път — от мостовете на Кьонигсберг през 1736 г. до мрежовата епидемиология на COVID-19 — една тема се прокрадва непрекъснато: силата на абстракцията.
Ойлер успя да види, че географските детайли на Кьонигсберг не са важни. Уотс и Строгац успяха да видят, че точната природа на „връзката" между неврони, актьори или електрически възли не е важна. Пейдж и Брин успяха да видят, че хипервръзката в интернет е структурно същото нещо като цитиране в научна статия. Барабаши и Алберт успяха да видят, че едни и същи статистически закони управляват мрежите на web, цитирания и дори метаболизма на клетките.
Точно тази способност да се изолира същественото от несъщественото превръща математиката в универсален език. Една и съща теорема — например, че в Ойлеров път всички върхове освен най-много два трябва да имат четна степен — се прилага без изменение към мостове, компютърни мрежи, пътни системи, генетични пътища и много други.
Както отбелязва Джак Мъртаг в своя материал за Scientific American (март 2024 г.): идеята да сведем картата на Кьонигсберг до гол граф изглежда очевидна в ретроспекция — но такива са много от най-добрите абстракции. Историята на математиката е до голяма степен история на силата на абстракцията.
Може би най-неочакваното в историята на графовете е колко плодотворно се оказа едно „банално" упражнение. Ойлер решава задачата за Кьонигсберг най-вече защото му се струва любопитно упражнение. Тогава едва ли някой би предположил, че след близо 290 години децата ще учат същите идеи в часовете по информатика, Google ще ги използва, за да подрежда резултатите, които виждаме в интернет, а здравните власти ще ги прилагат, за да забавят пандемии.
Днес графите стоят в основата на алгоритми, бази данни, компютърни мрежи, изкуствен интелект, оптимизация и анализ на големи данни. Те са един от най-ярките примери за това как една, на пръв поглед абстрактна математическа идея може да промени начина, по който разбираме света.
Следващия път, когато отворите Google Maps или влезете в социалните мрежи, може би ще си спомните, че всичко това започва със седем моста в пруски град преди близо 290 години. И с един математик, който видя, че в задачата има нещо повече от градска разходка.
Може би точно в това е най-красивото в математиката: че една проста идея за точки и линии може да се окаже език за описване на цели светове.
Източници
- Joshi, V. A Gentle Introduction to Graph Theory. Medium / basecs, 2017. medium.com/basecs
- Plus Maths. From bridges to networks. plus.maths.org
- Plus Maths. The bridges of Königsberg. From the series „Five of Euler's best“. plus.maths.org
- Plus Maths. Graphs and networks. Topic page. plus.maths.org
- Math Insight. An introduction to networks. mathinsight.org
- Math Insight. Small world networks. mathinsight.org
- Plus Maths. Six degrees of separation. plus.maths.org
- Built In. Social Network Analysis: How to Get Started. builtin.com
- Rodrigue, J-P. A.5 – Graph Theory: Definition and Properties. The Geography of Transport Systems. transportgeography.org
- Rodrigue, J-P. A.6 – Graph Theory: Measures and Indices. The Geography of Transport Systems. transportgeography.org
- Levin, J. & Strogatz, S. How Does Graph Theory Shape Our World? The Joy of Why, Quanta Magazine, 26 June 2025. Interview with Maria Chudnovsky. quantamagazine.org
- Honner, P. Math That Lets You Think Locally but Act Globally. Quanta Magazine, 21 July 2023. quantamagazine.org
- Murtagh, J. How a Classic Bridge-Crossing Puzzle Inspired New Math. Scientific American, 9 March 2024. scientificamerican.com
- Watts, D. J. & Strogatz, S. H. Collective dynamics of 'small-world' networks. Nature, 393 (1998), 440–442.
- Barabási, A.-L. & Albert, R. Emergence of scaling in random networks. Science, 286 (1999), 509–512.
- Broido, A. D. & Clauset, A. Scale-free networks are rare. Nature Communications, 10 (2019), 1017. nature.com
- Bryan, K. & Leise, T. The $25,000,000,000 Eigenvector: The Linear Algebra Behind Google. SIAM Review, 48(3), 2006, 569–581.
- Cornell Chronicle. Mathematical model that 'changed everything' turns 25. 2023. news.cornell.edu
- Dijkstra, E. W. A note on two problems in connexion with graphs. Numerische Mathematik, 1 (1959), 269–271.
- Frana, P. L. & Misa, T. J. An Interview with Edsger W. Dijkstra. Communications of the ACM, 53(8) (2010), 41–47. Interview conducted in August 2001 by Philip Frana for the Charles Babbage Institute. cacm.acm.org
- Kirkley, A., Barbosa, H., Barthelemy, M. & Ghoshal, G. From the betweenness centrality in street networks to structural invariants in random planar graphs. Nature Communications, 9 (2018), 2501. nature.com
- Silva, C., Machado, P., Leitão, R., Pinheiro, S. & Afreixo, V. Graph Theory Approach to COVID-19 Transmission by Municipalities and Age Groups. Mathematical and Computational Applications, 27(5) (2022), 86. mdpi.com
- Appel, K. & Haken, W. Every planar map is four colorable. Illinois Journal of Mathematics, 21 (1977), 429–490.
- Robertson, N., Sanders, D., Seymour, P. & Thomas, R. The Four-Colour Theorem. Journal of Combinatorial Theory, Series B, 70 (1997), 2–44.
- Karp, R. M. Reducibility Among Combinatorial Problems. In: Complexity of Computer Computations (eds. Miller & Thatcher), 1972, 85–103.
Още от поредицата „Любопитно от математиката“
Запишете урок
Индивидуални и групови онлайн уроци по математика за цялата страна
- ›НВО по математика след 7 клас
- ›НВО по математика след 10 клас
- ›Кандидатстудентски изпити по математика
- ›Прием в университети в чужбина (ISEE, SAT, A-Level)
- ›Усвояване на текущия учебен материал (всички класове)
- ›Студенти: Мат. анализ, Линейна алгебра, Аналитична геометрия, Диф. уравнения, Теория на вероятностите, Статистика и др.
Харесва ли ви съдържанието?
Ако тази статия ви е харесала, можете да подкрепите създаването на нови безплатни материали.
Коментари
Публикуване на коментар