Графы. графы. Решение логических задач с помощью графов
 Скачать 1.09 Mb.
|
|
Решение логических задач с помощью графов. Чем невозможнее кажется задача, тем интереснее её решать. Г Р А Ф И О Граф??? Графы – это рисунки, которые состоят из точек и линий, соединяющих эти точки. Каждая пара точек в графе может быть соединена линиями. Линия указывает на связь между двумя точками. Основные понятия Точки называются вершинами графа, а линиями рёбрами. Ребро может иметь направление, которое указывается стрелочкой. У графа обязательно есть вершины. Граф без рёбер называется пустым. Основные понятия Основные понятияНаправленная линия (со стрелкой) называется дуга. Линия ненаправленная (без стрелки) называется ребро. Линия, выходящая из некоторой вершины и входящая в неё же, называется петля. дуга ребро петля А В С А,В,С – вершины графа Степень вершины графа - это количество ребер, выходящих из данной вершиныA B C D Степень A – 1 Степень B – 3 Степень C – 2 Степень D – 2 Основные понятия Количество рёбер графа – равно сумме степеней всех его вершин, делённой на 2.A B C D E F (1+3+2+3+2+1):2=6 Основные понятия Неориентированный граф На схеме представлены дружеские связи в компании. Отношения являются двухсторонним, поэтому вершины соединены линиями без стрелок. Маша Юра Коля Витя Аня Граф называется неориентированным, если его вершины соединены ребрами. Какие бывают графы? Ориентированный граф Маша Юра Коля Витя Аня Ориентированный граф - граф, вершины которого соединены дугами. С помощью таких графов могут быть представлены схемы односторонних отношений. На рисунке представлена схема переписки Какие бывают графы? Связные и несвязные графыСвязный граф можно нарисовать не отрывая карандаша от бумаги Какие бывают графы? Полный графГраф называется полным, если каждая вершина связана со всеми другими вершинами графа.Если полный граф имеет n вершин, то количество ребер будет равноКакие бывают графы? Дерево Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель. компьютер суперкомпьютер рабочая станция персональный компьютер настольный портативный карманный Какие бывают графы? Коля Маша Юра Витя Аня Цепь – путь по вершинам и ребрам, включающий любое ребро графа не более одного раза. Цикл – цепь, начальная и конечная вершины которой совпадают. Граф с циклом называют сетью Сеть Какие бывают графы? Основоположники теории графов.Л. Эйлер (1707-1782), российский математик, швейцарец по происхождению, академик Петербургской и Берлинской академии наук) Г. Кирхгоф (1824-1871), иностранный член-корреспондент Петербургской академии наук разработал теорию деревьев) Проблема Кёнигсбергских мостовВ 1736 году Эйлер нашел решение головоломки, носящей название «проблема Кёнигсбергских мостов». Задача, для решения которой Эйлер впервые применил графы, - это задача о мостах Кенигсберга. В XVIII веке город Кенигсберг (сейчас Калининград) был расположен на берегах реки и двух островах. Различные части города были соединены семью мостами. Можно ли совершить прогулку, пройдя по каждому мосту ровно один раз? Задача Эйлера План города Эйлер заменил его упрощенной схемой, на которой части города изображены точками (вершинами), а мосты - линиями (ребрами). Задача Эйлера Получился следующий граф:Задача Эйлера В итоге Эйлер доказал общее утверждение: для того чтобы обойти все рёбра графа по одному разу и вернуться в исходную вершину, необходимо и достаточно выполнения следующих двух условий: 1. из любой вершины графа должен существовать путь по его рёбрам в любую другую вершину (граф должен быть связным); 2. из каждой вершины должно выходить чётное количество рёбер. Если отбросить условие возвращения в исходную вершину, то можно допустить наличие двух вершин, из которых выходит нечётное количество рёбер. В этом случае начинать движение следует с одной из этих двух вершин, а заканчивать - в другой. Задача Эйлера Граф кёнигсбергских мостов имел четыре нечётные вершины, следовательно невозможно пройти по всем мостам, не проходя ни по одному из них дважды. Решение задачи о Кёнигсбергских мостах Графы в современном мире Медицина
Науки, опирающиеся на знание теории графов: В государстве 100 городов, а из каждого города выходит 4 дороги. Сколько всего дорог в государстве?Решение логических задач с помощью графов № 1 Решение: Воспользуемся формулой: количество рёбер в графе равно сумме степеней его вершин, делённой на 2. (100 ∙ 4) : 2 = 200 . Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?Нет, не может, так как если X- число городов Решение: Воспользуемся формулой: количество рёбер в графе равно сумме степеней его вершин, делённой на 2. Решение логических задач с помощью графов № 2 Сколько всего рукопожатий было сделано?Решение логических задач с помощью графов № 3 Решение:Пусть каждому из молодых людей соответствует точка на плоскости, а произведенные рукопожатия – отрезок, который будет соединять точки.Количество ребер полного графа (5 ∙ 4) : 2=10. Значит, было сделано 10 рукопожатий Решение логических задач с помощью графов
Решение логических задач с помощью графов № 4 Изобразим все данные условия на рисунке с помощью графов и ответ станет очевиднымАлексей Борис Геннадий Виталий строитель тренер журналист врач Решение логических задач с помощью графов Алексей, Борис, Виталий и Геннадий – друзья. Один из них –врач, другой – журналист, третий – тренер спортивной школы, четвертый – строитель. Журналист написал статьи об Алексее и Геннадии. Тренер и журналист вместе с Борисом ходили в поход. Алексей и Борис были на приеме у врача. У кого какая профессия? Устный счёт. Сколько всего было рукопожатий? Каждый из 8-ми участников раздал по 7 значков. Значит всего значков 8·7 = 56. А рукопожатий было в 2 раза меньше чем значков, т.е. 28, так как рукопожатие одно на двоих. Физкультура. Задача № 3. На шахматном турнире встретились 8 участников. Перед игрой они друг друга поприветствовали и обменялись значками. Сколько всего было значков? Решение: А теперь решим такую задачу: Сколько мальчиков приехало на турнир по шахматам, если всего было 10 рукопожатий? Будем решать эту задачу графически. Точками будем изображать мальчиков, а отрезок будет обозначать рукопожатие. 2 4 1 3 5 Данная схема является графом. Решение задач с помощью графов. Задача №5. Андрей, Борис, Виктор, Галина, Дмитрий и Елена участвуют в соревнованиях по теннису: Андрей сыграл с Борисом, Галиной и Еленой; Борис, как уже говорилось, с Андреем и еще с Галиной; Виктор – с Галиной, Дмитрием и Еленой; Галина – с Андреем и Виктором. 1. Сколько игр проведено? 2. Сколько еще осталось игр, если каждый играет с каждым только 1 раз? Решение: А Б В Г Д Е А Б В Г Д Е 1 2 Проведено 7 игр. Осталось 8 игр. Задача №6 . Сколько нужно конвертов, чтобы каждая из девочек Оля (О), Лена (Л), Наташа (Н) и Маша (М) обменялись с каждой из них письмами? Решение: О Л Н М Нужно 12 конвертов. Решение задач с помощью графов. Решение задач с помощью графов. Задача №7. У Саши 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами он может выбрать конверт и марку, чтобы отправить письмо? Решение: О А П К Т П К Т Письмо Конверт Марка Всего 6 способов. Самостоятельное решение задач. Задача №8 Задача №9 Задача №10 Сколько можно составить всевозможных двухзначных кодов из 3-ёх цифр: 5,7,4, при условии, что цифры не повторяются? В соревнованиях участвовали 3 спортсменки и в конце соревнований каждая из них обменялась с каждой бейсболками. Сколько всего бейсболок участвовало в обмене? На борту космического корабля три пилота и два инженера. Сколькими способами можно составить экипаж разведывательно- го катера из одного пилота и одного инженера. Самостоятельное решение задач. Задача № 8 Решение: Код 1-я цифра 2-я цифра 5 7 4 7 4 5 5 7 4 Всего 6 кодов. 1. способ. 2 способ. 5 7 4 Задача №9. Решение 1. способ. 2 способ. Экипаж Пилоты Инженеры Инженеры Пилоты Самостоятельное решение задач. Всего 6 экипажей. Самостоятельное решение задач. Решение: 1 2 3 Всего 6 бейсболок. Задача №10 Решение задачи методом соответствий. В отделении банка работают кассир (К), охранник (О) и заведующий(З). Их фамилии Борисов(Б), Иванов(И) и Сидоров(С). Кассир не имеет ни братьев, ни сестёр и меньше всех ростом. Сидоров женат на сестре Борисова и ростом выше охранника. Назовите фамилии охранника и заведующего. Задача №11 Решение: отрицание подтверждение К О З Б И С Белов- охранник, Иванов- кассир, Сидоров- заведующий. Исторический фактС помощью графов можно определить, как фразы одного писателя или поэта отличаются от других. На язык деревьев переводятся трудноуловимые особенности стиля. На основании этих графов можно определить автора текста. Например, основная черта стихов А.С. Пушкина – ритмичность и лаконизм (краткость) выражений, а у М.Ю. Лермонтова поэзия более цветистая, фразы более длинные. Теория графов и анализ художественного текста |