1736, м.Кенігсберг. Через місто протікає річка Прегеля. У місті – сім мостів, розташованих так, як показано на малюнку вище. З давніх-давен жителі Кенігсберга билися над загадкою: чи можна пройти по всіх мостах, пройшовши по кожному тільки один раз? Це завдання вирішували і теоретично, на папері, і на практиці, на прогулянках - проходячи цими самими мостами. Нікому не вдавалося довести, що це нездійсненно, але й зробити таку «загадкову» прогулянку мостами ніхто не міг.

Вирішити проблему вдалося знаменитому математику Леонарду Ейлеру. Причому, він вирішив не лише це конкретне завдання, а й придумав загальний метод вирішення подібних завдань. При розв'язанні задачі про мости Кенігсберзьких Ейлер вчинив наступним чином: він "стиснув" сушу в крапки, а мости "витяг" в лінії. Таку фігуру, що складається з точок та ліній, що зв'язують ці точки, називають Графом.

Граф – це сукупність непорожньої множини вершин і зв'язків між вершинами. Гуртки називаються вершинами графа, лінії зі стрілками – дугами, без стрілок – ребрами.

Види графів:

1. Орієнтований граф(коротко орграф) - ребрам якого присвоєно напрямок.

2. Неорієнтований граф- це граф, у якому немає напряму ліній.

3. Зважений граф– дуги чи ребра мають вагу (додаткова інформація).

Розв'язання задач за допомогою графів:

Завдання 1.

Рішення: Позначимо вчених вершинами графа та проведемо від кожної вершини лінії до чотирьох інших вершин. Отримуємо 10 ліній, які і будуть вважатися рукостисканнями.

Завдання 2.

На пришкільній ділянці ростуть 8 дерев: яблуня, тополя, береза, горобина, дуб, клен, модрина та сосна. Горобина вище модрини, яблуня вище клена, дуб нижче берези, але вище сосни, сосна вище горобини, береза ​​нижче тополі, а модрина вище яблуні. Розташуйте дерева від найнижчого до найвищого.

Рішення:

Вершини графа - це дерева, позначені першою буквою назви дерева. У цьому завдання два відносини: " бути нижче " і " бути вище " . Розглянемо відношення "бути нижче" і проведемо стрілки від нижчого дерева до вищого. Якщо задачі сказано, що горобина вище модрини, то стрілку ставимо від модрини до горобини тощо. Отримуємо граф, на якому видно, що найнижче дерево - клен, потім йдуть яблуня, модрина, горобина, сосна, дуб, береза ​​та тополя.

Завдання 3.

У Наташі є 2 конверти: звичайний та авіа, і 3 марки: прямокутна, квадратна та трикутна. Скільки способів Наташа може вибрати конверт і марку, щоб надіслати листа?

Рішення:

Нижче наведено розбір завдань.

Поняття графа доцільно вводити після того, як розібрано кілька завдань, подібних до задачі 1, вирішальне міркування в яких - графічне уявлення. Важливо, щоб учні відразу усвідомили, що той самий граф може бути намальований різними способами. Суворе визначення графа, мій погляд, давати зайве, т.к. воно надто громіздке і це тільки ускладнить обговорення. Спочатку вистачить і інтуїтивного поняття. Під час обговорення поняття ізоморфізму можна вирішити кілька вправ на визначення ізоморфних та неізоморфних графів. Одне з центральних місць теми – теорема про парність числа непарних вершин. Важливо, щоб учні до кінця розібралися у її доказі та навчилися застосовувати до вирішення завдань. При аналізі кількох завдань рекомендую не посилатися на теорему, а практично повторювати її підтвердження. Надзвичайно важливим є також поняття зв'язності графа. Змістовним міркуванням тут розгляд компоненти зв'язності, цього необхідно звернути особливу увагу. Ейлерові графи – тема майже ігрова.

Перша і головна мета, яку слід переслідувати щодо графів, –навчити школярів бачити граф за умови завдання і грамотно перекладати умову на мову теорії графів. Не варто розповідати обидві всім на кількох заняттях поспіль. Краще рознести заняття за часом на 2-3 навчальні роки. (Додається розробка заняття "Поняття графа. Застосування графів для вирішення завдань" у 6 класі).

2. Теоретичний матеріал до теми "Графи".

Вступ

Графи – чудові математичні об'єкти, з допомогою можна вирішувати дуже багато різних, зовні не схожих друг на друга завдань. У математиці існує цілий розділ - теорія графів, який вивчає графи, їх властивості та застосування. Ми ж обговоримо лише основні поняття, властивості графів і деякі способи вирішення завдань.

Поняття графа

Розглянемо дві задачі.

Завдання 1. Між дев'ятьма планетами сонячної системи встановлено космічне сполучення. Рейсові ракети літають наступними маршрутами: Земля - ​​Меркурій; Плутон – Венера; Земля – Плутон; Плутон – Меркурій; Меркурій – Відні; Уран - Нептун; Нептун - Сатурн; Сатурн - Юпітер; Юпітер – Марс та Марс – Уран. Чи можна долетіти на рейсових ракетах із Землі до Марса?

Рішення:Намалюємо схему умови: планети зобразимо точками, а маршрути ракет – лініями.

Тепер одразу видно, що долетіти із Землі до Марса не можна.

Завдання 2. Дошка має форму подвійного хреста, який виходить, якщо із квадрата 4x4 прибрати кутові клітини.

Чи можна обійти її ходом шахового коня і повернутись на вихідну клітку, побувавши на всіх клітинах рівно по одному разу?

Рішення:Занумеруємо послідовно клітини дошки:

А тепер за допомогою малюнка покажемо, що такий обхід таблиці, як зазначено в умові, може бути:

Ми розглянули два несхожі завдання. Проте розв'язання цих двох завдань поєднує загальна ідея – графічне уявлення рішення. При цьому і картинки, намальовані для кожного завдання, виявились схожими: кожна картинка – це кілька точок, деякі з яких з'єднані лініями.

Такі картинки і називаються графами. Крапки при цьому називаються вершинами, а лінії – ребрамиграфів. Зауважимо, що не кожна картинка такого виду називатиметься графом. Наприклад. якщо вас попросять намалювати в зошиті п'ятикутник, то такий малюнок графом не буде. Будемо називати що малюнок такого виду, як у попередніх задачах, графом, якщо є якесь конкретне завдання для якого такий малюнок побудований.

Інше зауваження стосується виду графа. Спробуйте перевірити, що граф для одного і того ж завдання можна намалювати різними способами; і навпаки для різних завдань можна намалювати однакові на вигляд графи. Тут важливо лише те, які вершини з'єднані одна з одною, а які – ні. Наприклад, граф для задачі 1 можна намалювати по-іншому:

Такі однакові, але по-різному намальовані графи називаються ізоморфними.

Ступені вершин та підрахунок числа ребер графа

Запишемо ще одне визначення: Ступенем вершини графа називається кількість ребер, що виходять з неї. У зв'язку з цим, вершина, що має парний ступінь, називається парною вершиною, відповідно, вершина, що має непарний ступінь, називається непарною вершиною.

З поняттям ступеня вершини пов'язана одна з основних теорем теорії графів - теорема про чесність числа непарних вершин. Доведемо її трохи пізніше, а спочатку для ілюстрації розглянемо завдання.

Завдання 3. У місті Маленькому 15 телефонів. Чи можна їх з'єднати проводами так, щоб кожен телефон був з'єднаний з п'ятьма іншими?

Рішення:Припустимо, що таке з'єднання телефонів можливо. Тоді уявімо собі граф, у якому вершини позначають телефони, а ребра – дроти, що їх з'єднують. Підрахуємо, скільки всього вийде дротів. До кожного телефону підключено 5 проводів, тобто. ступінь кожної вершини нашого графа 5. Щоб знайти число проводів, треба підсумувати ступеня всіх вершин графа і отриманий результат розділити на 2 (бо кожен провід має два кінці, то при підсумовуванні ступенів кожен провід буде взято 2 рази). Але тоді кількість проводів вийде різною. Але це число не ціле. Отже, наше припущення про те, що можна з'єднати кожен телефон рівно з п'ятьма іншими, виявилося неправильним.

Відповідь.Таким чином неможливо з'єднати телефони.

Теорема: Будь-який граф містить парне число непарних вершин.

Доказ:Кількість ребер графа дорівнює половині суми ступенів його вершин. Оскільки кількість ребер має бути цілим числом, то сума ступенів вершин має бути парною. А це можливо лише в тому випадку, якщо граф містить парне число непарних вершин.

Зв'язність графа

Є ще одне важливе поняття, що стосується графів – поняття зв'язності.

Граф називається зв'язковим,якщо з будь-які дві його вершини можна з'єднати шляхом,тобто. безперервною послідовністю ребер. Існує ціла низка завдань, вирішення яких засноване на понятті зв'язності графа.

Завдання 4. У країні сімка 15 міст, кожен з міст з'єднаний дорогами не менше, ніж з сімома іншими. Доведіть, що з кожного міста модно дістатися будь-якої іншої.

Доказ: Розглянемо два довільні А і В міста і припустимо, що між ними немає шляху Кожен з них з'єднаний дорогами не менше, ніж з сімома іншими, причому немає такого міста, яке було б з'єднане з обома розглянутими містами (інакше існував би шлях з A до B). Намалюємо частину графа, що відповідає цим містам:

Тепер очевидно, що ми отримали щонайменше різних 16 міст, що суперечить умові завдання. Отже, твердження доведене від протилежного.

Якщо взяти до уваги попереднє визначення, то затвердження завдання можна переформулювати і по-іншому: "Довести, що граф доріг країни Семерка пов'язаний."

Тепер ви знаєте, як виглядає зв'язковий граф. Незв'язний граф має вигляд кількох “шматків”, кожен із яких – чи окрема вершина без ребер, чи зв'язковий граф. Приклад нескладного графа ви бачите на малюнку:

Кожен такий окремий шматок називається компонентом зв'язності графа.Кожна компонента зв'язності є зв'язним графом і для неї виконуються всі твердження, які ми довели для зв'язкових графів. Розглянемо приклад задачі, в якій використовується компонент зв'язності:

Завдання 5. У Тридев'ятому царстві лише один вид транспорту – килим-літак. Зі столиці виходить 21 ковролінія, з міста Далекий – одна, а з решти міст – по 20. Доведіть, що зі столиці можна долетіти до міста Далекий.

Доказ:Зрозуміло, що й намалювати граф ковроліній Царства, він може бути нескладним. Розглянемо компоненту зв'язності, що включає столицю Царства. Зі столиці виходить 21 ковролінія, а з будь-яких інших міст, крім міста Далекий – по 20, тому, щоб виконувався закон про парне число непарних вершин необхідно, щоб і місто Далеке входило в цю ж саму компоненту зв'язності. Оскільки компонента зв'язності – зв'язний граф, зі столиці існує шлях по ковролініям до міста Далекий, що й потрібно довести.

Графи Ейлера

Ви, напевно, стикалися з завданнями, в яких потрібно намалювати будь-яку фігуру, не відриваючи олівець від паперу і проводячи кожну лінію лише один раз. Виявляється, що таке завдання не завжди можна вирішити, тобто. існують фігури, які зазначеним способомнамалювати не можна. Питання розв'язання таких завдань також належить до теорії графів. Вперше його досліджував у 1736 році великий німецький математик Леонард Ейлер, вирішуючи завдання про Кенігсберзькі мости. Тому графи, які можна намалювати вказаним способом, називаються графами Ейлера.

Завдання 6. Чи можна намалювати зображений на малюнку граф не відриваючи олівець від паперу і проводячи кожне ребро рівно один раз?

Рішення.Якщо ми малюватимемо граф так, як сказано в умові, то в кожну вершину, крім початкової та кінцевої, ми увійдемо стільки ж разів, скільки вийдемо з неї. Тобто всі вершини графа, крім двох, повинні бути парними. У нашому ж графі є три непарні вершини, тому його не можна намалювати вказаним за умови способом.

Зараз ми довели теорему про Ейлерові графи:

Теорема: Ейлерів граф повинен мати не більше двох непарних вершин

І насамкінець – завдання про Кенігсберзькі мости.

Завдання 7. На малюнку зображено схему мостів міста Кенігсберга.

Чи можна прогулятися так, щоб пройти по кожному мосту рівно 1 раз?

3. Завдання до теми "Графи"

Концепція графа.

1. На квадратній дошці 3x3 розставлено 4 коні так, як показано на рис.1. Чи можна зробивши кілька ходів кіньми, переставити в положення, показане на рис.2?

Рис. 1

Рис. 2

Рішення.Занумеруємо клітини дошки, як показано на малюнку:

Кожній клітині поставимо у відповідність точку на площині і, якщо з однієї клітини можна потрапити до іншої ходом шахового коня, то відповідні точки з'єднаємо лінією. Вихідна та необхідна розстановка коней показана на рисунках:

При будь-якій послідовності ходів конями порядок їхнього слідування, очевидно, змінитися не може. Тому переставити коней необхідним чином неможливо.

2. У країні Цифра є 9 міст з назвами 1, 2, 3, 4, 5, 6, 7, 8, 9. Мандрівник виявив, що два міста з'єднані авіалінією в тому і лише в тому випадку, якщо двозначне число, утворене назвами міст, ділиться на 3. Чи можна долетіти повітрям з міста 1 до міста 9 ?

Рішення.Поставивши у відповідність кожному місту точку і з'єднавши точки лінією, якщо сума цифр ділиться на 3, отримаємо граф, у якому цифри 3, 5, 9 пов'язані між собою, але не пов'язані з рештою. Значить, долетіти з міста 1 до міста 9 не можна.

Ступені вершин та підрахунок числа ребер.

3. У державі 100 міст до кожного міста виходить 4 дороги. Скільки всього доріг у державі.

Рішення.Підрахуємо загальну кількість вихідних міст доріг – 100 . 4 = 400. Однак за такого підрахунку кожна дорога порахована 2 рази – вона виходить з одного міста і входить до іншого. Отже всього доріг вдвічі менше, тобто. 200.

4. У класі 30 осіб. Чи може бути так, що 9 людей мають по 3 друга, 11 – по 4 друга, а 10 – по 5 друзів?

Відповідь.Ні (теорема про парність числа непарних вершин).

5. У короля 19 васалів. Чи може бути так, що у кожного васала 1, 5 чи 9 сусідів?

Відповідь.Ні не може.

6. Чи може в державі, в якій з кожного міста виходить рівно 3 дороги, бути рівно 100 доріг?

Рішення. Підрахуємо кількість міст. Число доріг дорівнює числу міст х, помноженому на 3 (число доріг, що виходять з кожного міста) і поділеному на 2 (див. задачу 3). Тоді 100 = Зх / 2 => Зх = 200, чого не може бути при натуральному х. Отже, 100 доріг у такій державі бути не може.

7. Доведіть, що кількість людей, які коли-небудь жили на Землі і зробили непарне число рукостискань, парне.

Доказ безпосередньо випливає з теореми парності числа непарних вершин графа.

Зв'язність.

8. У країні з кожного міста виходить 100 доріг і з кожного міста можна дістатися будь-якого іншого. Одну дорогу закрили на ремонт. Доведіть, що й тепер із будь-якого міста можна дістатися будь-якого іншого.

Доказ. Розглянемо компоненту зв'язності, куди входить одне із міст, дорогу між якими закрили. По теоремі парності числа непарних вершин до неї входить і друге місто. А значить, як і раніше, можна знайти маршрут і дістатися з одного з цих міст до іншого.

Графи Ейлер.

9. Є група островів, з'єднаних мостами отже кожного острова можна дістатися будь-якого іншого. Турист обійшов всі острови, пройшовши по кожному мосту по-різному 1 раз. На Троєкратному острові він побував тричі. Скільки мостів веде з Троєкратного, якщо турист

а) чи не з нього почав і не на ньому закінчив?
б) із нього почав, але не на ньому закінчив?
в) з нього почав та на ньому закінчив?

10. На малюнку зображено парк, розділений на кілька частин огорожами. Чи можна прогулятися парком та його околицями так, щоб перелізти через кожен паркан по-різному 1 раз?

Графи в інформатиці є способом визначення відносин у сукупності елементів. Це основні об'єкти вивчення

Базові визначення

З чого складається граф у інформатиці? Він включає безліч об'єктів, які називаються вершинами або вузлами, деякі пари яких пов'язані т.з. ребрами. Наприклад, граф на малюнку (а) складається з чотирьох вузлів, позначених А, В, С, 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 – зв'язковий граф. Те саме можна сказати і про більшість комунікаційних та транспортних мереж, тому що їх мета полягає в тому, щоб спрямовувати трафік від одного вузла до іншого.

З іншого боку, немає жодних апріорних підстав очікувати на те, що дані види графів в інформатиці широко поширені. Наприклад, у соціальній мережі неважко уявити двох людей, не пов'язаних між собою.

Компоненти

Якщо графи в інформатиці не пов'язані, вони природним чином розпадаються на набір пов'язаних фрагментів, груп вузлів, які є ізольованими і не перетинаються. Наприклад, на малюнку зображені три такі частини: перша - А і В, друга - C, D і Е, і третя складається з вершин, що залишилися.

Компоненти зв'язності графа є підмножиною вузлів, у яких:

• кожна вершина підгрупи має маршрут до будь-якої іншої;
• підмножина не є частиною більшого набору, в якому кожен вузол має маршрут до будь-якого іншого.

Коли графи в інформатиці поділяються з їхньої компоненти, це є лише початковим способом описи їх структури. В рамках цього компонента може бути багата внутрішня структура, важлива інтерпретації мережі. Наприклад, формальним методом визначення важливості вузла є визначення того, скільки частин розділиться граф, якщо вузол буде прибраний.

Максимальний компонент

Існує метод якісної оцінки компонентів зв'язності. Наприклад, є всесвітня соціальна мережазі зв'язками між двома людьми, якщо вони є друзями.

Чи зв'язкова вона? Мабуть, ні. Зв'язність - досить крихка властивість, і поведінка одного вузла (або невеликого їх набору) може звести її нанівець. Наприклад, одна людина без будь-яких живих друзів буде компонентом, що складається з єдиної вершини, і, отже, граф не буде зв'язковим. Або віддалений тропічний острів, що складається з людей, які не мають жодного контакту із зовнішнім світом, також буде невеликою компонентою мережі, що підтверджує її незв'язність.

Глобальна мережа друзів

Але є ще щось. Наприклад, читач популярної книги має друзів, які виросли в інших країнах, і складає з ними один компонент. Якщо взяти до уваги батьків цих друзів та їхніх друзів, то всі ці люди також перебувають у тому ж компоненті, хоча вони ніколи не чули про читача, розмовляють іншою мовою і поруч із ним ніколи не були. Таким чином, хоча глобальна мережа дружби - не зв'язна, читач входитиме в компонент дуже великого розміру, що проникає у всі частини світу, що включає в себе людей з різних верств і, фактично, що містить значну частину населення земної кулі.

Те саме має місце і в мережевих наборах даних - великі, складні мережічасто мають максимальну компоненту, що включає значну частину всіх вузлів. Більше того, коли мережа містить максимальну компоненту, вона майже завжди лише одна. Щоб зрозуміти, чому, слід повернутись до прикладу з глобальною мережею дружби і спробувати уявити наявність двох максимальних компонентів, кожна з яких включає мільйони людей. Потрібна наявність єдиного ребра від когось із першої компоненти до другої, щоб дві максимальні компоненти злилися в одну. Так як ребро єдине, то в більшості випадків неймовірно, щоб воно не утворилося, і, отже, дві максимальні компоненти в реальних мережах ніколи не спостерігаються.

У деяких рідкісних випадках, коли дві максимальні компоненти співіснували протягом тривалого часу реальної мережі, їхнє об'єднання було несподіваним, драматичним, і, зрештою, мало катастрофічні наслідки.

Катастрофа злиття компонент

Наприклад, після прибуття європейських дослідників у цивілізації Західної півкулі приблизно півтисячоліття тому відбувся глобальний катаклізм. З погляду мережі це виглядало так: п'ять тисяч років глобальна соціальна мережа, ймовірно, складалася з двох гігантських компонентів - однієї в Північній та Південній Америці, а іншої - в Євразії. З цієї причини технології розвивалася незалежно в двох компонентах, і, що ще гірше, так само розвивалися і хвороби людини і т. д. Коли дві компоненти нарешті увійшли в контакт, технології та захворювання однієї швидко і катастрофічно переповнили другу.

Американська середня школа

Поняття максимальних компонент корисне для міркувань про мережі та в менших розмірах. Цікавий прикладє граф, що ілюструє романтичні відносини в американській середній школі за 18-місячний період. Той факт, що він містить максимальну компоненту, має важливе значення, коли мова заходить про поширення захворювань, що передаються статевим шляхом, що було метою проведеного дослідження. Учні, можливо, мали лише одного партнера за цей період часу, але не усвідомлюючи цього, були частиною максимальної компоненти і, отже, частиною багатьох маршрутів потенційної передачі. Ці структури відображають відносини, які, можливо, давно закінчилася, але вони пов'язують індивідуумів у ланцюгах занадто довго, щоб стати предметом пильної уваги та пліток. Проте вони реальні: як соціальні факти це невидимі, але логічно витікаючі макроструктури, що виникли як продукт індивідуального посередництва.

Відстань та пошук завширшки

На додаток до відомостей про те, чи пов'язані два вузли маршрутом, теорія графів в інформатиці дозволяє дізнатися і про його довжину - у транспорті, зв'язку або при поширенні новин та захворювань, а також про те, чи проходить він через кілька вершин чи безліч.

І тому слід визначити довжину маршруту, рівну числу кроків, що він містить від початку остаточно, т. е. число ребер в послідовності, що його становить. Наприклад, маршрут MIT, BBN, RAND, UCLA має довжину 3, а MIT, UTAH - 1. Використовуючи довжину шляху, можна говорити про те, чи розташовані два вузли у графі близько один до одного чи далеко: відстань між двома вершинами визначається як довжина найкоротшого шляху між ними. Наприклад, відстань між LINC і SRI дорівнює 3, хоча, щоб переконатися в цьому, слід переконатися у відсутності довжини, що дорівнює 1 або 2 між ними.

Алгоритм пошуку завширшки

Для невеликих графів відстань між двома вузлами легко підрахувати. Але для складних виникає потреба в систематичному методі визначення відстаней.

Найприроднішим способом це зробити і, отже, найбільш ефективним є наступний (на прикладі глобальної мережідрузів):

• Усі друзі оголошуються такими, що знаходяться на відстані 1.
• Всі друзі друзів (не враховуючи вже зазначених) оголошуються такими, що знаходяться на відстані 2.
• Всі їхні друзі (знову ж таки, крім помічених людей) оголошуються віддаленими на відстань 3.

Продовжуючи в такий спосіб, пошук проводять у наступних шарах, кожен із яких - на одиницю далі попереднього. Кожен новий шар складається з вузлів, які ще не брали участь у попередніх і які входять у ребро з вершиною попереднього шару.

Ця техніка називається пошуком завширшки, тому що вона виконує пошук за графом назовні від початкового вузла, в першу чергу охоплюючи найближчі. На додаток до надання способу визначення відстані, вона може бути корисною концептуальною основою для організації структури графа, а також того, як побудувати граф з інформатики, маючи вершини на підставі їхньої відстані від фіксованої початкової точки.

Пошук завширшки може бути застосований не тільки до мережі друзів, а й до будь-якого графа.

Світ тісний

Якщо повернутися до глобальної мережі друзів, можна побачити, що аргумент, який пояснює приналежність до максимальної компоненти, насправді стверджує щось більше: не тільки читач має маршрути до друзів, що пов'язують його зі значною часткою населення земної кулі, але ці маршрути напрочуд короткі. .

Ця ідея отримала назву "феномена тісного світу": світ здається маленьким, якщо думати про те, який короткий маршрут пов'язує двох людей.

Теорія «шості рукостискань» вперше експериментально досліджувалась Стенлі Мілгремом та його колегами у 1960-і роки. Не маючи якогось набору даних соціальних мереж і з бюджетом 680 доларів він вирішив перевірити популярну ідею. З цією метою він попросив 296 випадково відібраних ініціаторів спробувати надіслати листа біржовому брокеру, який жив у передмісті Бостона. Ініціаторам були надані деякі особисті дані про мету (включаючи адресу та професію), і вони повинні були переслати лист особі, яку вони знали на ім'я, з тими ж інструкціями, щоб вона досягла мети якнайшвидше. Кожен лист пройшов через руки ряду друзів і утворив ланцюжок, що замикався на біржовому брокері поза Бостона.

Серед 64 ланцюжків, що досягли мети, середня довжина дорівнювала шести, що підтвердило число, назване два десятиліття раніше у назві п'єси Джона Гера.

Незважаючи на всі недоліки цього дослідження, експеримент продемонстрував один із найважливіших аспектів нашого розуміння соціальних мереж. У наступні роки з нього було зроблено ширший висновок: соціальні мережі, зазвичай, мають дуже короткі маршрути між довільними парами людей. І навіть якщо такі опосередковані зв'язки з керівниками підприємств та політичними лідерами не окупаються на щоденній основі, існування таких коротких маршрутів відіграє велику роль у швидкості поширення інформації, хвороб та інших видів зараження у суспільстві, а також у можливостях доступу, які соціальна мережа надає людям з абсолютно протилежними властивостями.

Нуль-граф та повний граф.

Існують деякі спеціальні графи, що зустрічаються в багатьох додатках теорії графів. Будемо поки що знову розглядати граф як наочну схему, що ілюструє перебіг спортивних змагань. До початку сезону, поки що жодні ігри не проводилися, на графі немає жодних ребер. Такий граф складається із одних ізольованих вершин, тобто. з вершин, з'єднаних жодними ребрами. Граф такого виду ми називатимемо нуль-графом. На рис. 3 наведені такі графи для випадків, коли число команд, або вершин, дорівнює 1, 2, 3, 4 і 5. Ці нуль-графи зазвичай позначаються символами О1, О2, О3 і т.д., так що Оn-це нуль- граф із n вершинами, що не має ребер.

Розглянемо інший крайній випадок. Припустимо, що після закінчення сезону кожна команда зіграла по одному разу з кожною з залишених команд. Тоді на відповідному графі кожна пара вершин буде з'єднана руба. Такий граф називається повним графом. На рис.4 зображені повні графи з числом вершин n = 1, 2, 3, 4, 5. Ми позначаємо ці повні графи відповідно через U1, U2, Uз, U4 та U5, так що граф Un складається з 11 вершин та ребер, що з'єднують всілякі пари цих вершин. Цей граф можна уявити собі як n-кутник, у якому проведено всі діагоналі.

Маючи деякий граф, наприклад, граф G, зображений на рис. 1, ми завжди можемо перетворити його на повний граф з тими самими вершинами, додавши відсутні ребра (т. е. ребра, відповідні ігор, які тільки ще зіграні). На рис. 5 ми зробили це для рису графа. 1 (ігри, що ще не відбулися, зображені пунктиром). Можна також окремо накреслити граф, відповідний поки що зіграним, майбутнім ігор. Для графа G у своїй вийде граф, зображений на рис. 6.

Цей новий граф називаємо доповненням графа G; прийнято позначати його через G1. Взявши додаток графа G1, ми отримаємо граф G. Ребра обох графів G1 і G разом становлять повний граф.

Формат графічного файлу- це спосіб представлення графічних даних на зовнішньому носії. Розрізняють растрові та векторні форматиграфічних файлів, серед яких, у свою чергу, виділяють універсальні графічні форматиі власні (оригінальні) формати графічних програм.

Універсальні графічні формати «розуміються» усіма програмами, що працюють з растрової (векторної) графікою.

Універсальний растровий графічний формат формат BMP. Графічні файли у цьому форматі мають великий інформаційний обсяг, оскільки у них зберігання інформації про колір кожного пікселя відводиться 24 біта.

У малюнках, збережених в універсальному растровому форматі GIF, можна використовувати лише 256 різних кольорів. Така палітра підходить для простих ілюстрацій та піктограм. Графічні файли цього формату мають невеликий інформаційний обсяг. Це особливо важливо для графіки, яка використовується Всесвітній павутині, користувачам якої бажано, щоб запитана ними інформація з'явилася на екрані якнайшвидше.

Універсальний растровий формат JPEGрозроблений спеціально для ефективного зберігання зображень фотографічної якості. Сучасні комп'ютеризабезпечують відтворення понад 16 мільйонів кольорів, більшість із яких людським оком просто невиразні. Формат JPEG дозволяє відкинути "надлишкове" для людського сприйняття різноманітність кольорів сусідніх пікселів. Частина вихідної інформації при цьому втрачається, але це забезпечує зменшення інформаційного об'єму (стиснення) графічного файлу. Користувачеві надається можливість самому визначати ступінь стиснення файлу. Якщо зображення, що зберігається, — фотографія, яку передбачається роздрукувати на аркуші великого формату, то втрати інформації небажані. Якщо ж це фото - знімок буде розміщений на Web-сторінці, то його можна сміливо стискати в десятки разів: інформації, що залишилася, буде достатньо для відтворення зображення на екрані монітора.

До універсальних векторних графічних форматів відноситься формат WMF, що використовується для зберігання колекції зображень Microsoft.

Універсальний формат EPSдозволяє зберігати інформацію як про растру, так і про векторну графіку. Його часто використовують для імпорту файлів до програм підготовки поліграфічної продукції.

З власними форматами ви познайомитеся безпосередньо у процесі роботи з графічними програмами. Вони забезпечують найкраще співвідношенняякості зображення та інформаційного обсягу файлу, але підтримуються (тобто розпізнаються і відтворюються) тільки самим додатком, що створює файл.

Завдання 1.
Для кодування одного пікселя використовується 3 байти. Фотографію розміром 2048 х 1536 пікселів зберегли як несжатого файла. Визначте розмір файлу, що вийшов.

Рішення:
i = 3 байти
K = 2048 1536
I -?

I=K i
I = 2048 1536 3 = 2 2 10 1,5 2 10 3 = 9 2 20 (байтів) = 9 (Мб).

Відповідь: 9Мб.

Завдання 2.
Нестиснене растрове зображеннярозміром 128 х 128 пікселів займає 2 Кб пам'яті. Якою є максимально можлива кількість кольорів на панелі зображення?

Рішення:
K = 128128
I = 2 Кб
N -?

I=K i
i=I/K
N=2 i
i = (2 1024 8)/(128 128) = (2 2 10 2 3) /(2 7 2 7) = 2 1+10+3 /2 7+7 = 2 14 /2 14 = 1 (біт) .
N = 2 1 = 2.

Відповідь: 2 кольори - чорний і білий.

Найголовніше:

• Формат графічного файлу - це спосіб представлення графічних даних на зовнішньому носії. Розрізняють растрові та векторні формати графічних файлів, серед яких, у свою чергу, виділяють універсальні графічні формати та власні формати графічних додатків.

IPad