Графи в інформатиці: визначення, види, застосування, приклади. Теорія графів в інформатиці
Графи в інформатиці є способом визначення відносин в сукупності елементів. Це основні об`єкти вивчення теорії графів.
базові визначення
З чого складається граф в інформатиці? Він включає безліч об`єктів, званих вершинами або вузлами, деякі пари яких пов`язані т. Н. ребрами. Наприклад, граф на малюнку (а) складається з чотирьох вузлів, позначених А, В, С, і D, з яких B з`єднаний з кожною з трьох інших вершин ребрами, а C і D також з`єднані. Два вузла є сусідніми, якщо вони з`єднані ребром. На малюнку показаний типовий спосіб того, як будувати графи з інформатики. Кола представляють вершини, а лінії, що з`єднують кожну їх пару, є ребрами.
Який граф називається неорієнтованим в інформатиці? У нього відносини між двома кінцями ребра є симетричними. Ребро просто з`єднує їх один з одним. У багатьох випадках, однак, необхідно висловити асиметричні відносини - наприклад, те, що A вказує на B, але не навпаки. Цій меті служить визначення графа в інформатиці, як і раніше складається з набору вузлів разом з набором орієнтованих ребер. Кожне орієнтоване ребро являє собою зв`язок між вершинами, напрямок якої має значення. Спрямовані графи зображують так, як показано на малюнку (b), ребра їх представлені стрілками. Там, де необхідно підкреслити, що граф ненаправленої, його називають неорієнтованим.
моделі мереж
Графи в інформатиці служать математичною моделлю мережевих структур. На наступному малюнку представлена структура інтернету, тоді носив назву ARPANET, в грудні 1970 року, коли вона мала лише 13 точок. Вузли представляють собою обчислювальні центри, а ребра з`єднують дві вершини з прямим зв`язком між ними. Якщо не звертати уваги на накладену карту США, інша частина зображення є 13-вузловим графом, подібним попереднім. При цьому дійсне розташування вершин несуттєво. Важливо, які вузли з`єднані один з одним.
Застосування графів в інформатиці дозволяє уявити, як речі або фізично, або логічно пов`язані між собою в мережевій структурі. 13-вузловий ARPANET є прикладом комунікаційної мережі, в якій вершини-комп`ютери або інші пристрої можуть передавати повідомлення, а ребра є прямі лінії зв`язку, по яким інформація може бути передана.
Маршрути
Хоча графи застосовуються в багатьох різних областях, вони мають загальні риси. Теорія графів (інформатика) включає, можливо, найважливішу з них - ідею про те, що речі часто переміщаються по ребрах, послідовно переходячи від вузла до вузла, будь то пасажир кількох авіарейсів або інформація, що передається від людини до людини в соціальній мережі, або користувач комп`ютера, послідовно відвідує ряд веб-сторінок, слідуючи по посиланнях.
Відео: Інформатика. Теорія графів. Зберігання графа: списки суміжних вершин. Центр онлайн-навчання «Фоксфорд»
Ця ідея мотивує визначення маршруту як послідовності вершин, пов`язаних між собою ребрами. Іноді виникає необхідність розглядати маршрут, який містить не тільки вузли, але і послідовність ребер, їх з`єднують. Наприклад, послідовність вершин MIT, BBN, RAND, UCLA є маршрутом в графі інтернету ARPANET. Проходження вузлів і ребер може бути повторним. Наприклад, SRI, STAN, UCLA, SRI, UTAH, MIT також є маршрутом. Шлях, в якому ребра не повторюються, називається ланцюгом. Якщо ж не повторюються вузли, то він носить назву простий ланцюга.
цикли
Особливо важливі види графів в інформатиці - це цикли, які представляють собою кільцеву структуру, таку як послідовність вузлів LINC, CASE, CARN, HARV, BBN, MIT, LINC. Маршрути з, принаймні, трьома ребрами, у яких перший і останній вузол однакові, а інші різні, є циклічні графи в інформатиці.
Приклади: цикл SRI, STAN, UCLA, SRI є найкоротшим, а SRI, STAN, UCLA, RAND, BBN, UTAH, SRI значно більше.
Фактично кожне ребро графа ARPANET належить до циклу. Це було зроблено навмисно: якщо будь-яка з них вийде з ладу, залишиться можливість переходу з одного вузла в інший. Цикли в системах комунікації та транспорту присутні для забезпечення надмірності - вони передбачають альтернативні маршрути іншим шляхом циклу. У соціальній мережі теж часто помітні цикли. Коли ви виявите, наприклад, що близький шкільний друг кузена вашої дружини насправді працює з вашим братом, то це є циклом, який складається з вас, вашої дружини, її двоюрідного брата, його шкільного друга, його співробітника (т. Е. Вашого брата) і, нарешті, знову вас.
Зв`язний граф: визначення (інформатика)
Природно задатися питанням, чи можна з кожного вузла потрапити в будь-який інший вузол. Граф зв`язний, якщо між кожною парою вершин існує маршрут. Наприклад, мережа ARPANET - зв`язний граф. Те ж можна сказати і про більшість комунікаційних і транспортних мереж, так як їх мета полягає в тому, щоб направляти трафік від одного вузла до іншого.
Відео: 11 - Бази даних. GraphDB: Поняття граф. Застосування. типи графів
З іншого боку, немає ніяких апріорних підстав очікувати того, що дані види графів в інформатиці широко поширені. Наприклад, в соціальній мережі нескладно уявити двох людей, не пов`язаних між собою.
компоненти
Якщо графи в інформатиці не пов`язані, то вони природним чином розпадаються на набір пов`язаних фрагментів, груп вузлів, які є ізольованими і не перетинаються. Наприклад, на малюнку зображено три таких частини: перша - А і В, друга - C, D і Е, і третя складається з решти вершин.
Компоненти зв`язності графа представляють собою підмножина вузлів, у яких:
- кожна вершина підгрупи має маршрут до будь-якої іншої;
- підмножина не є частиною деякого більшого набору, в якому кожен вузол має маршрут до будь-якого іншого.
Коли графи в інформатиці поділяються на їх компоненти, то це є лише початковим способом опису їх структури. В рамках даного компонента може бути багата внутрішня структура, важлива для інтерпретації мережі. Наприклад, формальним методом визначення важливості вузла є визначення того, на скільки частин розділиться граф, якщо вузол буде прибраний.
Максимальна компонента
Існує метод якісної оцінки компонентів зв`язності. Наприклад, є всесвітня соціальна мережа зі зв`язками між двома людьми, якщо вони є друзями.
Зв`язкова вона? Ймовірно, немає. Можливості підключення - досить крихке властивість, і поведінка одного вузла (або невеликого їх набору) може звести її нанівець. Наприклад, одна людина без будь-яких живих друзів буде компонентом, що складається з єдиною вершини, і, отже, граф не буде зв`язковим. Або віддалений тропічний острів, що складається з людей, які не мають ніякого контакту із зовнішнім світом, також буде невеликий компонентою мережі, що підтверджує її незв`язність.
Глобальна мережа друзів
Але є ще дещо. Наприклад, читач популярної книги має друзів, які виросли в інших країнах, і становить з ними одну компоненту. Якщо взяти до уваги батьків цих друзів і їхніх друзів, то всі ці люди також знаходяться в тій же компоненті, хоча вони ніколи не чули про читача, говорять іншою мовою і поруч з ним ніколи не були. Таким чином, хоча глобальна мережа дружби - НЕ зв`язкова, читач буде входити в компонент дуже великого розміру, що проникає в усі частини світу, що включає в себе людей з різних верств і, фактично, містить значну частину населення земної кулі.
Те ж має місце і в мережевих наборах даних - великі, складні мережі часто мають максимальну компоненту, яка включає значну частину всіх вузлів. Більш того, коли мережа містить максимальну компоненту, вона майже завжди тільки одна. Щоб зрозуміти, чому, слід повернутися до прикладу з глобальною мережею дружби і спробувати уявити наявність двох максимальних компонент, кожна з яких включає мільйони людей. Буде потрібно наявність єдиного ребра від кого-то з першої компоненти до другої, щоб дві максимальні компоненти злилися в одну. Так як ребро єдине, то в більшості випадків неймовірно, щоб воно не утворилося, і, отже, дві максимальні компоненти в реальних мережах ніколи не спостерігаються.
У деяких рідкісних випадках, коли дві максимальні компоненти співіснували протягом тривалого часу в реальній мережі, їх об`єднання було несподіваним, драматичним, і, в кінцевому підсумку, мало катастрофічні наслідки.
Катастрофа злиття компонент
Наприклад, після прибуття європейських дослідників в цивілізації Західної півкулі приблизно півтисячоліття тому стався глобальний катаклізм. З точки зору мережі це виглядало так: п`ять тисяч років глобальна соціальна мережа, ймовірно, складалася з двох гігантських компонент - однієї в Північній і Південній Америці, а інший - в Євразії. З цієї причини технології розвивалася незалежно в двох компонентах, і, що ще гірше, так само розвивалися і хвороби людини і т. Д. Коли дві компоненти, нарешті, увійшли в контакт, технології і захворювання однієї швидко і катастрофічно переповнили другу.
Американська середня школа
Поняття максимальних компонент корисно для міркувань про мережах і в набагато менших розмірах. Цікавий приклад являє собою граф, який ілюструє романтичні стосунки в американській середній школі за 18-місячний період. Той факт, що він містить максимальну компоненту, має важливе значення, коли мова заходить про поширення захворювань, що передаються статевим шляхом, що і було метою проведеного дослідження. Учні, можливо, мали лише одного партнера за цей період часу, але, тим не менш, не усвідомлюючи цього, були частиною максимальної компоненти і, отже, частиною багатьох маршрутів потенційної передачі. Ці структури відображають відносини, які, можливо, давно закінчилася, але вони пов`язують індивідуумів в ланцюгах занадто довго, щоб стати предметом пильної уваги і пліток. Проте, вони реальні: як соціальні факти це невидимі, але логічно випливають макроструктури, що виникли як продукт індивідуального посередництва.
Відстань і пошук в ширину
На додаток до відомостей про те, чи пов`язані два вузла маршрутом, теорія графів в інформатиці дозволяє дізнатися і про його довжині - в транспорті, зв`язку або при поширенні новин та захворювань, а також про те, чи проходить він через кілька вершин або безліч.
Відео: Лекція 12: Теорія графів. Основні поняття (продовження)
Для цього слід визначити довжину маршруту, рівну числу кроків, які він містить від початку до кінця, т. Е. Число ребер в послідовності, яка його складає. Наприклад, маршрут MIT, BBN, RAND, UCLA має довжину 3, а MIT, UTAH - 1. Використовуючи довжину шляху, можна говорити про те, чи розташовані два вузла в графі близько один до одного або далеко: відстань між двома вершинами визначається як довжина найкоротшого шляху між ними. Наприклад, відстань між LINC і SRI дорівнює 3, хоча, щоб переконатися в цьому, слід упевнитися у відсутності довжини, яка дорівнює 1 або 2, між ними.
Алгоритм пошуку в ширину
Для невеликих графів відстань між двома вузлами підрахувати легко. Але для складних з`являється необхідність в систематичному методі визначення відстаней.
Найприроднішим способом це зробити і, отже, найбільш ефективним, є наступний (на прикладі глобальної мережі друзів):
- Всі друзі оголошуються знаходяться на відстані 1.
- Всі друзі друзів (не рахуючи вже зазначених) оголошуються знаходяться на відстані 2.
- Всі їхні друзі (знову ж таки, не рахуючи позначених людей) оголошуються віддаленими на відстань 3.
Продовжуючи таким чином, пошук проводять в наступних шарах, кожен з яких - на одиницю далі попереднього. Кожен новий шар складається з вузлів, які ще не брали участі в попередніх, і які входять в ребро з вершиною попереднього шару.
Ця техніка називається пошуком в ширину, так як вона виконує пошук по графу назовні від початкового вузла, в першу чергу охоплюючи найближчі. На додаток до надання способу визначення відстані, вона може служити корисною концептуальною основою для організації структури графа, а також того, як побудувати граф з інформатики, розташовуючи вершини на підставі їх відстані від фіксованої початкової точки.
Пошук в ширину може бути застосований не лише до мережі друзів, а й до будь-якого графу.
Світ тісний
Якщо повернутися до глобальної мережі друзів, можна побачити, що аргумент, що пояснює приналежність до максимальної компоненті, насправді стверджує щось більше: не тільки у читача є маршрути до друзів, що зв`язують його зі значною часткою населення земної кулі, але ці маршрути на подив короткі .
Ця ідея отримала назву «феномена тісного світу»: світ здається маленьким, якщо думати про те, який короткий маршрут пов`язує будь-яких двох людей.
Теорія «шести рукостискань» вперше експериментально досліджувалась Стенлі Мілгрем і його колегами в 1960-і роки. Не маючи будь-якого набору даних соціальних мереж і з бюджетом в 680 доларів він вирішив перевірити популярну ідею. З цією метою він попросив 296 випадково відібраних ініціаторів спробувати відіслати листа біржовому брокеру, який жив в передмісті Бостона. Ініціаторам були дані деякі особисті дані про мету (включаючи адресу і професію), і вони повинні були переслати лист особі, якого вони знали по імені, з тими ж інструкціями, щоб воно досягло мети якомога швидше. Кожен лист пройшло через руки ряду друзів і утворило ланцюжок, замикає на біржовому брокерові за межами Бостона.
Серед 64 ланцюжків, які досягли мети, середня довжина дорівнювала шести, що підтвердило число, назване два десятиліття раніше в назві п`єси Джона Гера.
Незважаючи на всі недоліки цього дослідження, експеримент продемонстрував один з найважливіших аспектів нашого розуміння соціальних мереж. У наступні роки з нього був зроблений більш широкий висновок: соціальні мережі, як правило, мають дуже короткі маршрути між довільними парами людей. І навіть якщо такі непрямі зв`язки з керівниками підприємств і політичними лідерами не окупаються на щоденній основі, існування таких коротких маршрутів грає велику роль в швидкості поширення інформації, хвороб та інших видів зараження в суспільстві, а також в можливості доступу, які соціальна мережа надає людям з абсолютно протилежними якостями.
