Графтарды сипаттау

Міне, әлеуметтік желіні көрсетудің бір жолы:

Екі адамның аты-жөні арасындағы сызық олардың бірін-бірі танитынын білдіреді. Екі есімнің арасында шекара болмаса, халық бірін-бірі танымайды. «Бірін-бірі тану» қарым-қатынасы екі бағытта жүреді; мысалы, Одри Гейлді танитындықтан, бұл Гейл Одриді танитынын білдіреді.

Бұл график - әлеуметтік желі. Атаулар графиктің төбелері болып табылады. (Егер сіз тек бір төбе туралы айтып жатсаңыз, бұл төбе болып табылады.) Әрбір жол екі төбені байланыстыратын қыры болып табылады. $u$‍ және $v$‍ шыңдарын байланыстыратын қырды $(u,v)$‍ жұбы арқылы белгілейміз. «Бірін-бірі тану» қатынасы екі жақты болғандықтан, бұл график бағытталмаған . $(u,v)$‍ бағытталмаған қыры $(v,u)$‍ сияқты. Кейінірек біз бағытталған графиктерді көреміз, онда төбелер арасындағы қатынастар міндетті түрде екі бағытта да жүрмейді. Бағытсыз графикте екі төбенің арасындағы қыр, мысалы, Одри мен Гейл арасындағы қыр сияқты, екі төбе арқылы өтеді , ал қыры арқылы байланысқан төбелерді іргелес немесе көршелес дейміз. Төбе арқылы өтетін қырлар саны төбе дәрежесі деп аталады.

Одри мен Фрэнк бір-бірін танымайды. Фрэнк Одримен танысқысы келді делік. Олар қалай танысады? Ол Одриді танитын Биллді, ал Биллді танитын Эмилиді таниды. Біз Фрэнк пен Одри арасында үш қырдан тұратын жол бар деп айтамыз. Шын мәнінде, бұл Фрэнк үшін Одримен кездесудің ең тікелей жолы; олардың арасында үш қырдан аз жол жоқ. Қырлары ең аз екі төбенің арасындағы жолды ең қысқа жол деп атаймыз. Біз төменде ең қысқа жолды атап өттік:

Жол белгілі бір төбеден өзіне қайта оралғанда, бұл цикл деп аталады. Әлеуметтік желіде көптеген циклдар бар; олардың бірі Одриден Биллге, Биллден Эмилиге, Эмилиден Джеффке, Джеффтен Гарриге, Гарриден Иланаға және қайтадан Одриге барады. Төменде көрсетілген Одриді қамтитын қысқарақ цикл бар: Одриден Биллге, Биллден Гейлге дейін және Гейлдан Одриге. Тағы қандай циклдарды таба аласыз?

Кейде біз қырларға сандық мәндерді қоямыз. Мысалы, әлеуметтік желіде біз екі адамның бір-бірін қаншалықты жақсы білетінін көрсету үшін мәндерді пайдалана аламыз. Басқа мысал келтіру үшін жол картасын график түрінде көрсетейік. Бір жақты көшелер жоқ деп есептесек, жол картасы да бағытталмаған график болып табылады, қалалар төбелер ретінде, жолдар қырлар ретінде және қырлардағы мәндер әр жолдың қашықтығын көрсетеді. Мысалы, АҚШ-тың солтүстік-шығысындағы кейбір мемлекетаралық магистральдардың қырлар қашықтықтары бар жол картасы (масштабсыз):

Біз қырына қоятын сан үшін қолданатын жалпы термин оның салмағы , ал қырларының салмағы бар график өлшенген граф болып табылады.Жол картасы жағдайында, екі нүкте арасындағы ең қысқа жолды тапқыңыз келсе, екі шыңның арасындағы барлық жолдар бойындағы қыр салмақтарының ең аз қосындысы бар екі төбе арасындағы жолды іздейсіз. Салмақсыз графиктер сияқты, біз мұны ең қысқа жол деп атаймыз. Мысалы, осы графиктегі Нью-Йорктен Конкордқа дейінгі ең қысқа жол Нью-Йорктен Нью-Хейвенге, одан кейін Хартфордқа, Стурбриджге, Уэстонға, Рединг пен Конкордқа небәрі 289 миль.

Төбелер арасындағы қатынас әрқашан екі жақты бола бермейді. Мысалы, жол картасында бір жақты көшелер болуы мүмкін. Немесе хоккей қақпашысының киіну тәртібін көрсететін график:

Енді көрсеткілермен көрсетілген қырлар бағытталған және бізде бағытталған график бар. Мұнда нұсқаулар басқа бөліктерден бұрын қандай жабдықты кию керектігін көрсетеді. Мысалы, кеуде жастықшасынан жемпірге дейінгі қыр кеуде жастықшасын жемпірдің алдында кию керек екенін көрсетеді. Шыңдардың жанындағы сандар жабдықты киюге болатын көптеген ықтимал тәртіптердің бірін көрсетеді, осылайша алдымен шолақ шалбар, содан кейін шұлықтар, содан кейін қысқыш шолақ шалбары және т.б., және ең соңғысы бөгегіш. Сіз бұл нақты бағытталған графикте цикл жоқ екенін байқаған боларсыз; мұндай графикті бағытталған ациклдік граф деп атаймыз. Әрине, бізде бір жақты көшелер мен жол қашықтықтары бар жол карталары сияқты өлшенген бағытталған графиктер болуы мүмкін.

Біз қырлары бағытталған әртүрлі терминологияны қолданамыз. Бағытталған қыр бір төбеден шығып, екінші төбеге кіреді дейміз. Мысалы, бір бағытталған қыр кеуде жастықшасы үшін үстіңгі жағынан шығып, жемпір үшін үстіңгі жағына шығады. Егер бағытталған қыр $u$‍ төбесінен шығып, $v$‍ төбесіне кірсе, оны $(u,v)$‍ деп белгілейміз және жұптағы төбелердің реті маңызды. Төбеден шығатын қырлар саны оның сыртқы дәрежесі , ал кіретін жиектер саны ішкі дәрежесі .

Сіз ойлағандай, графиктердің - бағытталған және бағытталмаған - нақты әлемдегі қарым-қатынастарды модельдеуге арналған көптеген қолданбалары бар.

Графиктермен жұмыс істегенде, төбелер жиыны мен қырлар жиыны туралы айта білу пайдалы. Біз әдетте төбелер жиынын $V$‍ және қырлар жиынын $E$‍ деп белгілейміз. Біз графикті көрсеткенде немесе графикте алгоритмді іске қосқанда, біз көбінесе асимптотикалық белгілерде төбе мен қырлардың өлшемдерін қолданғымыз келеді. Мысалы, төбелердің санына сызықты түрде тәуелді орындалу уақыты туралы айтқымыз келеді делік. Дәлірек айтқанда, $\mathrm{\Theta }(|V|)$‍ деп $|\cdot |$‍ жиынның өлшемін белгілеу үшін. Бірақ асимптотикалық белгілерде осы жиын өлшемінің белгіленуін пайдалану қиын, сондықтан біз асимптотикалық белгілеуде және тек асимптотикалық белгілеуде жиын өлшемдері туралы айтып жатқанымызды түсініп, жиын өлшемінің белгісін алып тастаймыз деген шартты қабылдаймыз. Сонымен, $\mathrm{\Theta }(|V|)$‍ деп жазудың орнына, біз тек $\mathrm{\Theta }(V)$‍ деп жазамыз. Сол сияқты, $\mathrm{\Theta }(\lg |E|)$‍ орнына $\mathrm{\Theta }(\lg E)$‍ деп жазамыз.

Бұл мазмұн ынтымақтастықтың нәтижесі Дартмут компьютерлік ғылымы профессорлар [Томас Кормен](http://www.cs.dartmouth.edu / ~thc/) және [Дэвин Бэлком](http://www.cs.dartmouth.edu / ~devin/), сонымен қатар Хан академиясының компьютерлік оқу бағдарламасы бойынша тобы. Мазмұн лицензияланған CC-BY-NC-SA.