Бұл не?
Сабақтың тақырыбы — «Граф дегеніміз не». Талдап көрейік. Метро сұлбасын елестет: дөңгелектер — станциялар, олардың арасындағы сызықтар — аралықтар. Міне, бұл граф: төбелер мен төбелер жұптарын қосатын қабырғалар жиыны. Графқа дөңгелектің қай жерде салынғаны маңызды емес, тек неменің немен қосылғаны маңызды.
Бұл не үшін керек?
Графтар барлық жерде дерлік жасырынған: навигаторлар мен жеткізу қызметтерінде, ұшқышсыз дрондар мен қойма роботтарының маршруттарында, электр желілерінің сұлбаларында және дата-орталықтардағы серверлер арасындағы байланыс желілерінде. Айтпақшы, нейрожелілерді де түйіндер мен байланыстардан тұратын граф ретінде салады, ал жаңа дәрілер мен материалдардың молекулаларын химиктер атомдар графымен сипаттайды. Он жылдан кейін жасанды интеллект миллиондаған нұсқаны өзі сұрыптайтын болады, бірақ тапсырманы графқа айналдыруға болатынын, нені төбе, нені қабырға деп санау керегін және оларға қандай салмақ беру керегін біреу түсінуі керек. Әлемге осылай қарай алатын адам машиналарға тапсырма қойып, олардың бос нәрсе есептемегенін тексере алады.
Бұл қалай жұмыс істейді?
Төбелер — нысандар: станциялар, адамдар, веб-беттер, ал қабырғалар — олардың арасындағы байланыстар. Егер байланыс достық сияқты өзара болса, қабырғаны қарапайым сызықпен салады, ал графты бағытталмаған деп атайды. Егер байланыс бір беттен екіншісіне сілтеме сияқты бір жаққа бағытталса, қабырғаны нұсқармен салып, оны доға деп атайды, ал графты — бағытталған. Егер қабырғаларда сандар жазылса — минуттар, километрлер немесе баға, — граф салмақталған болады. Ал төбенің дәрежесі — оған келетін қабырғалардың жай ғана саны; нұсқарлар үшін кіретіндері мен шығатындарын бөлек санайды.
Аздап тарих
Графтар теориясын ұлы математик Леонард Эйлер бастады. Кёнигсберг қаласының тұрғындары өзеннің үстіндегі жеті көпірдің әрқайсысында дәл бір рет болып, бәрінен өтуге бола ма деп таласатын. Эйлер жағалаулар мен аралдарды нүктелермен, ал көпірлерді сызықтармен алмастырып, мұндай серуеннің мүмкін емес екенін дәлелдеді: тым көп нүктеде сызықтар саны тақ. Осылайша қала аралау туралы есеп граф туралы алғашқы есепке айналды.
Формула: дәрежелер қосындысы
Кез келген қабырғаға қара: оның екі ұшы бар, және әр ұшы өз төбесінің дәрежесіне бір қосады. Демек, барлық төбелердің дәрежелерін қосқанда, әр қабырға дәл екі рет есептеледі. Осыдан формула шығады: дэ бір қосу дэ екі қосу және солай дэ энге дейін тең екі көбейтілген е. Мұндағы нөмірі бар дэ — әр төбенің дәрежесі, эн — төбелер саны, ал е — қабырғалар саны; мұның бәрі өлшем бірлігі жоқ, жай сандар. Графқа бір қабырға қоссаң — дәрежелер қосындысы бірден екіге өседі. Мысалы, метро сұлбасында тоғыз қабырға бар, демек, барлық станциялар дәрежелерінің қосындысы он сегізге тең.
d₁ + d₂ + … + dₙ = 2·Ed₁…dₙ — төбелердің дәрежелері, —
n — төбелер саны, —
E — қабырғалар саны, —
Практикада не істейміз?
Ал енді практикалық тапсырманы орындап көрейік. Қазір алдыңда «Метро» графы тұр: жеті станция және жолдағы минуттары көрсетілген тоғыз аралық — төбелерді сүйреп көріп, граф бұдан өзгермейтініне көз жеткізе аласың. Содан кейін «Әлеуметтік желі» графын ашып, досы ең көп адамды, яғни дәрежесі ең үлкен төбені тап: әрқайсысының қабырғаларын мұқият санап шық. «Веб» графында ең көп сілтеме апаратын бет керек, сондықтан онда тек кіретін нұсқарларды сана. Төбені таңдап, «Бұл жауап» батырмасын бас. Бірдеңе түсініксіз болып қалса — ештеңе етпейді, менен кез келген нәрсені сұра, жауап беремін. Уайымдама.