Презентация по математике на тему "Графы"

Графы.
Решение задач с помощью графов
Учитель математики
Переведенцева Е.Н., МБОУ Средняя школа №7
г.Щёкино Тульской области

О Кенигсбергских мостах. 
Город Кенигсберг расположен на берегах реки Прегель и двух островах. Различные части города были соединены семью мостами. По воскресеньям горожане совершали прогулки по городу.

Леонард Эйлер – российский, немецкий и швейцарский математик, внесший огромный вклад в развитие математики. С его именем связана история появления графов.

Примеры графов

 
Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – ребрами.
Вершины, которые не принадлежат ни одному ребру, называются изолированными.

Граф называется полным, если каждые две различные вершины его соединены одним и только одним ребром.
Степенью вершины называется число ребер графа, которым принадлежит эта вершина.
Вершина называется нечетной, если ее степень — число нечетное. Вершина называется четной, если ее степень — число четное.

Циклом в графе называется такая конечная цепь, которая начинается и заканчивается в одной вершине. Цикл обозначается последовательностью вершин, которые он содержит, например: (3-5-6-7-3).
В теории графов два типа объектов обычно называются циклами. Один тип циклов, чаще называющиеся замкнутым обходом, состоит из последовательности вершин, начинающейся и заканчивающейся в той же самой вершине, и каждые две последовательные вершины в последовательности смежные. Другой тип циклов, иногда называемых простыми циклами, — это замкнутые обходы без повторного прохода по ребру или посещения вершины дважды, за исключением начальной и конечной вершин.

Две вершины А и В графа называются связными, если в графе существует путь с концами А и В.
Две вершины графа называются несвязными, если в графе не существует ни одного пути, связывающего их.
Граф называется связным, если каждые две вершины его связные.
Граф называется несвязным, если хотя бы две вершины его не­связные.

Деревом называется всякий связный граф, не имеющий циклов.
Вершина дерева, степень которой равна единице, называется висячей вершиной (на рисунке висячие вершины выдел закрашенными кружками).

Задачи, приводящие к графам

Женя, Дима, Максим и Але­ша сыграли между собой по одной партии в шахматы. Сколько всего партий было сыграно?
Вася, Коля, Петя, Аня и Наташа - луч­шие лыжники в пятом классе. Для уча­стия в соревнованиях нужно выбрать из них одного мальчика и одну девоч­ку. Сколькими способами это можно сделать?
Пятеро ученых, участвовавших в научной конференции, обменялись рукопожатиями. Сколько всего было сделано рукопожатий?
На прощание эти ученые обменялись визитными карточками. Сколько карточек было передано из рук в руки?

Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам:
Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран.
Можно ли долететь на рейсовых ракетах с Земли до Марса ?

Однажды Андрей, Борис, Володя, Даша и Галя договорились вечером пойти в кино. Выбор кинотеатра и сеанса они решили согласовать по телефону. Было также решено, что если с кем-то созвониться не удастся, то поход в кино отменяется. Вечером у кинотеатра собрались не все, и поэтому посещение кино сорвалось. На следующий день стали выяснять, кто кому звонил. Оказалось, что Андрей звонил Борису и Володе, Володя звонил Борису и Даше, Борис звонил Андрею и Даше, Даша звонила Андрею и Володе, а Галя звонила Андрею, Володе и Борису. Кто не сумел созвониться и поэтому не пришёл на встречу?

В одном дворе живут 4 друга:
Вадим и шофер старше Сергея; Николай и слесарь занимаются боксом;
электрик младший из друзей.
По вечерам Антон и токарь играют в домино против Сергея и электрика.
Определите профессию каждого из друзей.

Алексей, Борис, Виталий и Геннадий – друзья. Один из них –врач, другой – журналист, третий – тренер спортивной школы, четвертый – строитель. Журналист написал статьи об Алексее и Геннадие . Тренер и журналист вместе с Борисом ходили в поход. Алексей и Борис были на приеме у врача. У кого какая профессия?