Файл: Графы. Вершина. Ребро. Представление задачи с помощью графов.pptx

Графы. Вершина. Ребро. Представление задачи с помощью графов.

Леонард Эйлер

(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

---