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

• 1 слайд

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

• 2 слайд

  Леонард Эйлер
  (1707г – 1783гг)
  Швейцарский, прусский и российский математик
  Основы теории графов как математической науки заложил в 1736 г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Сегодня эта задача стала классической.
  Теория графов зародилась в ходе решения головоломок двести с лишним лет назад.
  

• 3 слайд

  Что такое граф
  Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. В процессе решения задач математики заметили, что удобно изображать объекты точками, а отношения между ними отрезками или дугами.
  
  Дальше
  

• 4 слайд

  Примеры графов: карта дорог, схема метро, электросхема, чертеж прямоугольника и т.п.
  

• 5 слайд

  Что такое граф
  Графом называется конечное множество точек, некоторые из которых соединены линиями.
  Точки называются вершинами графа, а соединяющие линии – рёбрами.
  (Каждое ребро соединяет ровно две вершины).
  Рёбра графа
  Вершины графа
  

• 6 слайд

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

• 7 слайд

  Упражнения
  1. В графе 3 вершины, каждая из которых имеет степень 2. Сколько у него ребер? Нарисуйте такой граф.
  Ответ: 3.
  

• 8 слайд

  2. В графе 4 вершин, каждая из которых имеет степень 3. Сколько у него ребер? Нарисуйте такой граф.
  Ответ: 6.
  

• 9 слайд

  3. В графе 5 вершин, каждая из которых имеет степень 4. Сколько у него ребер? Нарисуйте такой граф.
  Ответ: 10.
  

• 10 слайд

  П
  И
  А
  М
  С
  В
  Н
  Д
  Е
  Ответ: нет.
  

• 11 слайд

  Пример 2:
  Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
  

• 12 слайд

  Решение:
  А
  Г
  В
  Б
  Д
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  Ответ: 10.
  

• 13 слайд

  Пример 3
  В первенстве класса по настольному теннису принимали участие 5 учеников:
  Андрей, Борис, Галина, Олег, Елена.
  Первенство проводилось по круговой системе – каждый участник играет с каждым из остальных один раз.
  К настоящему моменту некоторые игры уже проведены:
  Андрей сыграл с Борисом, Галиной и Еленой;
  Борис с Андреем и Галиной;
  Галина с Андреем и Олегом.
  Сколько игр проведено к настоящему
  моменту и сколько ещё осталось?
  
  

• 14 слайд

  Решение
  Андрей сыграл с Борисом, Галиной и Еленой;
  Борис с Андреем и Галиной
  Галина с Андреем и Олегом.
  Андрей
  Борис
  Галина
  Елена
  Олег
  Ответ: сыграно 5 партий,
  осталось 5 партий.
  

• 15 слайд

  Пример 4. По окончании деловой встречи специалисты обменялись визитными карточками (каждый вручил свою карточку каждому). Сколько всего визитных карточек было роздано, если во встрече участвовали 4 человека?
  1
  2
  3
  4
  Ответ: 12.
  

• 16 слайд

  Пример 5
  У Васи в альбоме нарисован прямоугольник, разделённый на три равные части. Он должен закрасить каждую из этих частей в один из трёх цветов: красный, жёлтый, зелёный. Нельзя закрашивать разные части одинаковым цветом. Сколько вариантов рисунка может получиться?
  1 клетка
  2 клетка
  3 клетка
  Ответ: 6 вариантов
  

• 17 слайд

  Пример 6. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Е?
  
  
  1
  1
  Отметим на рисунке индексами сверху каждого пункта количество путей,
  с помощью которых в него можно попасть
  1+1=2
  2+1=3
  2+1=3
  3+3+2=8