поняття графа
Поняття графа.
Припустимо, що футбольна команда вашої школи бере участь в змаганнях і грає з командами інших шкіл. Нехай загальне число команд дорівнює шести. Вашу команду позначимо літерою А, а інші команди - буквами B, C, D, E і F. Через кілька тижнів після початку змагань виявиться, що ні-які з команд вже зіграли один з одним, наприклад:
A з C, D, F;
B c C, E, F;
З з A, B;
D з A, E, F;
E з B, D, F;
F з A, B, D.
Це можна зобразити за допомогою такої геометричної схеми. Кожну команду представимо точкою або маленьким кружечком і з'єднаємо відрізком ті пари точок, які відповідають командам, вже грав один з одним. Тоді для даного списку проведених ігор ми отримаємо схему, зображену на рис. 5.
Схема такого виду називається графом. Вона складається з декількох точок А, В, С, D, E, F, званих вершинами. і декількох з'єднують ці точки відрізків, таких, як АС або ЕВ, званих ребрами графа.
Отже, фігуру, утворену набором точок і відрізків, що з'єднують деякі з цих точок, називається графом. Точки називаються вершинами графа. А відрізки - ребрами графа.
Прикладами графів можуть служити схеми метрополітену, залізничних і шосейних доріг, плани виставок і т.д. За допомогою графів вказуються різні зв'язки між об'єктами.
З рис. 5 видно, що точки перетину деяких ребер графа можуть не бути його вершинами; це відбувається тому, що ми зобразили наш граф на площині. Можливо, зручніше було б уявляти собі його ребра нитками, що проходять один над одним у просторі; у всякому разі, при зображенні на площині вершини графа щоб уникнути плутанини повинні відзначатися достатньо чітко (наприклад, кружечками).
Один і той же граф може виглядати на малюнках по-різному. Наприклад, на трьох малюнку 6 (а), (б), (в), мало схожих один на одного, зображений один і той же граф. Три цих графа мають однакове число вершин, і відповідні вершини графів з'єднані ребрами.
Завдання 1.1. Розглянемо наступні малюнки. Зображують вони один і той же граф?
А)
1. Перевіримо число вершин на графах.
У першому графі три вершини, а в другому чотири, отже, графи різні.
B)
1. Перевіримо число вершин на графах.
У першому і в другому графі по чотири вершини.
2. Перевіримо, чи пов'язані ребрами відповідні вершини графа.
Вершина А в першому графі з'єднана тільки з вершиною В. А в другому графі вершина А з'єднана ще і з вершиною D. Отже графи різні.
Завдання 1.2. Аркадій, Борис, Сміла, Григорій і Дмитро при зустрічі обмінялися рукостисканнями (кожен потиснув руку кожному по одному разу). Скільки всього рукостискань було зроблено?
Рішення:
Нехай кожному з п'яти молодих людей відповідає певна точка на площині, названа першою літерою його імені, а виробленому рукостисканню - відрізок або частина кривої, що з'єднує конкретні точки - імена.
Розглянемо процес з'єднання точок А, Б, В, Г, Д ребрами.
1. Ситуація, відповідна моменту, коли рукостискання ще не здійснювалися, являє собою точкову схему, зображену на рис 3. Таку схему називають нульовим графом.
Рис 9. Рис 10.
2. Ситуація, відповідна моменту, коли здійснені ще не все рукостискання, може схематично бути зображена, наприклад, за допомогою рис. 10.
Графи, в яких побудовані не всі можливі ребра, називаються неповними графами.
3. На рис. 9 Борис не зробив жодного рукостискання. Вершини, які не належать жодному ребру, називаються ізольованими.
Тепер ми можемо тать чітке визначення нульового графу. Схема, що складається з «ізольованих» вершин, називається нульовим графом.
4. Ситуація, коли здійснилися всі рукостискання, зображена на рис. 11. У ньому кожна з вершин з'єднана з кожної з решти. Цей граф називається повним графом.
Рис 11.
Якщо ми підрахуємо число ребер графа, зображеного на рис. 11, то це число і буде дорівнює кількості скоєних рукостискань між п'ятьма молодими людьми. Їх 10.
Зауважимо, що граф, який не є повним, можна доповнити до повного з тими ж вершинами, додавши відсутні ребра. Так на рис. 10 зображений неповний граф з п'ятьма вершинами. А на рис. 11 граф перетворений в повний. Ребра, що перетворюють граф в повний зображені фіолетовим кольором. Сукупність вершин графа з цими ребрами називається доповненням графа.
Пропозиція 1.Докажем, що якщо повний граф імеетnвершін, то кількість ребер дорівнюватиме:.
Дійсно, все вершин n штук, кожна з'єднана з n-1 вершиною - отримуємо твір n (n-1). Але ми порахували кожне ребро два рази, значить, треба твір розділити на два, і тоді отримаємо шукану формулу для знаходження кількості ребер.
Завдання 1.3. Чи існує повний граф з сімома ребрами?
Рішення. Припустимо, що такий граф існує.
Знаючи кількість ребер, дізнаємося кількість вершин.
= 7; n (n-1) = 14.
Зауважимо, що n і (n-1) - це два послідовних натуральних числа. Число 14 не6льзя представити у вигляді добутку двох послідовних натуральних чисел, значить, дане рівняння не має рішень. Отже, такого графа не існує.