Математический аппарат для построения компьютерных сетей что это

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

В настоящий момент дополнительные накопительные скидки (от 2% до 25%) предоставляются 58.119 образовательным учреждениям . Чтобы узнать, какая скидка действует для всех сотрудников Вашего образовательного учреждения, войдите в свой личный кабинет «Инфоурок».

Курс повышения квалификации

Методы и инструменты современного моделирования

К данной скидке мы можем добавить скидку Вашего образовательного учреждения (она зависит от того, сколько Ваших коллег прошло курсы «Инфоурок»)

В настоящий момент дополнительные накопительные скидки (от 2% до 25%) предоставляются 58.119 образовательным учреждениям . Чтобы узнать, какая скидка действует для всех сотрудников Вашего образовательного учреждения, войдите в свой личный кабинет «Инфоурок».

Курс профессиональной переподготовки

Информатика: теория и методика преподавания в профессиональном образовании

К данной скидке мы можем добавить скидку Вашего образовательного учреждения (она зависит от того, сколько Ваших коллег прошло курсы «Инфоурок»)

В настоящий момент дополнительные накопительные скидки (от 2% до 25%) предоставляются 58.119 образовательным учреждениям . Чтобы узнать, какая скидка действует для всех сотрудников Вашего образовательного учреждения, войдите в свой личный кабинет «Инфоурок».

Основы работы с программой PowerPoint

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

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

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

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

Если вершины соединены ребром, они называются смежными.

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

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

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

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

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

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

Если все вершины
различны
– путь называется простым.

12 слайд 1. Что такое граф?
Направленный путь от вершины a к вершине b – последовательность смежных вершин в ориентированном графе, которая начинается от вершины a и заканчивается в вершине b.

13 слайд 1. Что такое граф?
Длина пути — количество ребер, через которые нужно пройти (количество вершин – 1).

Длина простого пути
№1 0→6: 4
№ 2 0→6: 5

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

Длина простого пути
№1 0→6: 5+8+6+7=26
№2 0→6: 5+2+4+6+7=24

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

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

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

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

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

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

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

22 слайд 2. Как хранить графы?
Граф хранится в виде:

Матрицы смежности Списков смежности

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

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

25 слайд 2. Как хранить графы?
Для взвешенного графа

Матрица смежности представляет собой матрицу весов. На пересечении a и b ставится вес ребра, или ∞, если ребра нет.
В связном списке появляется поле для обозначения веса ребра.

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

27 слайд 2. Как хранить графы?

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 311 983 материала в базе

Другие материалы

Вам будут интересны эти курсы:

• Курс повышения квалификации «Информационные технологии в деятельности учителя физики»
• Курс повышения квалификации «Внедрение системы компьютерной математики в процесс обучения математике в старших классах в рамках реализации ФГОС»
• Курс повышения квалификации «Облачные технологии в образовании»
• Курс повышения квалификации «Сетевые и дистанционные (электронные) формы обучения в условиях реализации ФГОС по ТОП-50»
• Курс повышения квалификации «Развитие информационно-коммуникационных компетенций учителя в процессе внедрения ФГОС: работа в Московской электронной школе»
• Курс профессиональной переподготовки «Информационные технологии в профессиональной деятельности: теория и методика преподавания в образовательной организации»
• Курс повышения квалификации «Специфика преподавания информатики в начальных классах с учетом ФГОС НОО»
• Курс повышения квалификации «Введение в программирование на языке С (СИ)»
• Курс профессиональной переподготовки «Управление в сфере информационных технологий в образовательной организации»
• Курс повышения квалификации «Специфика преподавания дисциплины «Информационные технологии» в условиях реализации ФГОС СПО по ТОП-50»
• Курс повышения квалификации «Современные языки программирования интегрированной оболочки Microsoft Visual Studio C# NET., C++. NET, VB.NET. с использованием структурного и объектно-ориентированного методов разработки корпоративных систем»

Оставьте свой комментарий

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал. Удалить материал

Автор материала

• На сайте: 7 лет и 7 месяцев
• Подписчики: 0
• Всего просмотров: 32812
• Всего материалов: 15

41 минута

56 минут

56 минут

• 

• 

• 

Подарочные сертификаты

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

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.

Источник