Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему ГРАФ И ЕГО ЭЛЕМЕНТЫ. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

Содержание

Переход по слайдам осуществляется только по нажатию левой кнопки мыши клик мыши!!! Если есть мигающая стрелка, значит нужно нажатие левой кнопки мыши в любом месте слайд для продолжения презентации!!!!После прочтения удалить слайд!
Граф и его элементыОсновные определения Переход по слайдам осуществляется только по нажатию левой кнопки мыши клик мыши!!! ГРАФОМ G = (V, X) НАЗЫВАЕТСЯ ПАРА ДВУХ ТОЧКИ НАЗЫВАЮТСЯ ВЕРШИНАМИ, ИЛИ УЗЛАМИ, ГРАФА, ЛИНИИ – РЕБРАМИ ГРАФА.ПРИМЕРЫ ГРАФОВ ЕСЛИ РЕБРО ГРАФА СОЕДИНЯЕТ ДВЕ ЕГО ВЕРШИНЫ, ТО ГОВОРЯТ, ЧТО ЭТО РЕБРО КРАТНЫЕ РЕБРАЧИСЛО РЕБЕР, ИНЦИДЕНТНЫХ ВЕРШИНЕ A , НАЗЫВАЕТСЯ СТЕПЕНЬЮ ЭТОЙ ВЕРШИНЫ И deg(E) = 0E – ИЗОЛИРОВАННАЯ ВЕРШИНАdeg(G) = 1deg(H) = 1deg(E) = 1deg(B) ТЕОРЕМАВ ГРАФЕ G(V, X) СУММА СТЕПЕНЕЙ ВСЕХ ЕГО ВЕРШИН – ЧИСЛО ЧЕТНОЕ, ГРАФ НАЗЫВАЕТСЯ ПОЛНЫМ, ЕСЛИ ЛЮБЫЕ ДВЕ ЕГО РАЗЛИЧНЫЕ ВЕРШИНЫ СОЕДИНЕНЫ ОДНИМ И ДУГИНАЧАЛО ДУГИ (A,B)КОНЕЦ ДУГИ (A,B)СТЕПЕНЬЮ ВХОДА (ВЫХОДА) ВЕРШИНЫ ОРГРАФА НАЗЫВАЕТСЯ ЧИСЛО РЕБЕР, Последовательность ребер неориентированного графа, в которой вторая вершина Если начальная вершина маршрута совпадает с конечной, то такой маршрут называется совпадает с началом следующего и все ребра единственны.ЦИКЛ В ОРГРАФЕ – ПУТЬ, ЦЕПЬ, ПУТЬ И ЦИКЛ В ГРАФЕ НАЗЫВАЮТСЯ ПРОСТЫМИ, ЕСЛИ ОНИ ПРОХОДЯТ ЧЕРЕЗ ГРАФ G НАЗЫВАЕТСЯ ПЛАНАРНЫМ (ПЛОСКИМ), ЕСЛИ СУЩЕСТВУЕТ ТАКОЙ ГРАФ G' , В ЭЙЛЕРОВЫМ ПУТЕМ (ЦИКЛОМ) ГРАФА НАЗЫВАЕТСЯ ПУТЬ (ЦИКЛ), КОТОРЫЙ СОДЕРЖИТ ВСЕ РЕБРА ГРАФА ГАМИЛЬТОНОВЫМ ПУТЕМ(ЦИКЛОМ) ГРАФА НАЗЫВАЕТСЯ ПУТЬ(ЦИКЛ), ПРОХОДЯЩИЙ ЧЕРЕЗ КАЖДУЮ ЕГО ВЕРШИНУ ТОЛЬКО ОДИН МАТРИЦЕЙ ИНЦИДЕНТНОСТИ ГРАФА G НАЗЫВАЮТ ТАБЛИЦУ B, СОСТОЯЩУЮ ИЗ n СТРОК(ВЕРШИНЫ) И МАТРИЦЕЙ СМЕЖНОСТИ ГРАФА G(V,X) БЕЗ КРАТНЫХ РЕБЕР НАЗЫВАЮТ КВАДРАТНУЮ МАТРИЦУ A ПОРЯДКА СЛЕДУЮЩИЙ ОРГРАФ ЗАДАЕТСЯ ТАБЛИЦЕЙ ИНЦИДЕНТНОСТИ: СЛЕДУЮЩИЙ ГРАФ ЗАДАЕТСЯ ТАБЛИЦЕЙ ИНЦИДЕНТНОСТИ:
Слайды презентации

Слайд 2 Переход по слайдам осуществляется только по нажатию левой

Переход по слайдам осуществляется только по нажатию левой кнопки мыши клик

кнопки мыши клик мыши!!!
Если есть мигающая стрелка, значит

нужно нажатие левой кнопки мыши в любом месте слайд для продолжения презентации!!!!



После прочтения удалить слайд!

Слайд 3 ГРАФОМ G = (V,

ГРАФОМ G = (V, X) НАЗЫВАЕТСЯ ПАРА ДВУХ КОНЕЧНЫХ

X) НАЗЫВАЕТСЯ ПАРА ДВУХ КОНЕЧНЫХ МНОЖЕСТВ: МНОЖЕСТВО ТОЧЕК И

МНОЖЕСТВО ЛИНИЙ, СОЕДИНЯЮЩИХ НЕКОТОРЫЕ ПАРЫ ТОЧЕК.

Впервые понятие «граф» ввел в 1936 г. венгерский математик Денни Кёниг. но первая работа по теории графов принадлежала перу великого Леонарда Эйлера и была написана еще в 1736 г.

Слайд 4 ТОЧКИ НАЗЫВАЮТСЯ ВЕРШИНАМИ, ИЛИ УЗЛАМИ, ГРАФА, ЛИНИИ –

ТОЧКИ НАЗЫВАЮТСЯ ВЕРШИНАМИ, ИЛИ УЗЛАМИ, ГРАФА, ЛИНИИ – РЕБРАМИ ГРАФА.ПРИМЕРЫ ГРАФОВ

РЕБРАМИ ГРАФА.
ПРИМЕРЫ ГРАФОВ

Слайд 5 ЕСЛИ РЕБРО ГРАФА СОЕДИНЯЕТ ДВЕ ЕГО ВЕРШИНЫ, ТО

ЕСЛИ РЕБРО ГРАФА СОЕДИНЯЕТ ДВЕ ЕГО ВЕРШИНЫ, ТО ГОВОРЯТ, ЧТО ЭТО

ГОВОРЯТ, ЧТО ЭТО РЕБРО ИМ ИНЦИДЕНТНО. ДВЕ ВЕРШИНЫ ГРАФА

НАЗЫВАЮТСЯ СМЕЖНЫМИ, ЕСЛИ СУЩЕСТВУЕТ ИНЦИДЕНТНОЕ ИМ РЕБРО.

НА РИСУНКЕ СМЕЖНЫМИ ЯВЛЯЮТСЯ ВЕРШИНЫ A и B, A и C; СМЕЖНЫМИ ЯВЛЯЮТСЯ РЕБРА c и d, a и b.

ЕСЛИ ГРАФ ИМЕЕТ РЕБРО, У КОТОРОГО НАЧАЛО И КОНЕЦ СОВПАДАЮТ, ТО ЭТО РЕБРО НАЗЫВАЕТСЯ ПЕТЛЕЙ (у графа петля – q(C,C)).

ДВА РЕБРА НАЗЫВАЮТСЯ СМЕЖНЫМИ, ЕСЛИ ОНИ ИМЕЮТ ОБЩУЮ ВЕРШИНУ.

Слайд 6 КРАТНЫЕ РЕБРА
ЧИСЛО РЕБЕР, ИНЦИДЕНТНЫХ ВЕРШИНЕ A , НАЗЫВАЕТСЯ

КРАТНЫЕ РЕБРАЧИСЛО РЕБЕР, ИНЦИДЕНТНЫХ ВЕРШИНЕ A , НАЗЫВАЕТСЯ СТЕПЕНЬЮ ЭТОЙ ВЕРШИНЫ

СТЕПЕНЬЮ ЭТОЙ ВЕРШИНЫ И ОБОЗНАЧАЕТСЯ deg(A).
deg(A)= 3; deg(B) =

3; deg(C) = 4; deg(D) = 2; deg(E) = 0.

ЕСЛИ ВЕРШИНЕ ИНЦИДЕНТНА ПЕТЛЯ, ОНА ДАЕТ ВКЛАД В СТЕПЕНЬ, РАВНЫЙ ДВУМ, ТАК КАК ОБА КОНЦА ПРИХОДЯТ В ЭТУ ВЕРШИНУ.

Слайд 7 deg(E) = 0
E – ИЗОЛИРОВАННАЯ ВЕРШИНА
deg(G) = 1
deg(H)

deg(E) = 0E – ИЗОЛИРОВАННАЯ ВЕРШИНАdeg(G) = 1deg(H) = 1deg(E) =

= 1
deg(E) = 1
deg(B) = 1
deg(A) = 1
G, H,

E, B, A - ВИСЯЧИЕ ВЕРШИНЫ

Слайд 8 ТЕОРЕМА
В ГРАФЕ G(V, X) СУММА СТЕПЕНЕЙ ВСЕХ ЕГО

ТЕОРЕМАВ ГРАФЕ G(V, X) СУММА СТЕПЕНЕЙ ВСЕХ ЕГО ВЕРШИН – ЧИСЛО

ВЕРШИН – ЧИСЛО ЧЕТНОЕ, РАВНОЕ УДВОЕННОМУ ЧИСЛУ РЕБЕР ГРАФА:


ТЕОРЕМА

ЧИСЛО НЕЧЕТНЫХ ВЕРШИН ЛЮБОГО ГРАФА – ЧЕТНО.

СЛЕДСТВИЕ

НЕВОЗМОЖНО НАЧЕРТИТЬ ГРАФ С НЕЧЕТНЫМ ЧИСЛОМ НЕЧЕТНЫХ ВЕРШИН.

ВЕРШИНА НАЗЫВАЕТСЯ ЧЕТНОЙ (НЕЧЕТНОЙ), ЕСЛИ ЕЕ СТЕПЕНЬ – ЧЕТНОЕ(НЕЧЕТНОЕ) ЧИСЛО.

Слайд 9 ГРАФ НАЗЫВАЕТСЯ ПОЛНЫМ, ЕСЛИ ЛЮБЫЕ ДВЕ ЕГО РАЗЛИЧНЫЕ

ГРАФ НАЗЫВАЕТСЯ ПОЛНЫМ, ЕСЛИ ЛЮБЫЕ ДВЕ ЕГО РАЗЛИЧНЫЕ ВЕРШИНЫ СОЕДИНЕНЫ ОДНИМ

ВЕРШИНЫ СОЕДИНЕНЫ ОДНИМ И ТОЛЬКО ОДНИМ РЕБРОМ.
ДОПОЛНЕНИЕМ ГРАФА НАЗЫВАЕТСЯ

ГРАФ С ТЕМИ ЖЕ ВЕРШИНАМИ И ИМЕЮЩИЙ ТЕ И ТОЛЬКО ТЕ РЕБРА, КОТОРЫЕ НЕОБХОДИМО ДОБАВИТЬ К ИСХОДНОМУ ГРАФУ, ЧТОБЫ ОН СТАЛ ПОЛНЫМ.

ДОПОЛНЕНИЕ

Слайд 10 ДУГИ
НАЧАЛО ДУГИ (A,B)
КОНЕЦ ДУГИ
(A,B)
СТЕПЕНЬЮ ВХОДА (ВЫХОДА) ВЕРШИНЫ

ДУГИНАЧАЛО ДУГИ (A,B)КОНЕЦ ДУГИ (A,B)СТЕПЕНЬЮ ВХОДА (ВЫХОДА) ВЕРШИНЫ ОРГРАФА НАЗЫВАЕТСЯ ЧИСЛО

ОРГРАФА НАЗЫВАЕТСЯ ЧИСЛО РЕБЕР, ДЛЯ КОТОРЫХ ЭТА ВЕРШИНА ЯВЛЯЕТСЯ

КОНЦОМ (НАЧАЛОМ).

СТЕПЕНИ ВХОДА ВЕРШИН ГРАФА (см. рис.):

СТЕПЕНИ ВЫХОДА ВЕРШИН:

ОРГРАФ

ОРИЕНТИРОВАННЫЙ ГРАФ (ОРГРАФ) — ГРАФ, РЁБРАМ КОТОРОГО ПРИСВОЕНО НАПРАВЛЕНИЕ. НАПРАВЛЕННЫЕ РЁБРА ИМЕНУЮТСЯ ДУГАМИ.

Слайд 11 Последовательность ребер неориентированного графа,

Последовательность ребер неориентированного графа, в которой вторая вершина предыдущего

в которой вторая вершина предыдущего ребра совпадает с первой

вершиной следующего, называется маршрутом.
Число ребер маршрута называется длиной маршрута.

HCDFD – МАРШРУТ ДЛИНОЙ 4.

Слайд 12 Если начальная вершина маршрута совпадает с конечной,

Если начальная вершина маршрута совпадает с конечной, то такой маршрут

то такой маршрут называется замкнутым или циклом.

Если ребро встретилось только один раз, то маршрут называется цепью.

(t, s, p, r) – 4-ЦИКЛ
(t, s, u, r, t, s, p, r) – 8-ЦИКЛ
петля (q) – 1-ЦИКЛ

(t, s, p) – 3-ЦЕПЬ

Слайд 13 совпадает с началом следующего и все ребра единственны.
ЦИКЛ

совпадает с началом следующего и все ребра единственны.ЦИКЛ В ОРГРАФЕ –

В ОРГРАФЕ – ПУТЬ, У КОТОРОГО СОВПАДАЮТ НАЧАЛО И

КОНЕЦ.

(u, s, r, t) – 4-путь
(r, u) – 2-путь
(s, r, t) и (u, s, r) – 3-циклы

Путь – упорядоченная последовательность ребер ориентированного графа, в которой конец предыдущего ребра

Слайд 14 ЦЕПЬ, ПУТЬ И ЦИКЛ В ГРАФЕ НАЗЫВАЮТСЯ ПРОСТЫМИ,

ЦЕПЬ, ПУТЬ И ЦИКЛ В ГРАФЕ НАЗЫВАЮТСЯ ПРОСТЫМИ, ЕСЛИ ОНИ ПРОХОДЯТ

ЕСЛИ ОНИ ПРОХОДЯТ ЧЕРЕЗ ЛЮБУЮ ИЗ ВЕРШИН НЕ БОЛЕЕ

ОДНОГО РАЗА.
НЕОРИЕНТИРОВАННЫЙ ГРАФ НАЗЫВАЕТСЯ СВЯЗНЫМ, ЕСЛИ МЕЖДУ ЛЮБЫМИ ДВУМЯ ЕГО ВЕРШИНАМИ ЕСТЬ МАРШРУТ.

ТЕОРЕМА

ДЛЯ ТОГО, ЧТОБЫ СВЯЗНЫЙ ГРАФ ЯВЛЯЛСЯ ПРОСТЫМ ЦИКЛОМ, НЕОБХОДИМО И ДОСТАТОЧНО, ЧТОБЫ КАЖДАЯ ЕГО ВЕРШИНА ИМЕЛА СТЕПЕНЬ, РАВНУЮ 2.

Слайд 15 ГРАФ G НАЗЫВАЕТСЯ ПЛАНАРНЫМ (ПЛОСКИМ), ЕСЛИ СУЩЕСТВУЕТ ТАКОЙ

ГРАФ G НАЗЫВАЕТСЯ ПЛАНАРНЫМ (ПЛОСКИМ), ЕСЛИ СУЩЕСТВУЕТ ТАКОЙ ГРАФ G' ,

ГРАФ G' , В ИЗОБРАЖЕНИИ КОТОРОГО НА ПЛОСКОСТИ РЕБРА

ПЕРЕСЕКАЮТСЯ ТОЛЬКО В ВЕРШИНАХ.

ПЛАНАРНЫЕ ГРАФЫ

Слайд 16 ЭЙЛЕРОВЫМ ПУТЕМ (ЦИКЛОМ) ГРАФА НАЗЫВАЕТСЯ ПУТЬ (ЦИКЛ), КОТОРЫЙ

ЭЙЛЕРОВЫМ ПУТЕМ (ЦИКЛОМ) ГРАФА НАЗЫВАЕТСЯ ПУТЬ (ЦИКЛ), КОТОРЫЙ СОДЕРЖИТ ВСЕ РЕБРА

СОДЕРЖИТ ВСЕ РЕБРА ГРАФА ТОЛЬКО ОДИН РАЗ.
ГРАФ, ОБЛАДАЮЩИЙ ЭЙЛЕРОВЫМ

ЦИКЛОМ, НАЗЫВАЕТСЯ ЭЙЛЕРОВЫМ.

ТЕОРЕМА

ГРАФ ЯВЛЯЕТСЯ ЭЙЛЕРОВЫМ ТОГДА И ТОЛЬКО ТОГДА, КОГДА ОН – СВЯЗНЫЙ ГРАФ, ИМЕЮЩИЙ ВСЕ ЧЕТНЫЕ ВЕРШИНЫ.

Слайд 17 ГАМИЛЬТОНОВЫМ ПУТЕМ(ЦИКЛОМ) ГРАФА НАЗЫВАЕТСЯ ПУТЬ(ЦИКЛ), ПРОХОДЯЩИЙ ЧЕРЕЗ КАЖДУЮ

ГАМИЛЬТОНОВЫМ ПУТЕМ(ЦИКЛОМ) ГРАФА НАЗЫВАЕТСЯ ПУТЬ(ЦИКЛ), ПРОХОДЯЩИЙ ЧЕРЕЗ КАЖДУЮ ЕГО ВЕРШИНУ ТОЛЬКО

ЕГО ВЕРШИНУ ТОЛЬКО ОДИН РАЗ.
ГРАФ, СОДЕРЖАЩИЙ ГАМИЛЬТОНОВ ЦИКЛ, НАЗЫВАЕТСЯ

ГАМИЛЬТОНОВЫМ.

(C, D, A, B, E) – гамильтонов путь

Слайд 18 МАТРИЦЕЙ ИНЦИДЕНТНОСТИ ГРАФА G НАЗЫВАЮТ ТАБЛИЦУ B, СОСТОЯЩУЮ

МАТРИЦЕЙ ИНЦИДЕНТНОСТИ ГРАФА G НАЗЫВАЮТ ТАБЛИЦУ B, СОСТОЯЩУЮ ИЗ n СТРОК(ВЕРШИНЫ)

ИЗ n СТРОК(ВЕРШИНЫ) И m СТОЛБЦОВ(РЕБРА), В КОТОРОЙ:
bij =

1, ЕСЛИ ВЕРШИНА Vj ИНЦИДЕНТНА РЕБРУ Xj
bij = 0, ЕСЛИ ВЕРШИНА Vi ИНЦИДЕНТНА РЕБРУ Xi

ДЛЯ ОРИЕНТИРОВАННОГО ГРАФА:

ДЛЯ НЕОРИЕНТИРОВАННОГО ГРАФА:

bij = 1, ЕСЛИ ВЕРШИНА Vi ЯВЛЯЕТСЯ НАЧАЛОМ ДУГИ Xj
bij = 1, ЕСЛИ ВЕРШИНА Vj НЕ ИНЦИДЕНТНА ДУГЕ Xj
bij = -1, ЕСЛИ ВЕРШИНА Vi ЯВЛЯЕТСЯ КОНЦОМ ДУГИ Xj

Слайд 19 МАТРИЦЕЙ СМЕЖНОСТИ ГРАФА G(V,X) БЕЗ КРАТНЫХ РЕБЕР НАЗЫВАЮТ

МАТРИЦЕЙ СМЕЖНОСТИ ГРАФА G(V,X) БЕЗ КРАТНЫХ РЕБЕР НАЗЫВАЮТ КВАДРАТНУЮ МАТРИЦУ A

КВАДРАТНУЮ МАТРИЦУ A ПОРЯДКА n, В КОТОРОЙ:
aij = 1,

ЕСЛИ (Vi, Vj)  X
aij = 0, ЕСЛИ (Vi, Vj)  X

Слайд 20 СЛЕДУЮЩИЙ ОРГРАФ ЗАДАЕТСЯ ТАБЛИЦЕЙ ИНЦИДЕНТНОСТИ:

СЛЕДУЮЩИЙ ОРГРАФ ЗАДАЕТСЯ ТАБЛИЦЕЙ ИНЦИДЕНТНОСТИ:
  • Имя файла: graf-i-ego-elementy-osnovnye-opredeleniya.pptx
  • Количество просмотров: 20
  • Количество скачиваний: 0
- Предыдущая Жить так здорово!
Следующая - Формулы квадрата суммы и квадрата разности

Похожие презентации

Задачи на проценты 5 класс Задачи на проценты 5 класс 141
Координатная плоскость Координатная плоскость 105
Понятие одночлена. Стандартный вид одночлена Понятие одночлена. Стандартный вид одночлена 73
Презентация Число 5.Сравнение чисел -1 класс коррекционной школы Презентация Число 5.Сравнение чисел -1 класс коррекционной школы 94
Презентация к панорамному уроку для педагогического колледжа Презентация к панорамному уроку для педагогического колледжа 104
Функции и их графики Функции и их графики 91
Элективный курс Решение задач с параметром Элективный курс Решение задач с параметром 106
Презентация к занятию внеурочной деятельности по математике Древние ученые Архимед, Евклид, их вклад в развитие математики как науки презентация к уроку по математике (3 класс) по теме Презентация к занятию внеурочной деятельности по математике Древние ученые Архимед, Евклид, их вклад в развитие математики как науки презентация к уроку по математике (3 класс) по теме 134
Умножение десятичных дробей на натуральное число 5 класс Умножение десятичных дробей на натуральное число 5 класс 106
Презентация За строкой фронтового письма Презентация За строкой фронтового письма 117
Деление Деление 89
Математика Бақытты сәт сайысы 2 класс Математика Бақытты сәт сайысы 2 класс 148
урок математики в 1 классе Счет в пределах 10.(Закрепление) презентация к уроку по математике (1 класс) урок математики в 1 классе Счет в пределах 10.(Закрепление) презентация к уроку по математике (1 класс) 95
Решение задач по теме Нахождение числа по его дроби Решение задач по теме Нахождение числа по его дроби 86
Презентация по теме Понятие процента. Основные задачи на проценты Презентация по теме Понятие процента. Основные задачи на проценты 95
Интерактивный тренажёр Числа от 1 до 100. Сложение и вычитание. Часть 1 Интерактивный тренажёр Числа от 1 до 100. Сложение и вычитание. Часть 1 86
Задачи на движение Задачи на движение 110
Приёмы сложения и вычитания чисел Приёмы сложения и вычитания чисел 103
Презентация по математике: Решение неравенств с абсолютной величиной Презентация по математике: Решение неравенств с абсолютной величиной 130
ARCH and GARCH. Modeling Volatility Dynamics ARCH and GARCH. Modeling Volatility Dynamics 76
Презентация по математике на тему Противоположные числа. ФГОС (6 класс) Презентация по математике на тему Противоположные числа. ФГОС (6 класс) 131
Устный счет 4 класс Устный счет 4 класс 82
Число та цифра 6 Число та цифра 6 78
Умножение суммы на число 3 класс Умножение суммы на число 3 класс 87
Функция. График функции. Виды функций Функция. График функции. Виды функций 96
Конспект педагогического мероприятия с детьми средней группы общеразвивающей направленности по ФЭМП В гостях у Геометрика план-конспект занятия по математике (средняя группа) Конспект педагогического мероприятия с детьми средней группы общеразвивающей направленности по ФЭМП В гостях у Геометрика план-конспект занятия по математике (средняя группа) 88
Графическое решение систем уравнений Графическое решение систем уравнений 102
ИСПОЛЬЗОВАНИЕ ИНТЕРАКТИВНОЙ ДОСКИ НА УРОКЕ МАТЕМАТИКИ ИСПОЛЬЗОВАНИЕ ИНТЕРАКТИВНОЙ ДОСКИ НА УРОКЕ МАТЕМАТИКИ 112
Открытый урок по математике Корень. Решение уравнений. план-конспект урока по математике (4 класс) Открытый урок по математике Корень. Решение уравнений. план-конспект урока по математике (4 класс) 85
Алгоритм нахождения производной Алгоритм нахождения производной 78