Орієнтовані графи й задачі, що розв'язуються графами
Читай орієнтовані графи, рахуй рукостискання та ігри в турнірі й знаходь найкоротший маршрут, перетворивши задачу на граф.
📖 Почніть тут: читайте кроки «Уроку» по порядку (1, 2, 3 …) і відповідайте на кожне запитання. Потім переходьте до «Практики».
- Росія: 7 клас
Поради для дорослих
Граф — зручна модель: вершини — це люди, міста чи команди, а ребра — зв'язки між ними (дружба, дороги, матчі). Якщо зв'язок має напрям («A обігнав B»), ребро малюють зі стрілкою: це орієнтований граф. Тоді в кожної вершини є певна кількість вихідних і вхідних стрілок.
Класичні задачі: рукостискання в групі з n людей (кожен з кожним по одному разу), матчі в турнірі (кожна команда грає з кожною іншою). Сума степенів удвічі більша за кількість ребер, тож ребер — половина суми степенів; для n вершин, з'єднаних усіма можливими ребрами, дістаємо n·(n − 1) : 2.
Типова помилка — рахувати кожне ребро двічі. Інша — плутати вихідні та вхідні стрілки. Задачу про маршрут розв'язують, підрахувавши ребра найкоротшого ланцюга. У шкільній програмі України теорія графів окремо не вивчається: це розширення теми про комбінаторні задачі та логічні міркування.