Как решать математические задачи на логику с помощью построения графа?

Метод графов используют для решения логических задач, в которых даны отношения между предметами. school-science.ru

Граф в этом случае представляет собой несколько точек, часть из которых соединены друг с другом отрезками или стрелками. school-science.ru

Пример решения задачи: school-science.ru

> Жила-была одна дружная семья: мама, папа и сын. school-science.ru Они все любили делать вместе, но мультфильмы любили разные: «Ну, погоди!», «Покемоны», «Том и Джерри». school-science.ru Определите, какой мультфильм любит каждый из них, если мама, папа и любитель мультфильма «Покемоны» никогда не унывают, а папа и любитель мультфильма «Том и Джерри» делают зарядку по утрам. school-science.ru

Решение: school-science.ru

1. Рассмотрим множество людей: мама, папа, сын и множество мультфильмов «Ну, погоди!», «Покемоны», «Том и Джерри». school-science.ru
2. Обозначим элементы этих двух множеств точками. school-science.ru
3. Если точке из одного множества соответствует точка другого множества, будем соединять эти точки сплошной линией, если не соответствует — то штриховой. school-science.ru
4. Заметим, что по условию задачи у человека только один любимый мультфильм. school-science.ru Поэтому нужно найти единственно возможное соответствие между элементами двух множеств. school-science.ru
5. Правило: если какая-то точка оказывается соединённой с двумя точками другого множества штриховыми линиями, то с третьей точкой она должна быть соединена сплошной. school-science.ru
6. Теперь установлено, что папа любит мультфильм «Ну, погоди!», сын — «Покемоны». school-science.ru В обеих множествах остаётся только по одной точке, следовательно, мама любит мультфильм «Том и Джерри». school-science.ru Задача решена. school-science.ru

В результате решения на графе должна остаться только одна линия каждого типа и из каждой вершины должна выходить только одна линия. in.lit.msu.ru