Что такое графы в математике 5 класс
Открытый урок математики по теме «Графы вокруг нас». 5-й класс
Разделы: Математика
Класс: 5
Цели урока:
Оборудование: проектор, экран, раздаточный материал (Приложение 1), презентация (Приложение 2)
Ход урока
1. Организационный момент
Сегодня мы познакомимся с математическим понятием «граф»; рассмотрим примеры использования графов в различных областях знаний; задачи по теории графов. Работа на уроке будет проходить в группах. Надеюсь, что наша работа будет продуктивной.
2. Этап усвоения новых знаний
1. Рассмотрим задачу. В первенстве класса по настольному теннису 6 участников: Артем, Булат, Влад Батыршин, Глеб, Дмитрий и Ермошин Влад. Первенство проводится по круговой системе– каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Артем сыграл с Булатом, Глебом и Ермошиным; Булат, как уже говорилось, с Артемом и еще с Глебом; Влад – с Глебом, Дмитрием и Ермошиным; Глеб – с Артемом и Булатом; Дмитрий – с Владом и Ермошин – с Артемом и Владом. Сколько игр проведено к настоящему моменту и сколько еще осталось?
Решение демонстрируется на доске. Изобразим данные задачи в виде схемы. Участников будем изображать точками: Андрея – точкой А, Бориса – точкой Б и т.д. Если двое участником уже сыграли между собой, то будем соединять изображающие их точки отрезками. Получается схема, которая называется графом.
2. Определение. Графом называют конечное множество точек, которые соединены отрезками прямых. Точки называются вершинами графа, а отрезки – ребрами графа.
Прежде всего стоит сказать о том, что графы, о которых пойдет речь, к аристократам былых времен никакого отношения не имеют. Наши «графы» имеют корнем греческое слово «графо», что значит «пишу». Тот же корень в словах «график», «биография», «голография», география.
Точки А, Б, В, Г, Д, Е называются вершинами графа, соединяющие их отрезки – ребрами графа.
Число игр, проведенных к настоящему моменту, равно числу ребер, т.е. 7. Чтобы найти число игр, которые осталось провести, построим еще один граф с теми же вершинами, но ребрами будем соединять тех участников, которые еще не играли друг с другом. Ребер у этого графа осталось 8. Значит, осталось провести 8 игр.
Сейчас почти в любой отрасли науки и техники встречаешься с графами.
Придумайте свои примеры графов.
В качестве примеров ученики могут привести следующие примеры: схемы железных и автомобильных дорог, тепло– и электросети, дерево каталогов, планы выставок и другие.
Графы широко используются в современной математике и программировании. С теорией графов связаны не только математические головоломки, но и такие серьезные науки, как теория отношений и теория групп. Графы находят все новые приложения в теории планирования и управления, теории расписаний, социологии, математической лингвистике, биологии и медицине.
Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез, это сравнительно молодая наука: во времена Ньютона такой науки еще не было, хотя и были «генеалогические деревья», представляющие собой разновидности графов.
3. Этап закрепления новых знаний
1. Рассмотрим задачу: 5 друзей при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Обменяйтесь, пожалуйста, рукопожатиями. Сколько всего рукопожатий было сделано?
Решение демонстрируется на доске. Задача легко решается с помощью теории графов.
Изобразите в тетради 5 точек: А, Б, В, Г, Д.
Сколько всего рукопожатий было сделано?
К решению можно прийти чисто логически. Но графы придали наглядность, упростили решение.
2. Хочу предложить вам решить задачу – загадку. Перед вами граф – «распечатанное письмо». Попробуйте начертить этот граф не отрывая карандаша от бумаги и не проводя по одной линии дважды.
Тот, у кого получилось, может выйти к доске и записать маршрут обхода.
В какой вершине вы начали движение? В какой закончили? (Начала в А, закончила в Е)
Есть другие варианты? (Да, я начал в Е, закончил в А)
Не расстраивайтесь. Мы сейчас с вами выведем алгоритм для решения этой задачи. Для этого нам нужно будет перенестись на более чем 200 лет назад и оказаться вместе с великим математиком Леонардом Эйлером в городе Кенигсберге (сейчас этот город называется Калининград).
На доске портрет Леонарда Эйлера. Что вы знаете о Леонарде Эйлере?
3. Историческая справка (сообщение ученика)
Леонард Эйлер (1707-1783) – математик, механик, физик и астроном. Ученый необычайной широты интересов. Автор свыше 800 работ по математическому анализу, дифференциальной геометрии, теории чисел, приближенным вычислениям, небесной механике, математической физике, оптике, баллистике, кораблестроению, теории музыки и других, оказавших значительное влияние на развитие науки. Леонард Эйлер по происхождению швейцарец. В 1726г. был приглашен работать в Петербург, в 1727г. переехал жить в Россию. Являлся академиком, а затем почетным членом Петербургской академии наук.
Первая работа по теории графов принадлежит именно ему (1736), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. В начале 20 века наряду с термином «граф» употреблялись другие термины, например карта, комплекс, диаграмма, сеть, лабиринт.
4. Задача о Кёнигсбергских мостах.
Бывший Кёнигсберг расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Жители города предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причем на каждом мосту следовало побывать только один раз. До Эйлера никто не мог этого сделать, но и доказать, что это невозможно, тоже ни у кого не получалось. Как поступил Эйлер?
Попробуйте найти нужный ответ и выдвиньте свою гипотезу. Через 3 минуты слушаем гипотезы.
Прогуляться по городским мостам предложили и Эйлеру. После безуспешной попытки совершить нужный обход он начертил упрощенную схему мостов. Получился граф, вершины которого – части города, разделенные рекой, а ребра – мосты.
Леонард Эйлер сформулировал правило:
Обход возможен:
Обход невозможен если нечетных вершин больше 2.
Во время прогулки по городу нельзя пройти по всем семи мостам, проходя по каждому только один раз.
5. Давайте вернемся к задаче «распечатанное письмо» и применим правило Эйлера.
– Сколько ребер сходится в каждой вершине? (В вершине А сходится 3 ребра, в вершине В-4, в вершине С-2, в вершине Д-4.)
– Что вы скажите о четности вершин в этом графе? ( Три вершины – четные, две – нечетные.)
– Как нужно совершить обход этого графа, согласно правилу Эйлера? (Начать обход в одной из нечетных вершин А или Е, а завершить в другой.)
6. Вычерчивание фигур одним росчерком
Итак, мы увидели, что на языке теории графов каждая решенная задача выглядит как задача изображения «одним росчерком» графа, представленного на рисунке.
Теперь нам нетрудно будет разобраться и показать, какую из любых данных фигур можно вычертить одним росчерком, без повторения линий, а какую нет. Каждую из задач подобного рода можно свести к разобранной уже нами Эйлеровой задаче о мостах.
Например, на рисунке изображена птица.
Взяв за вершины графа точки пересечения линии, получим 7 вершин, только две из которых имеют нечетную степень.
Поэтому в этом графе существует эйлеров путь, а значит, птицу можно нарисовать одним росчерком.
Нечетные вершины: две.
4. Итог урока
Учитель выясняет у детей, на все ли вопросы они получили интересующие их ответы, а также сообщает, что с остальными видами задач знакомство будет продолжено на следующем уроке.
На сегодняшнем уроке мы познакомились с основными понятиями теории графов, примерами графов и их использованием в различных областях знаний, а также применением графов при решении различных задач.
5. Домашнее задание
Графы. Применение графов к решению задач
1. Методические рекомендации к теме “Графы”.
Понятие графа целесообразно вводить после того, как разобрано несколько задач, подобных задаче 1, решающее соображение в которых – графическое представление. Важно, чтобы ученики сразу осознали, что один и тот же граф может быть нарисован разными способами. Строгое определение графа, на мой взгляд, давать не нужно, т.к. оно слишком громоздко и это только затруднит обсуждение. На первых порах хватит и интуитивного понятия. При обсуждении понятия изоморфизма можно решить несколько упражнений на определение изоморфных и неизоморфных графов. Одно из центральных мест темы – теорема о четности числа нечетных вершин. Важно, чтобы ученики до конца разобрались в ее доказательстве и научились применять к решению задач. При разборе нескольких задач рекомендую не ссылаться на теорему, а фактически повторять ее доказательство. Чрезвычайно важно также понятие связности графа. Содержательным соображением здесь является рассмотрение компоненты связности, на это необходимо обратить особое внимание. Эйлеровы графы – тема почти игровая.
Первая и главная цель, которую нужно преследовать при изучении графов, –научить школьников видеть граф в условии задачи и грамотно переводить условие на язык теории графов. Не стоят рассказывать обе всем на нескольких занятиях подряд. Лучше разнести занятия по времени на 2–3 учебных года. (Прилагается разработка занятия “Понятие графа. Применение графов к решению задач” в 6 классе).
2. Теоретический материал к теме “Графы”.
Графы – замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач. В математике существует целый раздел – теория графов, который изучает графы, их свойства и применение. Мы же обсудим только самые основные понятия, свойства графов и некоторые способы решения задач.
Рассмотрим две задачи.
Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.
Теперь сразу видно, что долететь с Земли до Марса нельзя.
Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4×4 убрать угловые клетки.
Решение: Занумеруем последовательно клетки доски:
А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:
Мы рассмотрели две непохожие задачи. Однако решения этих двух задач объединяет общая идея – графическое представление решения. При этом и картинки, нарисованные для каждой задачи, оказались похожими: каждая картинка – это несколько точек, некоторые из которых соединены линиями.
Такие картинки и называются графами. Точки при этом называются вершинами, а линии – ребрами графа. Заметим, что не каждая картинка такого вида будет называться графом. Например. если вас попросят нарисовать в тетради пятиугольник, то такой рисунок графом не будет. Будем называть что рисунок такого вида, как в предыдущих задачах, графом, если есть какая-то конкретная задача для которой такой рисунок построен.
Другое замечание касается вида графа. Попробуйте проверить, что граф для одной и той же задачи можно нарисовать разными способами; и наоборот для разных задач можно нарисовать одинаковые по виду графы. Здесь важно лишь то, какие вершины соединены друг с другом, а какие – нет. Например, граф для задачи 1 можно нарисовать по-другому:
Такие одинаковые, но по-разному нарисованные графы, называются изоморфными.
Степени вершин и подсчет числа ребер графа
Запишем еще одно определение: Степенью вершины графа называется количество выходящих из нее ребер. В связи с этим, вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной.
С понятием степени вершины связана одна из основных теорем теории графов –теорема о честности числа нечетных вершин. Докажем ее мы немного позднее, а сначала для иллюстрации рассмотрим задачу.
Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным 
. Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.
Ответ. Соединить телефоны таким образом невозможно.
Теорема: Любой граф содержит четное число нечетных вершин.
Доказательство: Количество ребер графа равно половине суммы степеней его вершин. Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной. А это возможно только в том случае, если граф содержит четное число нечетных вершин.
Есть еще одно важное понятие, относящееся к графам – понятие связности.
Граф называется связным, если из любые две его вершины можно соединить путем, т.е. непрерывной последовательностью ребер. Существует целый ряд задач, решение которых основано на понятии связности графа.
Задача 4. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.
Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:
Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного.
Если принять во внимание предыдущее определение, то утверждение задачи можно переформулировать и по-другому: “Доказать, что граф дорог страны Семерка связен.”
Теперь вы знаете, как выглядит связный граф. Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф. Пример несвязного графа вы видите на рисунке:
Каждый такой отдельный кусок называется компонентой связности графа. Каждая компонента связности представляет собой связный граф и для нее выполняются все утверждения, которые мы доказали для связных графов. Рассмотрим пример задачи, в которой используется компонента связности:
Задача 5. В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний.
Доказательство: Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний – по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности – связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.
Вы наверняка сталкивались с задачами, в которых требуется нарисовать какую-либо фигуру не отрывая карандаш от бумаги и проводя каждую линию только один раз. Оказывается, что такая задача не всегда разрешима, т.е. существуют фигуры, которые указанным способом нарисовать нельзя. Вопрос разрешимости таких задач также входит в теорию графов. Впервые его исследовал в 1736 году великий немецкий математик Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами.
Решение. Если мы будем рисовать граф так, как сказано в условии, то в каждую вершину, кроме начальной и конечной, мы войдем столько же раз, сколько выйдем из нее. То есть все вершины графа, кроме двух должны быть четными. В нашем же графе имеется три нечетные вершины, поэтому его нельзя нарисовать указанным в условии способом.
Сейчас мы доказали теорему об Эйлеровых графах:
Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.
И в заключение – задача о Кенигсбергских мостах.
Задача 7. На рисунке изображена схема мостов города Кенигсберга.
Можно ли совершить прогулку так, чтобы пройти по каждому мосту ровно 1 раз?
3. Задачи к теме “Графы”
Понятие графа.
1. На квадратной доске 3×3 расставлены 4 коня так, как показано на рис.1. Можно ли сделав несколько ходов конями, переставить их в положение, показанное на рис.2?
 |
Рис. 1
Решение. Занумеруем клетки доски, как показано на рисунке:
Каждой клетке поставим в соответствие точку на плоскости и, если из одной клетки можно попасть в другую ходом шахматного коня, то соответствующие точки соединим линией. Исходная и требуемая расстановки коней показаны на рисунках:
 |  |
При любой последовательности ходов конями порядок их следования, очевидно, измениться не может. Поэтому переставить коней требуемым образом невозможно.
Решение. Поставив в соответствие каждому городу точку и соединив точки линией, если сумма цифр делится на 3, получим граф, в котором цифры 3, 5, 9 связаны между собой, но не связаны с остальными. Значит долететь из города 1 в город 9 нельзя.
Степени вершин и подсчет числа ребер.
3. В государстве 100 городов к из каждого города выходит 4 дороги. Сколько всего дорог в государстве.
Решение. Подсчитаем общее количество выходящих городов дорог – 100 . 4 = 400. Однако при таком подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 200.
Ответ. Нет (теорема о четности числа нечетных вершин).
Ответ. Нет, не может.
6. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?
Решение. Подсчитаем число городов. Число дорог равно числу городов х, умноженному на 3 (число выходящих из каждого города дорог) и разделенному на 2 (см. задачу 3). Тогда 100 = Зх/2 => Зх=200, чего не может быть при натуральном х. Значит 100 дорог в таком государстве быть не может.
7. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.
Доказательство непосредственно следует из теоремы о четности числа нечетных вершин графа.
Связность.
8. В стране из каждого города выходит 100 дорог и из каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь из любого города можно добраться до любого другого.
Доказательство. Рассмотрим компоненту связности, в которую входит один из городов, дорогу между которыми закрыли. По теореме о четности числа нечетных вершин в нее входит и второй город. А значит по-прежнему можно найти маршрут и добраться из одного из этих городов в другой.
Графы Эйлера.
9. Имеется группа островов, соединенных мостами так, что от каждого острова можно добраться до любого другого. Турист обошел все острова, пройдя по каждому мосту розно 1 раз. На острове Троекратном он побывал трижды. Сколько мостов ведет с Троекратного, если турист
а) не с него начал и не на нем закончил?
б) с него начал, но не на нем закончил?
в) с него начал и на нем закончил?
10. На рисунке изображен парк, разделенный на несколько частей заборами. Можно ли прогуляться по парку и его окрестностям так, чтобы перелезть через каждый забор розно 1 раз?
ПРезентация «Графы», 5-6 класс
Описание презентации по отдельным слайдам:
Занятие кружка по математике «Мосты Эйлера». Теория графов. Мосты Кёнигсберга.
Появление теории графов как математической дисциплины, все единодушно относят к 1736 году, когда Л. Эйлер (1707-1782, российский математик, швейцарец по происхождению, академик Петербургской и Берлинской академии наук), решил широко известную в то время задачу о Кёнигсбергских мостах. Подробнее об этой задаче будет сказано ниже. Этот результат более ста лет оставался единственным в теории графов.
В процессе решения задач математики заметили, что удобно изображать объекты точками, а отношения между ними отрезками или дугами. В математике определение графа дается так: Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами. Рёбра графа Вершина графа
Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной. Нечётная степень Чётная степень
если нечетных точек в фигуре нет, то ее можно начертить одним росчерком, начиная вычерчивать с любого места; если в фигуре две нечетные точки (если фигура имеет нечетную точку, то она всегда имеет и вторую нечетную точку), то ее можно начертить одним росчерком, начав вычерчивание в одной из нечетных точек и закончив в другой; если в фигуре более двух нечетных точек, то ее нельзя вычертить одним росчерком.
Попробуй начертить самостоятельно Давай проверим!
Определите, какие из фигур можно начертить не отрывая карандаш от бумаги (и не проводя по одной линии дважды). признаки вычерчивания задачи физминутка
Бывший Кенигсберг Возникший в XIII веке (ныне Калининград) расположен на реке Прегель, делящей город на четыре главные части: Альтштадт, Кнайпхоф, Ломзе и Форштадт. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены.
К концу 19 века в Кёнигсберге было построено 7 основных мостов. Примерно в эти же годы составлена классическая задача о семи мостах Кёнигсберга. Надо было пройти по всем городским мостам не проходя по одному из них дважды.
Схема мостов Кёнигсберга
По старой традиции, каждый приезжающий в Кёнигсберг должен бросить по одной монетке с любого из семи мостов, чтобы вернуться в этот город.
Философ Иммануил Кант, гуляя по городу Кенигсбергу, поставил задачу, известную в математике как задача о семи кенигсбергских мостах: можно ли пройти по всем этим мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз.
Преподаватель Кёнигсбергского университета «Альбертина» Леонард Эйлер решил задачу, составленную Кантом.
Прохождение по всем мостам при условии, что нужно на каждом побывать один раз и вернуться в точку начала путешествия, на языке теории графов выглядит как задача изображения «одним росчерком» графа.
Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. Решая задачу О кенигсбергских мостах, Эйлер сформулировал свойства графа: Невозможно начертить граф с нечетным числом нечетных вершин.
В Кенигсберге река, омывающая два острова, делится на два рукава, через которые перекинуто семь мостов. Можно ли обойти все эти мосты, не побывав ни на одном из них более раза? № 1
Составим схему к решению задачи Из рисунка видно, что у полученной фигуры четыре нечетные вершины, следовательно, ее нельзя построить, не пройдя по одной линии дважды, а значит, нельзя пройти по мостам так, чтобы не пройти по одному и тому же два раза. А В С D
Через реку, омывающую три острова, перекинуто 9 мостов. Можно ли обойти все эти мосты, гоняясь за зайцем, не побывав ни на одном из них более одного раза? А В С D E № 2
Составим схему к решению задачи Из рисунка видно, что у полученной фигуры две нечетные вершины, следовательно, ее можно построить, не отрывая карандаша от бумаги, а значит, можно пройти по мостам, не пройдя по одному и тому же два раза, начиная, например, с одного из мостов островка Е.
ЕСЛИ все вершины – четные, то его можно начертить «одним росчерком», начиная с любой вершины. ЕСЛИ 2 вершины – нечетные, то его нужно начать с одной из нечетных вершин. Обход невозможен, если нечетных вершин больше 2.
В 1905 году в Кенигсберге был поострен еще один мост. (Слайд 30) История кайзера Вильгельма: Кайзер (император) Вильгельм славился своей прямотой, простотой мышления и солдатской «недалёкостью». Однажды, находясь на светском рауте, он чуть не стал жертвой шутки, которую с ним решили сыграть учёные умы, присутствующие на приёме. Они показали кайзеру карту Кёнигсберга, и попросили попробовать решить эту знаменитую задачу, которая по определению была нерешаемой. К всеобщему удивлению, кайзер попросил перо и лист бумаги, сказав, что решит задачу за полторы минуты. Ошеломлённый немецкий истеблишмент не мог поверить своим ушам, но бумагу и чернила быстро нашли. Кайзер положил листок на стол, взял перо, и написал: «приказываю построить восьмой мост на острове Ломзе». Так в Кёнигсберге и появился новый мост, который так и назвали — мост кайзера. А задачу с восемью мостами теперь мог решить даже ребёнок.
Был построен в 1905 году по приказу канцлера Вильгельма. Своему появлению он обязан самой задачи Эйлера. ИМПЕРАТОРСКИЙ мост(Kaiser-brucke).
В розыгрыше финальной части турнира участвуют семь команд: шесть команд, набравших наибольшее количество очков в предварительной части турнира и команда – победитель прошлого года. Сначала играют друг с другом первые шесть команд, затем три команды, одержавшие победы и команда, победитель прошлого года, играют друг с другом. Два победителя этого тура встречаются в финале.
Задача №2 В школьный компьютерный класс завезли 5 компьютеров, которые требуется связать локальной сетью. Известны расстояния между компьютерами. Требуется связать компьютеры таким образом, чтобы общая длина кабеля была бы наименьшей.
ЗАДАЧА 4 Дан кусок проволоки, длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см? Решение: Если куб – граф, тогда он имеет более двух нечетных вершин (8). Значит, невозможно изготовить такой каркас, не ломая проволоки.
На этом занятии были рассмотрены графы, которые тесно связаны с историей о мостах Кёнигсберга. С помощью графов часто упрощалось решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии и др. С помощью графов изображаются схемы дорог, газопроводов, тепло- и электросети. Помогают графы в решении математических и экономических задач.
Курс повышения квалификации
Дистанционное обучение как современный формат преподавания
Курс повышения квалификации
Методика обучения математике в основной и средней школе в условиях реализации ФГОС ОО
Курс профессиональной переподготовки
Математика: теория и методика преподавания в образовательной организации
Ищем педагогов в команду «Инфоурок»
Номер материала: ДБ-446424
Не нашли то что искали?
Вам будут интересны эти курсы:
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.
Учителя о ЕГЭ: секреты успешной подготовки
Время чтения: 11 минут
Итоговое сочинение успешно написали более 97% выпускников школ
Время чтения: 2 минуты
В Хабаровске родители смогут заходить в школы и детсады только по QR-коду
Время чтения: 1 минута
Российские юниоры завоевали 6 медалей на Международной научной олимпиаде
Время чтения: 2 минуты
Путин поручил не считать выплаты за классное руководство в средней зарплате
Время чтения: 1 минута
Путин призвал повышать уровень общей подготовки в колледжах
Время чтения: 1 минута
Учителя о ЕГЭ: секреты успешной подготовки
Время чтения: 11 минут
Подарочные сертификаты
Ответственность за разрешение любых спорных моментов, касающихся самих материалов и их содержания, берут на себя пользователи, разместившие материал на сайте. Однако администрация сайта готова оказать всяческую поддержку в решении любых вопросов, связанных с работой и содержанием сайта. Если Вы заметили, что на данном сайте незаконно используются материалы, сообщите об этом администрации сайта через форму обратной связи.
Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.