Графы и их применение. 11 класс

1.

ГРАФЫ И ИХ
ПРИМЕНЕНИЕ
Выполнил:
обучающийся 11а класса
МОУ «СОШ № 42»
Калашников Алексей
Руководитель проекта:
учитель информатики
Шерстобитов В.Г.

2.

ИСТОРИЯ ПОЯВЛЕНИЯ
ГРАФОВ
Леонард
Кёнигсбергские

3.

ПОНЯТИЕ ГРАФА
Графом в математике называется конечная совокупность точек,
именуемых вершинами; некоторые из них соединены друг с другом
линиями, называемых ребрами графа.

4.

ВИДЫ ГРАФОВ
A. Ориентированный
Б. Неориентированный
граф
граф

5.

ВИДЫ ГРАФОВ
В. Взвешенный
граф
Г. Связный граф

6.

ПОЛНОТА ГРАФА
Полный граф
Неполный граф

7.

СТЕПЕНЬ ВЕРШИНЫ
Степень =1
Степень =2
Степень =0

8.

СВОЙСТВА ГРАФОВ
Если все вершины графа четные, то можно одним росчерком
начертить граф. Граф с двумя нечетными вершинами тоже
можно начертить одним росчерком. Если нечетных вершин
больше, то уже не получится.

9.

ЗАДАЧА
В городе Маленький 15 телефонов. Можно ли их соединить
проводами так, чтобы каждый телефон был соединен ровно с
пятью другими?

10.

ОТВЕТ
Число вершин нечётной степени должно быть чётно. В
нашем графе все вершины нечётной степени. А так как их 15,
то есть нечётное число, то такое соединение телефонов
невозможно.