Граф. Связный граф. Путь, цикл, цепь.
методическая разработка по математике (10 класс)

Слайд 1

Слайд 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

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

Слайд 17

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

Слайд 18

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

Слайд 19

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