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

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

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

Получите профессию

Копирайтер

за 6 месяцев

Пройти курс

Рабочие листы
к вашим урокам

Скачать

Методические разработки к Вашему уроку:

Получите новую специальность за 3 месяца

Культуролог-аниматор

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

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

    1 слайд

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

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

    2 слайд

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

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

    3 слайд

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

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

    4 слайд

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


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

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

    5 слайд

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

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

    6 слайд

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

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

    7 слайд

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

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

    8 слайд

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

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

    9 слайд

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

  • 1. Что такое граф?Взвешенный граф – граф, в котором ребрам поставлены в соотв...

    10 слайд

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

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

    11 слайд

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

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

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

    12 слайд

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

    (1→6): 1→2→4→6
    (1→6): 1→2→4→5→6
    (1→6): 1→2→3→6

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

    13 слайд

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


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

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

    14 слайд

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

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

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

    15 слайд

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

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

    16 слайд

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




    Циклический Ациклический



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

    17 слайд

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






    Несвязный граф


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

    18 слайд

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




    Компонент 1: {a,b,c,d,e}
    Компонент 2: {f,g,h,i}





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

    19 слайд

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








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

    20 слайд

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








  • 1. Что такое граф?Плотный граф – граф, в котором количество ребер близко к ма...

    21 слайд

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




    Плотный Разреженный

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




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

    22 слайд

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




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

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

    23 слайд

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





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

    24 слайд

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




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





Матрица смежности представляе...

    25 слайд

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





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




  • 2. Как хранить графы?Выбор способа хранения графа зависит, как правило, от ис...

    26 слайд

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




  • 2. Как хранить графы?

    27 слайд

    2. Как хранить графы?




Получите профессию

Фитнес-тренер

за 6 месяцев

Пройти курс

Рабочие листы
к вашим урокам

Скачать

Скачать материал

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

6 625 421 материал в базе

Скачать материал

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

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

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

Авторизуйтесь, чтобы задавать вопросы.

  • Скачать материал
    • 06.12.2015 3417
    • PPTX 560.7 кбайт
    • 27 скачиваний
    • Оцените материал:
  • Настоящий материал опубликован пользователем Скряго Ольга Сергеевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

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

    Удалить материал
  • Автор материала

    Скряго Ольга Сергеевна
    Скряго Ольга Сергеевна
    • На сайте: 8 лет и 3 месяца
    • Подписчики: 0
    • Всего просмотров: 34363
    • Всего материалов: 15

Ваша скидка на курсы

40%
Скидка для нового слушателя. Войдите на сайт, чтобы применить скидку к любому курсу
Курсы со скидкой

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

Няня

Няня

500/1000 ч.

Подать заявку О курсе

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

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

Преподаватель информационных технологий

300/600 ч.

от 7900 руб. от 3950 руб.
Подать заявку О курсе
  • Сейчас обучается 188 человек из 53 регионов

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

Разработка и сопровождение требований и технических заданий на разработку и модернизацию систем и подсистем малого и среднего масштаба и сложности

Системный аналитик

600 ч.

9840 руб. 5900 руб.
Подать заявку О курсе
  • Сейчас обучается 63 человека из 33 регионов

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

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

Учитель информатики

300/600 ч.

от 7900 руб. от 3950 руб.
Подать заявку О курсе
  • Сейчас обучается 487 человек из 71 региона

Мини-курс

Основы налогообложения и формирования налогооблагаемых показателей

2 ч.

780 руб. 390 руб.
Подать заявку О курсе

Мини-курс

Практические аспекты работы логопеда: методы и приемы в логоритмике

2 ч.

780 руб. 390 руб.
Подать заявку О курсе

Мини-курс

Этапы развития речи: от первых звуков до полноценной коммуникации

4 ч.

780 руб. 390 руб.
Подать заявку О курсе
  • Сейчас обучается 103 человека из 43 регионов