Условие задания:
1 Б.
Можно решать задачи графическим способом — с помощью графов.
Что такое граф?
Граф представляет собой структуру, состоящую из вершин и рёбер.
Точки на рисунках обозначают вершины, а отрезки, которые их соединяют, — рёбра.
Рис. \(1\). Граф
Примеры графов существуют в реальной жизни, например:
схема метро, где вершины — это станции, а рёбра — это ветки метро.
Сеть компьютеров в офисе или университете, где вершины — компьютеры, а рёбра — сетевые соединения между ними.
Граф авиарейсов, где вершины — аэропорты, а рёбра — рейсы между ними.
Виды графов
Графы бывают ориентированными и неориентированными.
Пример неориентированного графа изображён на рис. \(2\), где представляется, как пять подруг пишут сообщения друг другу в социальной сети. По линиям (рёбрам) в таком графе можно перемещаться в обоих направлениях.
Рис. \(2\). Неориентированный граф
В ориентированном графе по каждому ребру можно пройти только в одну сторону, и в таком случае рёбра обозначаются стрелками. То есть в данном графе можно проследить последовательность обмена сообщениями между девочками.
Рис. \(3\). Ориентированный граф
Граф, в котором вершины или рёбра обладают дополнительной информацией (весом вершины или ребра), называется взвешенным.
На рис. \(4\) представлена информация о городах с помощью взвешенного графа, где вершины — названия городов и годы их основания, а рёбра — расстояния между городами.
Рис. \(4\). Взвешенный граф
Граф иерархической системы называется деревом. Особенность его в том, что между его вершинами существует только один путь — от высшего к низшему.
Рис. \(5\). Граф иерархической структуры (дерево)
Задача
Артём, Богдан, Владислав, Галина, Денис и Екатерина участвовали в соревнованиях по шахматам. Каждый участник должен сыграть только по одной партии друг с другом.
На данный момент уже известны некоторые сыгранные партии:
1. Артём сыграл с Богданом, Галиной и Екатериной.
2. Богдан — с Артёмом, Галиной.
3. Владислав — с Галиной, Денисом.
4. Екатерина — с Артёмом и Владиславом.
1. Артём сыграл с Богданом, Галиной и Екатериной.
2. Богдан — с Артёмом, Галиной.
3. Владислав — с Галиной, Денисом.
4. Екатерина — с Артёмом и Владиславом.
Сколько игр проведено и сколько осталось провести?
Решение
Для начала изобразим точки с первыми буквами имён участников и отметим сыгранные партии, которые известны по условию:
Рис. \(6\). Сыгранные партии участников
Получается, что уже сыграно \(7\) партий.
Далее соединим между собой точки с первыми буквами имён тех ребят, которые ещё не играли партии, и выделим их зелёным цветом.
Рис. \(7\). Несыгранные партии участников
Получилось \(8\) отрезков зелёного цвета. Следовательно, осталось провести ещё \(8\) игр.
Чтобы найти количество рёбер в графе, необходимо воспользоваться формулой (где \(n\) — количество вершин в графе):
.
Рассчитай количество рёбер в графе, если количество вершин равно 14.
Ответ: .
Источники:
Рис. 1. Граф. © ЯКласс.
Рис. 2. Неориентированный граф. © ЯКласс.
Рис. 3. Ориентированный граф. © ЯКласс.
Рис. 4. Взвешенный граф. © ЯКласс.
Рис. 5. Граф иерархической структуры (дерево). © ЯКласс.
Рис. 6. Сыгранные партии участников. © ЯКласс.
Рис. 7. Несыгранные партии участников. © ЯКласс.
Рис. 2. Неориентированный граф. © ЯКласс.
Рис. 3. Ориентированный граф. © ЯКласс.
Рис. 4. Взвешенный граф. © ЯКласс.
Рис. 5. Граф иерархической структуры (дерево). © ЯКласс.
Рис. 6. Сыгранные партии участников. © ЯКласс.
Рис. 7. Несыгранные партии участников. © ЯКласс.
Вы должны авторизоваться, чтобы ответить на задание. Пожалуйста, войдите в свой профиль на сайте или зарегистрируйтесь.
Вход
или
Регистрация