Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Презентации / Презентация по теме «Графы (основные понятия)» для МДК 01.02 Математический аппарат для построения компьютерных сетей
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 26 апреля.

Подать заявку на курс
  • Информатика

Презентация по теме «Графы (основные понятия)» для МДК 01.02 Математический аппарат для построения компьютерных сетей

библиотека
материалов
Тема урока: «Графы (основные понятия)» МДК 01.02 Математический аппарат для п...
Что такое граф? Как хранить графы?
1. Что такое граф? Граф – набор точек (вершин, узлов), часть из которых соеди...
1. Что такое граф? Граф определяется парой множеств: Конечное множество элеме...
1. Что такое граф?
1. Что такое граф? Ориентированный граф (орграф, диграф) – граф, ребрам котор...
1. Что такое граф? Для ребра (a,c) говорят, что ребро выходит из вершины a и...
1. Что такое граф? Петля – ребро, которое соединяет вершину саму с собой.
1. Что такое граф? Полный граф – граф, в котором каждая пара вершин соединена...
1. Что такое граф? Взвешенный граф – граф, в котором ребрам поставлены в соот...
1. Что такое граф? Путь от вершины a к вершине b –последовательность смежных...
1. Что такое граф? Направленный путь от вершины a к вершине b – последователь...
1. Что такое граф? Длина пути - количество ребер, через которые нужно пройти...
1. Что такое граф? Длина пути во взвешенном графе – сумма весов ребер, через...
1. Что такое граф? Кратчайший путь в графе – путь с наименьшим количеством ре...
1. Что такое граф? Цикл – простой путь, который начинается и заканчивается в...
1. Что такое граф? Связный граф – граф, в котором для любой пары вершин есть...
1. Что такое граф? Связный компонент графа – максимальный связный подграф, ко...
1. Что такое граф? Сильно связный граф – ориентированный граф, в котором для...
1. Что такое граф? Сильно связный компонент графа – максимально связный подгр...
1. Что такое граф? Плотный граф – граф, в котором количество ребер близко к м...
2. Как хранить графы? Граф хранится в виде: Матрицы смежности Списков смежности
2. Как хранить графы? Матрица смежности для графа с n вершинами состоит из n*...
2. Как хранить графы? Списки смежности – массив связанных списков. Для n верш...
2. Как хранить графы? Для взвешенного графа Матрица смежности представляет со...
2. Как хранить графы? Выбор способа хранения графа зависит, как правило, от и...
2. Как хранить графы? Задача Оптимальныйвариант Проверкана вхождение ребра (x...
27 1

"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs

Описание презентации по отдельным слайдам:

№ слайда 1 Тема урока: «Графы (основные понятия)» МДК 01.02 Математический аппарат для п
Описание слайда:

Тема урока: «Графы (основные понятия)» МДК 01.02 Математический аппарат для построения компьютерных сетей Смоленск 2015

№ слайда 2 Что такое граф? Как хранить графы?
Описание слайда:

Что такое граф? Как хранить графы?

№ слайда 3 1. Что такое граф? Граф – набор точек (вершин, узлов), часть из которых соеди
Описание слайда:

1. Что такое граф? Граф – набор точек (вершин, узлов), часть из которых соединена отрезками (ребрами, дугами).

№ слайда 4 1. Что такое граф? Граф определяется парой множеств: Конечное множество элеме
Описание слайда:

1. Что такое граф? Граф определяется парой множеств: Конечное множество элементов V (вершин) Конечное множество элементов (ребер) E, каждый элемент содержит пару вершин (например (a,b)) Если вершины соединены ребром, они называются смежными.

№ слайда 5 1. Что такое граф?
Описание слайда:

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

№ слайда 6 1. Что такое граф? Ориентированный граф (орграф, диграф) – граф, ребрам котор
Описание слайда:

1. Что такое граф? Ориентированный граф (орграф, диграф) – граф, ребрам которого задано направление.

№ слайда 7 1. Что такое граф? Для ребра (a,c) говорят, что ребро выходит из вершины a и
Описание слайда:

1. Что такое граф? Для ребра (a,c) говорят, что ребро выходит из вершины a и входит в вершину с

№ слайда 8 1. Что такое граф? Петля – ребро, которое соединяет вершину саму с собой.
Описание слайда:

1. Что такое граф? Петля – ребро, которое соединяет вершину саму с собой.

№ слайда 9 1. Что такое граф? Полный граф – граф, в котором каждая пара вершин соединена
Описание слайда:

1. Что такое граф? Полный граф – граф, в котором каждая пара вершин соединена ребрами.

№ слайда 10 1. Что такое граф? Взвешенный граф – граф, в котором ребрам поставлены в соот
Описание слайда:

1. Что такое граф? Взвешенный граф – граф, в котором ребрам поставлены в соответствия какие-то числовые значения. Числа называются весами, ценами, стоимостями и т.д.

№ слайда 11 1. Что такое граф? Путь от вершины a к вершине b –последовательность смежных
Описание слайда:

1. Что такое граф? Путь от вершины a к вершине b –последовательность смежных вершин, которая начинается от вершины a и заканчивается в вершине b. (0→6): 0→1→2→4→6 (0→6): 0→1→3→2→4→6 Если все вершины различны – путь называется простым.

№ слайда 12 1. Что такое граф? Направленный путь от вершины a к вершине b – последователь
Описание слайда:

1. Что такое граф? Направленный путь от вершины a к вершине b – последовательность смежных вершин в ориентированном графе, которая начинается от вершины a и заканчивается в вершине b. (1→6): 1→2→4→6 (1→6): 1→2→4→5→6 (1→6): 1→2→3→6

№ слайда 13 1. Что такое граф? Длина пути - количество ребер, через которые нужно пройти
Описание слайда:

1. Что такое граф? Длина пути - количество ребер, через которые нужно пройти (количество вершин – 1). Длина простого пути №1 0→6: 4 № 2 0→6: 5

№ слайда 14 1. Что такое граф? Длина пути во взвешенном графе – сумма весов ребер, через
Описание слайда:

1. Что такое граф? Длина пути во взвешенном графе – сумма весов ребер, через которые прошел путь. Длина простого пути №1 0→6: 5+8+6+7=26 №2 0→6: 5+2+4+6+7=24

№ слайда 15 1. Что такое граф? Кратчайший путь в графе – путь с наименьшим количеством ре
Описание слайда:

1. Что такое граф? Кратчайший путь в графе – путь с наименьшим количеством ребер. Кратчайший путь во взвешенном графе – путь с минимальным суммарным весом. Кратчайший путь в графе: №1 Кратчайший путь во взвешенном графе: №2

№ слайда 16 1. Что такое граф? Цикл – простой путь, который начинается и заканчивается в
Описание слайда:

1. Что такое граф? Цикл – простой путь, который начинается и заканчивается в одной и той же вершине. Граф, в котором нет циклов – ациклический. Если циклы есть – граф циклический. Циклический Ациклический

№ слайда 17 1. Что такое граф? Связный граф – граф, в котором для любой пары вершин есть
Описание слайда:

1. Что такое граф? Связный граф – граф, в котором для любой пары вершин есть путь (не обязательно простой), который их соединяет. Несвязный граф

№ слайда 18 1. Что такое граф? Связный компонент графа – максимальный связный подграф, ко
Описание слайда:

1. Что такое граф? Связный компонент графа – максимальный связный подграф, который нельзя расширить за счет включения вершин, смежных, с какой-либо вершиной компонента. Компонент 1: {a,b,c,d,e} Компонент 2: {f,g,h,i}

№ слайда 19 1. Что такое граф? Сильно связный граф – ориентированный граф, в котором для
Описание слайда:

1. Что такое граф? Сильно связный граф – ориентированный граф, в котором для любой пары вершин есть путь (не обязательно простой), который их соединяет.

№ слайда 20 1. Что такое граф? Сильно связный компонент графа – максимально связный подгр
Описание слайда:

1. Что такое граф? Сильно связный компонент графа – максимально связный подграф, в котором любая вершина достижима из любой другой вершины.

№ слайда 21 1. Что такое граф? Плотный граф – граф, в котором количество ребер близко к м
Описание слайда:

1. Что такое граф? Плотный граф – граф, в котором количество ребер близко к максимальному ((n2-n)/2) Разреженный граф – граф, в котором количество ребер далеко от максимального. Плотный Разреженный

№ слайда 22 2. Как хранить графы? Граф хранится в виде: Матрицы смежности Списков смежности
Описание слайда:

2. Как хранить графы? Граф хранится в виде: Матрицы смежности Списков смежности

№ слайда 23 2. Как хранить графы? Матрица смежности для графа с n вершинами состоит из n*
Описание слайда:

2. Как хранить графы? Матрица смежности для графа с n вершинами состоит из n*n элементов. Строка – исходная вершина, столбец – входящая. Если существует ребро, которое соединяет вершины a и b, тогда на пересечении строки a и столбца b ставится 1, если ребра нет – ставится 0. Для неориентированного графа матрица смежности симметрична главной диагонали.

№ слайда 24 2. Как хранить графы? Списки смежности – массив связанных списков. Для n верш
Описание слайда:

2. Как хранить графы? Списки смежности – массив связанных списков. Для n вершин массив будет состоять из n элементов. Каждый элемент массива – вершина, откуда выходит ребро. Каждый элемент списка – вершина, в которую входит ребро. Связный список формируется в произвольном порядке

№ слайда 25 2. Как хранить графы? Для взвешенного графа Матрица смежности представляет со
Описание слайда:

2. Как хранить графы? Для взвешенного графа Матрица смежности представляет собой матрицу весов. На пересечении a и b ставится вес ребра, или ∞, если ребра нет. В связном списке появляется поле для обозначения веса ребра.

№ слайда 26 2. Как хранить графы? Выбор способа хранения графа зависит, как правило, от и
Описание слайда:

2. Как хранить графы? Выбор способа хранения графа зависит, как правило, от используемых алгоритмов. В остальных случаях, если граф плотный – лучше использовать матрицу смежности. Если граф разреженный – лучше использовать списки смежности.

№ слайда 27 2. Как хранить графы? Задача Оптимальныйвариант Проверкана вхождение ребра (x
Описание слайда:

2. Как хранить графы? Задача Оптимальныйвариант Проверкана вхождение ребра (x,y)в граф Матрица смежности Определениестепени вершины Спискисмежности Объемпамяти для небольших графов Спискисмежности (m-n), Матрица смежности (n2) Объем памяти для больших графов Матрицасмежности Вставка или удаление ребра МатрицасмежностиO(1), Списка смежностиO(d) Обход графа Спискисмежности Ѳ(m+n) Матрица смежности Ѳ(n2) Лучше для решения большинствапроблем Спискисмежности

Автор
Дата добавления 06.12.2015
Раздел Информатика
Подраздел Презентации
Просмотров303
Номер материала ДВ-234871
Получить свидетельство о публикации

"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ


Идёт приём заявок на международный конкурс по математике "Весенний марафон" для учеников 1-11 классов и дошкольников

Уникальность конкурса в преимуществах для учителей и учеников:

1. Задания подходят для учеников с любым уровнем знаний;
2. Бесплатные наградные документы для учителей;
3. Невероятно низкий орг.взнос - всего 38 рублей;
4. Публикация рейтинга классов по итогам конкурса;
и многое другое...

Подайте заявку сейчас - https://urokimatematiki.ru

Похожие материалы

Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.
Специальное предложение
Вверх