PPt4Web Хостинг презентаций

Главная / Математика / Графа и его элементы
X Код для использования на сайте:

Скопируйте этот код и вставьте его на свой сайт

X

Чтобы скачать данную презентацию, порекомендуйте, пожалуйста, её своим друзьям в любой соц. сети.

После чего скачивание начнётся автоматически!

Кнопки:

Презентация на тему: Графа и его элементы


Скачать эту презентацию

Презентация на тему: Графа и его элементы


Скачать эту презентацию



№ слайда 1 ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ГРАФА И ЕГО ЭЛЕМЕНТОВ
Описание слайда:

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ГРАФА И ЕГО ЭЛЕМЕНТОВ

№ слайда 2 ГРАФОМ G = (V, X) НАЗЫВАЕТСЯ ПАРА ДВУХ КОНЕЧНЫХ МНОЖЕСТВ: МНОЖЕСТВО ТОЧЕК И МНОЖ
Описание слайда:

ГРАФОМ G = (V, X) НАЗЫВАЕТСЯ ПАРА ДВУХ КОНЕЧНЫХ МНОЖЕСТВ: МНОЖЕСТВО ТОЧЕК И МНОЖЕСТВО ЛИНИЙ, СОЕДИНЯЮЩИХ НЕКОТОРЫЕ ПАРЫ ТОЧЕК. ВПЕРВЫЕ ПОНЯТИЕ «ГРАФ» ВВЕЛ В 1936 г. ВЕНГЕРСКИЙ МАТЕМАТИК ДЕННИ КЁНИГ. НО ПЕРВАЯ РАБОТА ПО ТЕОРИИ ГРАФОВ ПРИНАДЛЕЖАЛА ПЕРУ ВЕЛИКОГО ЛЕОНАРДА ЭЙЛЕРА И БЫЛА НАПИСАНА ЕЩЕ В 1736 г.

№ слайда 3 ТОЧКИ НАЗЫВАЮТСЯ ВЕРШИНАМИ, ИЛИ УЗЛАМИ, ГРАФА, ЛИНИИ – РЕБРАМИ ГРАФА. ПРИМЕРЫ ГР
Описание слайда:

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

№ слайда 4 ЕСЛИ РЕБРО ГРАФА СОЕДИНЯЕТ ДВЕ ЕГО ВЕРШИНЫ, ТО ГОВОРЯТ, ЧТО ЭТО РЕБРО ИМ ИНЦИДЕН
Описание слайда:

ЕСЛИ РЕБРО ГРАФА СОЕДИНЯЕТ ДВЕ ЕГО ВЕРШИНЫ, ТО ГОВОРЯТ, ЧТО ЭТО РЕБРО ИМ ИНЦИДЕНТНО. ДВЕ ВЕРШИНЫ ГРАФА НАЗЫВАЮТСЯ СМЕЖНЫМИ, ЕСЛИ СУЩЕСТВУЕТ ИНЦИДЕНТНОЕ ИМ РЕБРО. ЕСЛИ ГРАФ ИМЕЕТ РЕБРО, У КОТОРОГО НАЧАЛО И КОНЕЦ СОВПАДАЮТ, ТО ЭТО РЕБРО НАЗЫВАЕТСЯ ПЕТЛЕЙ(у графа петля – q(C,C)). НА РИСУНКЕ СМЕЖНЫМИ ЯВЛЯЮТСЯ ВЕРШИНЫ A и B, A и C ; СМЕЖНЫМИ ЯВЛЯЮТСЯ РЕБРА c и d, a и b. ДВА РЕБРА НАЗЫВАЮТСЯ СМЕЖНЫМИ, ЕСЛИ ОНИ ИМЕЮТ ОБЩУЮ ВЕРШИНУ.

№ слайда 5 ЧИСЛО РЕБЕР, ИНЦИДЕНТНЫХ ВЕРШИНЕ A , НАЗЫВАЕТСЯ СТЕПЕНЬЮ ЭТОЙ ВЕРШИНЫ И ОБОЗНАЧА
Описание слайда:

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

№ слайда 6 E – ИЗОЛИРОВАННАЯ ВЕРШИНА
Описание слайда:

E – ИЗОЛИРОВАННАЯ ВЕРШИНА

№ слайда 7 В ГРАФЕ G(V, X) СУММА СТЕПЕНЕЙ ВСЕХ ЕГО ВЕРШИН – ЧИСЛО ЧЕТНОЕ, РАВНОЕ УДВОЕННОМУ
Описание слайда:

В ГРАФЕ G(V, X) СУММА СТЕПЕНЕЙ ВСЕХ ЕГО ВЕРШИН – ЧИСЛО ЧЕТНОЕ, РАВНОЕ УДВОЕННОМУ ЧИСЛУ РЕБЕР ГРАФА: ВЕРШИНА НАЗЫВАЕТСЯ ЧЕТНОЙ (НЕЧЕТНОЙ), ЕСЛИ ЕЕ СТЕПЕНЬ – ЧЕТНОЕ(НЕЧЕТНОЕ) ЧИСЛО. ЧИСЛО НЕЧЕТНЫХ ВЕРШИН ЛЮБОГО ГРАФА – ЧЕТНО. СЛЕДСТВИЕ НЕВОЗМОЖНО НАЧЕРТИТЬ ГРАФ С НЕЧЕТНЫМ ЧИСЛОМ НЕЧЕТНЫХ ВЕРШИН.

№ слайда 8 ГРАФ НАЗЫВАЕТСЯ ПОЛНЫМ, ЕСЛИ ЛЮБЫЕ ДВЕ ЕГО РАЗЛИЧНЫЕ ВЕРШИНЫ СОЕДИНЕНЫ ОДНИМ И Т
Описание слайда:

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

№ слайда 9 ОРГРАФ СТЕПЕНИ ВХОДА ВЕРШИН ГРАФА (см. рис.): СТЕПЕНИ ВЫХОДА ВЕРШИН: СТЕПЕНЬЮ ВХ
Описание слайда:

ОРГРАФ СТЕПЕНИ ВХОДА ВЕРШИН ГРАФА (см. рис.): СТЕПЕНИ ВЫХОДА ВЕРШИН: СТЕПЕНЬЮ ВХОДА (ВЫХОДА) ВЕРШИНЫ ОРГРАФА НАЗЫВАЕТСЯ ЧИСЛО РЕБЕР, ДЛЯ КОТОРЫХ ЭТА ВЕРШИНА ЯВЛЯЕТСЯ КОНЦОМ (НАЧАЛОМ).

№ слайда 10 ПОСЛЕДОВАТЕЛЬНОСТЬ РЕБЕР НЕОРИЕНТИРОВАННОГО ГРАФА, В КОТОРОЙ ВТОРАЯ ВЕРШИНА ПРЕД
Описание слайда:

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

№ слайда 11 ПУТЬ – УПОРЯДОЧЕННАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ РЕБЕР ОРИЕНТИРОВАННОГО ГРАФА, В КОТОРОЙ
Описание слайда:

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

№ слайда 12 ЦЕПЬ, ПУТЬ И ЦИКЛ В ГРАФЕ НАЗЫВАЮТСЯ ПРОСТЫМИ, ЕСЛИ ОНИ ПРОХОДЯТ ЧЕРЕЗ ЛЮБУЮ ИЗ
Описание слайда:

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

№ слайда 13 ГРАФ G НАЗЫВАЕТСЯ ПЛАНАРНЫМ(ПЛОСКИМ), ЕСЛИ СУЩЕСТВУЕТ ТАКОЙ ГРАФ G' , В ИЗОБРАЖЕ
Описание слайда:

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

№ слайда 14 ЭЙЛЕРОВЫМ ПУТЕМ(ЦИКЛОМ) ГРАФА НАЗЫВАЕТСЯ ПУТЬ(ЦИКЛ), КОТОРЫЙ СОДЕРЖИТ ВСЕ РЕБРА
Описание слайда:

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

№ слайда 15 ГАМИЛЬТОНОВЫМ ПУТЕМ(ЦИКЛОМ) ГРАФА НАЗЫВАЕТСЯ ПУТЬ(ЦИКЛ), ПРОХОДЯЩИЙ ЧЕРЕЗ КАЖДУЮ
Описание слайда:

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

№ слайда 16 МАТРИЦЕЙ ИНЦИДЕНТНОСТИ ГРАФА G НАЗЫВАЮТ ТАБЛИЦУ B, СОСТОЯЩУЮ ИЗ n СТРОК(ВЕРШИНЫ)
Описание слайда:

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

№ слайда 17 МАТРИЦЕЙ СМЕЖНОСТИ ГРАФА G(V,X) БЕЗ КРАТНЫХ РЕБЕР НАЗЫВАЮТ КВАДРАТНУЮ МАТРИЦУ A
Описание слайда:

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

№ слайда 18 ЗАДАЙТЕ СЛЕДУЮЩИЙ ОРГРАФ ТАБЛИЦЕЙ ИНЦИДЕНТНОСТИ
Описание слайда:

ЗАДАЙТЕ СЛЕДУЮЩИЙ ОРГРАФ ТАБЛИЦЕЙ ИНЦИДЕНТНОСТИ

№ слайда 19 ЗАДАЙТЕ СЛЕДУЮЩИЙ ГРАФ ТАБЛИЦЕЙ СМЕЖНОСТИ
Описание слайда:

ЗАДАЙТЕ СЛЕДУЮЩИЙ ГРАФ ТАБЛИЦЕЙ СМЕЖНОСТИ

№ слайда 20 Автор: Оркина Марина Александровна, преподаватель ГОУ СПО «Зубово-Полянский педа
Описание слайда:

Автор: Оркина Марина Александровна, преподаватель ГОУ СПО «Зубово-Полянский педагогический колледж» Республика Мордовия

Скачать эту презентацию


Презентации по предмету
Презентации из категории
Лучшее на fresher.ru