Граф, вершины, ребро. Презентация по ТВиС _Графы. Вершина. Ребро. Представление задачи. Графы. Вершина. Ребро. Представление задачи с помощью графов
 Скачать 1.6 Mb.
|
Графы. Вершина. Ребро. Представление задачи с помощью графов.Леонард Эйлер (1707г – 1783гг) Швейцарский, прусский и российский математик Основы теории графов как математической науки заложил в 1736 г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Сегодня эта задача стала классической. Теория графов зародилась в ходе решения головоломок двести с лишним лет назад. Что такое графСлово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. В процессе решения задач математики заметили, что удобно изображать объекты точками, а отношения между ними отрезками или дугами.Дальше Примеры графов: карта дорог, схема метро, электросхема, чертеж прямоугольника и т.п. Что такое графГрафом называется конечное множество точек, некоторые из которых соединены линиями.Точки называются вершинами графа, а соединяющие линии – рёбрами.(Каждое ребро соединяет ровно две вершины).Рёбра графа Вершины графа Что такое графКоличество рёбер, выходящих из вершины графа, называется степенью вершины.Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.Нечётная степень Чётная степень содержание Упражнения1. В графе 3 вершины, каждая из которых имеет степень 2. Сколько у него ребер? Нарисуйте такой граф. Ответ: 3. 2. В графе 4 вершин, каждая из которых имеет степень 3. Сколько у него ребер? Нарисуйте такой граф. Ответ: 6. 3. В графе 5 вершин, каждая из которых имеет степень 4. Сколько у него ребер? Нарисуйте такой граф. Ответ: 10. П И А М С В Н Д Е Ответ: нет. Пример 2:Пример 2:Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?Решение:Решение:А Г В Б Д 1 2 3 4 5 6 7 8 9 10 Ответ: 10. Пример 3В первенстве класса по настольному теннису принимали участие 5 учеников:Андрей, Борис, Галина, Олег, Елена.Первенство проводилось по круговой системе – каждый участник играет с каждым из остальных один раз.К настоящему моменту некоторые игры уже проведены:
Сколько игр проведено к настоящемумоменту и сколько ещё осталось?Решение
Андрей Борис Галина Елена Олег Ответ: сыграно 5 партий, осталось 5 партий. Пример 4. По окончании деловой встречи специалисты обменялись визитными карточками (каждый вручил свою карточку каждому). Сколько всего визитных карточек было роздано, если во встрече участвовали 4 человека? 1 2 3 4 Ответ: 12. Пример 5У Васи в альбоме нарисован прямоугольник, разделённый на три равные части. Он должен закрасить каждую из этих частей в один из трёх цветов: красный, жёлтый, зелёный. Нельзя закрашивать разные части одинаковым цветом. Сколько вариантов рисунка может получиться?1 клетка 2 клетка 3 клетка Ответ: 6 вариантов 1 1 Отметим на рисунке индексами сверху каждого пункта количество путей, с помощью которых в него можно попасть 1+1=2 2+1=3 2+1=3 3+3+2=8 |