�Метод графів
УРОК 25
Графи
Одним із видів математичних моделей, що допомагають розв’язувати певні види прикладних задач є графи.
У вигляді графів подають схему метропо-літену, схеми шосейних та залізничних доріг, плани виставок, структурні формули молекул, тобто схеми, що показують зв’язок між об’єктами без зазначення масштабу.
Графи
Граф — це фігура, що складається з точок і ліній, які з’єднують деякі із заданих точок. Зазвичай, позначають граф буквою Г. Точки графа називають вершинами, а лінії — ребрами.
Графи
Прикладами графів є такі фігури:
Графи
При зображенні графів на рисунках або схемах визначальним є кількість вершин і ребер, а не їх розташування і вид. Ребра можуть бути прямолінійними або криволінійними, а їх довжини — довільними. Тож три перші фігури зображують один і той самий граф.
Графи
Графи
Четверта фігура зображує інший граф, оскільки має на два ребра більше.
Не завжди точка перетину ребер є вершиною графа.
Наприклад, для останнього графа точка перетину діагоналей не є його вершиною.
Графи
Вершини в графі характеризуються тим, якій кількості ребер вони належать.
Степінь вершини — це число ребер графа, яким належить ця вершина.
Вершина називається непарною, якщо її степінь — число непарне.
Вершина називається парною, якщо її степінь — число парне.
Графи
Вершини, які не належать жодному ребру називають ізольованими.
Наприклад, вершина Р є ізольованою, вершини А і С — парними, а вершини В і К — непарними.
Графи
Залежно від того, чи містить граф ізольовані точки, усі графи поділяються на зв’язні та незв’язні.
Зв’язний граф — із будь-якої вершини якого по ребрах можна потрапити в будь-яку іншу вершину.
Графи
Деякі графи можна побудувати не відриваючи руки. Але які саме? Ознаки графів, які можна побудувати саме так:
1) Якщо всі вершини графа парні (починати можна з довільного місця).
2) Якщо граф має лише 2 непарні вершини (починати треба з однієї, а закінчити в другій).
Графи
Відкритий конверт можна намалювати не відриваючи руки, бо він має дві непарні вершини. Починати треба в одній з них. Спробуй це зробити.
Вправи
Завдання 1. Намалюйте у зошиті граф, який має:
а) три вершини і два ребра;
б) чотири вершини і чотири ребра;
в) чотири вершини і шість ребер.
Завдання 2. Подумайте і намалюйте зв'язний і незв'язний графи.
Вправи
Завдання 3. Визначте, чи можна побудувати граф, у якого:
а) одна вершина степеня 3 і три - степеня 1;
б) одна вершина степеня 2 і три - степеня 1;
в) п'ять вершин степеня 7 і дві - степеня 6;
г) три вершини степеня 5, п'ять вершин степеня 7 і сім вершин степеня 3.
Вправи
Завдання 4. Визначте для зображених графів степені його вершин.
Вправи
Завдання 5. У магазині посуду на прилавку стоять тарілки. Є скляні, є пластмасові, є глиняні. Всі глиняні тарілки розписані вручну, пластмасові можуть бути кольоровими або білими, скляні тарілки однотонні або прозорі. Зобразіть це за допомогою графа.
Вправи
Завдання 6. Для поздоровлень на пошті є конверти трьох видів, на які клеїться одна з двох видів марок, в які вкладається одна з чотирьох листівок. Скільки існує різних способів оформити привітання?
Вправи
Завдання 7. Розв'яжіть задачу про Кенігсберзькі мости: "У Кенігсберзі ріка омиває два острови, через які перекинуто сім мостів. Чи можна обійти всі ці мости, не проходячи двічі по одному й тому самому мосту?"
Вправи
Завдання 8. У змаганнях з волейболу, де не буває нічиїх, беруть участь 5 команд. Команда, що посіла перше місце, виграла всі зустрічі. По дві перемоги здобули лише команди, що посіли 2-ге та 3-тє місця. Якщо кількість перемог однакова, то першість визначається за результатом зустрічі між командами, які здобули однакову кількість перемог. Скільки перемог здобула команда, яка посіла останнє місце? Визначте, хто у кого виграв.