В настоящее время для многих девятиклассников актуальна тема ОГЭ. В нем можно встретить задачи, которые на первый взгляд кажутся сложными, но на самом деле решаются легко. В математике существует целый раздел – теория графов, который изучает графы, их свойства и применение. Графы нашли применение практически во всех отраслях научных знаний: математике, физике, биологии, химии, истории, лингвистике, технике и т.п. Самое распространенное применение теории графов нашла в математике при решении логических задач и головоломок. И в этой статье я разберу как с помощью данной темы можно решить задачи из ОГЭ и ЕГЭ.
Рассмотрим только самые основные понятия в теории графов.
Теория графов — обширный раздел дискретной математики, в котором системно изучают свойства графов.
Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.
Путем или цепью в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.
Циклом называют путь, в котором первая и последняя вершины совпадают.
Путь или цикл называют простым, если ребра в нем не повторяются.
Граф называется связным, если между любыми двумя его вершинами есть путь. Если граф несвязный, то его можно разбить на несколько частей (подграфов), каждая из которых будет связной. Такие части называются компонентами связности. Возможно, что некоторые компоненты связности будут состоять всего лишь из одной вершины.
Основой применения графов для решения логических задач служит выявление и последовательное исключение возможностей, заданных в условии. Возьмем, к примеру, такую задачу: «На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому».
Решение: Вершины графа – это деревья, обозначенный первой буквой названия дерева. Рассмотрим отношение дерево ниже чем другое и проведем стрелки о более низкого дерева к более высокому. Если в задаче сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине и т.д. Получаем граф, на котором видно, что самое низкое дерево - клён, затем идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь.
Теория графов в медицине. Каждому человеку важно знать свою группу крови и резус-фактор. Всего существует четыре группы крови. При переливании крови от одного человека к другому не все группы совместимы. Оказывается, с помощью графа можно наглядно показать возможные варианты переливания крови. Группы крови – это вершины графа с соответствующими номерами, а стрелки указывают на возможность переливания одной группы крови человеку с другой группой крови. Например, кровь первой группы можно переливать любому человеку, а человек с первой группой крови воспринимает только кровь своей группы.
В ОГЭ по математике задачу № 21 можно решить с помощью теории графов.
Задача: Два автомобиля одновременно отправляются в 800-километровый пробег. Первый едет со скоростью на 36 км/ч больше, чем второй, и прибывает к финишу на 5 ч раньше второго. Найдите скорость первого автомобиля.
Решение:
Составим граф, на котором будут отображены данные задачи, обозначив переменной х неизвестную величину – скорость 1 автомобиля:
Так как мы обозначили за х скорость 1 авто, значит скорость 2 авто будет на 36 км/ч меньше.
Расстояние у каждого авто будет 800 км.
Для нахождения времени надо расстояние разделить на скорость, поэтому мы получили дроби с переменной в знаменателе.
Зная, что первый прибывает к финишу на 5 ч раньше второго, составим и решим уравнение:
Приведем к общему знаменателю х(х-36) наше уравнение и решим его:
Разделим на 5 каждый коэффициент:
Решим полученное квадратное уравнение
Отсюда х1=96, а х2 не удовлетворяет условию задачи, так как оно отрицательное, а скорость не может быть выражена отрицательным числом.
Значит, скорость первого автомобиля 36 км/ч
Ответ: 36
Так же можно применить теорию графов в решении задач из ОГЭ по информатике. Вот разбор задачи №9
Задача: На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К, проходящих через город В?
Решение:
Поскольку нас интересуют пути, проходящие через город В, то вычеркнем те дороги, которые минуют город В:
Как видим, таких дорог получилось две — Б->Д и А->Г. Учтем это при дальнейших расчетах.
Количество путей из города А в город К, проходящих через город В, равно произведению количества путей из города А в город В и количества путей из города В в город К.
Найдем количество путей из города А в город В:
А = 1
Б = А = 1
В = А + Б = 2
Найдем количество путей из города В в город К (при этом В - исходный пункт):
В = 1
Г = В = 1
Ж = В + Г =1 + 1 = 2
Д = В = 1
Е = В + Д = 1 + 1 = 2
К = Д + Е + Ж = 1 + 2 + 2 = 5
Тогда количество путей из города А в город К, проходящих через город В, равно 2 · 5 = 10.
Ответ: 10.
Подробнее с разбором данных задачи можно ознакомиться в моем видео-уроке: https://youtu.be/aOyuwgS2KKA
В данной статье мы посмотрели решение задач с помощью графов, изучили новые понятия и разобрались как можно применить теорию графов в решении задач ОГЭ по математике и информатике.