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