Графы

Слайд 1

Слайд 2

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

Слайд 3

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

Слайд 4

Графы Вершин:6 Рёбер:7 Вершина графа. Ребро графа.

Слайд 5

Задача Условие: В спортивном зале собрались ребята. Кто с кем знаком. (если ребро графа означает « мы знакомы») В – Витя. С – Саша. П – Петя. М – Миша. К – Коля. С В П М К Витя +Саша +Коля Саша + Витя + Петя Петя + Саша +Миша Коля + Витя + Миша Миша + Коля + Петя Ребро графа

Слайд 6

Задача Вера, Нина, Оля и Люба надели платья различных цветов. (Красное, синее, белое, голубое). Кто из них в каком платье? Оля Нина Вера Люба Красное синее голубое белое Оля - в синем, Люба - в белом; Оля - в красном, Нина - в синем; Вера - в синем, Люба - в голубом . Ответы: Оля в красном, Нина в голубом, Люба в белом, Вера в синем.

Слайд 7

Марина Лариса Жанна Катя Пианино гитара виолончель скрипка Англ. яз. Немец. яз. Франц. яз. Испан. яз. Марина, Лариса, Жанна и Катя умеют играть на различных инструментах,( пианино, виолончели, гитаре, скрипке), но каждая только на одном. Они же знают иностранные языки(английский, немецкий, французский, испанский. Известно : 1( девушка, которая играет на гитаре, говорит по- испански; 2)Лариса не играет на скрипке, ни на виолончели и и не знает английского языка; 3 ) Марина не играет ни на скрипке, ни на виолончели и не знает ни немецкого, ни английского языка; 4) девушка, которая говорит по немецкий не играет на виолончели; 5 ) Жанна знает французский язык, но не играет на скрипке. Стрелочками обозначено то на чем девочки не играют, и какого языка они не знают.

Слайд 8

Задача « Мосты Эйлера » Мост Река Теорема : В неориентированном графе эйлерова цепь существует тогда и только тогда, когда число вершин с нечётной степенью равно 0 или 2, а эйлеров цикл существует тогда и только тогда, когда нет вершин с нечётной степенью. Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает остров. С берегов на остров были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз. Остров