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