Презентация к уроку

Граф. Связный граф 10 класс

Теория графов:

Начало - задача о кёнигсбергских мостах , ( Леонард Эйлером, 1736 г.)

21 век: развитие компьютеров - активное развитие научных дисциплин, находящихся на стыке математики и информатики.

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

Точки называются вершинами графа, а соеди няющие их линии — рёбрами .

Вершины и рёбра обо значают буквами или числами.

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

• 1. Что такое граф?

• 2. Приведите пример графа, с которым вы сталкивались в реальной жизни. Что служило вер шинами, а что рёбрами этого графа?

• 3. Нарисуйте какой-нибудь граф с четырьмя вершинами

• 4. Чем мультиграф отличается от графа?

• 5. Нарисуйте мультиграф с пятью вершинами

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

СТЕПЕНЬ – главная характеристика графа

СТЕПЕНЬ вершины – количество ребер, проведенных из этой вершины.

Если вершина имеет степень 0 (т. е. не соединена ни с какой другой

вершиной), то она называется изолированной .

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

Теорема 2. Сумма степеней всех вершин графа равна удвоенному числу его рёбер.

Следствие. В любом графе количество вершин нечётной степени всегда чётно.

Упражнение

Упражнение

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

Определите, существует ли описанный ниже граф. Если да, то постройте его:

а) граф из семи вершин, в котором все вершины имеют степень 2;

б) граф из восьми вершин, в котором все вершины имеют степень 2;

в) граф из восьми вершин, в котором все вершины имеют степень 1;

г) граф из семи вершин, в котором все вершины имеют степень 1;

д) граф из семи вершин, в котором все вершины имеют степень 3;

е) граф из восьми вершин, в котором все вершины имеют степень 3.

Определите, существует ли описанный ниже граф. Если да, то постройте его:

а) граф из 7 вершин, в котором все вершины имеют степень 2; а) да;

б) граф из 8 вершин, в котором все вершины имеют степень 2; б) да;

в) граф из 8 вершин, в котором все вершины имеют степень 1; б) да;

г) граф из 7 вершин, в котором все вершины имеют степень 1; г) нет;

д) граф из 7 вершин, в котором все вершины имеют степень 3; д) нет;

е) граф из 8 вершин, в котором все вершины имеют степень 3. е) да.

Пути, цепи и циклы

Путь (маршрут) - последовательность ребер,

по которым можно перейти из одной вершины в другую.

Длина пути – количество ребер в пути.

Цепь – это путь, в котором ребра не повторяются.

Цикл – это цепь,

в которой начальная и конечная вершина совпадают .

(простейший цикл –петля)

аbcdeg – цепь

bcfba — цепь,

abaf - нет.

Цикл - abfa , abcfa , bcdgcfb .

1 Петя вбил в землю 5 колышков и соединил некоторые из них верёвками. Могло ли так по лучиться, что к каждому колышку привязано ровно по 3 верёвки?

2 На олимпиаде по математике каждый из 30 участников решил по 4 задачи, а каждую задачу решило ровно 10 человек. Сколько задач было на олимпиаде?

3 В чемпионате города по футболу участвует 12 команд. Чемпионат проводится в один круг. Докажите, что в любой момент проведения чемпионата всегда найдутся хотя бы две коман ды, сыгравшие одинаковое число матчей.

4 На лавке сидят семеро ребят. Каждый имеет среди остальных не менее трёх братьев. Докажите, что все семеро — братья.

5 Можно ли из куска проволоки длиной 120 см изготовить каркас куба с ребром 10 см? Проволоку разрешается сгибать, но не разламывать.

6 Можно ли раскрасить рёбра куба в красный и зелёный цвета так, чтобы муравей мог прой- ти из любой вершину в любую только по красным рёбрам, а жук — только по зелёным?

СВЯЗНЫЙ ГРАФ

Граф называется связным, если для любых двух вершин найдется путь,

который их соединяет.