Презентация на тему "Граф. Связный граф. Путь, цикл, цепь." 10 класс

Содержание

• 
  Слайд 1
  

  Граф. Связный граф

• 
  Слайд 2
  
• 
  Слайд 3
  

  Теорияграфов: Начало - задачаокёнигсбергских мостах, (Леонард Эйлером, 1736 г.) 21 век: развитие компьютеров - активноеразвитие научныхдисциплин,находящихсянастыкематематикииинформатики.

• 
  Слайд 4
  

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

• 
  Слайд 5
  

  Мультиграф – наличие нескольких рёбер между одной и той же парой вершин. Эти несколько рёбер называют кратнымирёбрами.

• 
  Слайд 6
  

  1. Чтотакоеграф? 2. Приведите пример графа, с которым вы сталкивались в реальной жизни. Чтослужиловершинами, а чторёбрамиэтогографа? 3. Нарисуйте какой-нибудь граф с четырьмя вершинами 4. Чем мультиграф отличается отграфа? 5. Нарисуйте мультиграф с пятью вершинами

• 
  Слайд 7
  

  Петля - ребро особого вида, которое соединяет вершину с ней же самой.

• 
  Слайд 8
  

  СТЕПЕНЬ – главная характеристика графа СТЕПЕНЬвершины – количество ребер, проведенных из этой вершины. Если вершина имеет степень 0 (т. е. не соединена ни с какой другой вершиной), то она называется изолированной.

• 
  Слайд 9
  

  Теорема 1. Если простой граф содержит больше одной вершины, то в нём обязательнонайдутсяхотябыдвевершиныодинаковойстепени. Теорема 2. Сумма степеней всех вершин графа равна удвоенному числу его рёбер. Следствие. В любом графе количество вершин нечётной степени всегда чётно.

• 
  Слайд 10
  

  Упражнение

• 
  Слайд 11
  

  Упражнение

• 
  Слайд 12
  

  1 Чтоназываетсястепеньювершины? 2 Если у простого графа 12 вершин, в каких границах могут изменяться ихстепени? 3 Существует ли граф с тремя вершинами, степени которых равны 0, 1 и2? 4 Может ли сумма степеней всех вершин графа равняться13? 5 Если у графа 10 рёбер, чему равна сумма степеней всех еговершин?

• 
  Слайд 13
  

  Определите, существует ли описанный ниже граф. Если да, то постройте его: а) граф из семи вершин, в котором все вершины имеют степень 2; б) граф из восьми вершин, в котором все вершины имеют степень 2; в) граф из восьми вершин, в котором все вершины имеют степень 1; г) граф из семи вершин, в котором все вершины имеют степень 1; д) граф из семи вершин, в котором все вершины имеют степень 3; е) граф из восьми вершин, в котором все вершины имеют степень3.

• 
  Слайд 14
  

  Определите, существует ли описанный ниже граф. Если да, то постройте его: а) граф из 7 вершин, в котором все вершины имеют степень 2;а)да; б) граф из 8 вершин, в котором все вершины имеют степень 2; б)да; в) граф из 8 вершин, в котором все вершины имеют степень 1; б)да; г) граф из 7 вершин, в котором все вершины имеют степень 1;г)нет; д) граф из 7 вершин, в котором все вершины имеют степень 3; д)нет; е) граф из 8 вершин, в котором все вершины имеют степень3.е)да.

• 
  Слайд 15
  

  Путь (маршрут) - последовательность ребер, по которым можно перейти из одной вершины в другую. Длина пути – количество ребер в пути. Пути, цепи и циклы Цикл – это цепь, в которой начальная и конечная вершина совпадают. (простейший цикл –петля) Цепь – это путь, в котором ребра не повторяются.

• 
  Слайд 16
  
• 
  Слайд 17
  

  аbcdeg – цепь bcfba— цепь, abaf- нет. Цикл - abfa, abcfa, bcdgcfb.

• 
  Слайд 18
  

  1 Петявбил в землю 5 колышков и соединилнекоторыеизнихверёвками. Могло ли так получиться, что к каждому колышку привязано ровно по 3 верёвки? 2 Наолимпиадепоматематикекаждыйиз30участниковрешилпо4задачи,акаждуюзадачу решило ровно 10 человек. Сколькозадачбылонаолимпиаде? 3 В чемпионате города по футболу участвует 12 команд. Чемпионат проводится в один круг. Докажите,чтовлюбоймоментпроведениячемпионатавсегданайдутсяхотябыдвекоманды, сыгравшие одинаковое числоматчей. 4 На лавке сидят семеро ребят. Каждый имеет среди остальных не менее трёх братьев. Докажите, чтовсесемеро —братья. 5 Можно ли из куска проволоки длиной 120 см изготовить каркас куба с ребром 10 см? Проволокуразрешаетсясгибать, нонеразламывать. 6 Можно ли раскрасить рёбра куба в красный и зелёный цвета так, чтобы муравей мог прой- ти из любой вершину в любую только по красным рёбрам, а жук — только позелёным?

• 
  Слайд 19
  

  СВЯЗНЫЙ ГРАФ Граф называется связным, если для любых двух вершин найдется путь, который их соединяет.

• 
  Слайд 20
  
• 
  Слайд 21
  
• 
  Слайд 22