1154589
столько раз учителя, ученики и родители
посетили сайт «Инфоурок»
за прошедшие 24 часа
+Добавить материал
и получить бесплатное
свидетельство о публикации
в СМИ №ФС77-60625 от 20.01.2015
Дистанционные курсы профессиональной переподготовки и повышения квалификации для педагогов

Дистанционные курсы для педагогов - курсы профессиональной переподготовки от 1.410 руб.;
- курсы повышения квалификации от 430 руб.
Московские документы для аттестации

ВЫБРАТЬ КУРС СО СКИДКОЙ ДО 90%

ВНИМАНИЕ: Скидка действует ТОЛЬКО до конца апреля!

(Лицензия на осуществление образовательной деятельности №038767 выдана ООО "Столичный учебный центр", г.Москва)

ИнфоурокИнформатикаПрезентацииПрезентация по информатике "Введение в теорию графов" (11 класс)

Презентация по информатике "Введение в теорию графов" (11 класс)

Выберите документ из архива для просмотра:

Выбранный для просмотра документ Введение в теорию графов.pptx

библиотека
материалов
Введение в теорию графов
Задача прокладки коммуникаций 2 3 4 1 5
Определение графа Граф - это множество точек или вершин и множество линий или...
Основные понятия теории графов Граф задается с помощью пары множеств: G=(V,R)...
Граф G: Смежные вершины – это вершины, которые соединены рёбрами. V2 V3 V1 V4...
Граф G: Мощность множеств V и R- количество вершин и количество ребер соответ...
Граф G: Ребро и любая из его двух вершин называются инцидентными V2 V3 V1 V4...
Граф G: Степень вершины – количество инцидентных ей рёбер. V2 V3 V1 V4 V5 R12...
Граф G: Маршрут графа – это последовательность чередующихся вершин и рёбер. З...
Задание 1. (А1 А4); (А4 А5). (А1 А2); (А2 А4); (А4 А5). (А1 А4); (А4 А2); (А2...
a) 4 ребра; b) 6 ребер; c) 5 ребер; d) 10 ребер. Какие из этих циклов являют...
ОТВЕТ (AB, BC, CE, EA), (CD, DA, AB, BC), (EB, BC, CD, DE) и т.д. – простые ц...
Граф G: Маршрут называется простой цепью, если все его вершины и рёбра – разл...
(А1 А4); (А4 А5). (А1 А2); (А2 А4); (А4 А5). (А1 А4); (А4 А2); (А2 А1); (А1 А...
Граф G: Граф является связным, если каждая его вершина достижима из другой ве...
Граф G: Вершины, не имеющие инцидентных рёбер, называются изолированными верш...
Граф, состоящий из «изолированных» вершин, называется нулевым графом Рис. 1....
Графы, в которых не построены все возможные ребра, называются неполными графа...
Заметим, что если полный граф имеет n вершин, то количество ребер равно n(n-...
Задание 4. Построить граф по заданному условию: В соревнованиях по футболу уч...
Изображение графа Один и тот же граф может выглядеть на рисунках по-разному....
Задание 5. Определить изображают ли фигуры на рисунке один и тот же граф или...
 Логические задачи
Известно, что в настоящий момент: Ваня сыграл шесть партий; Толя сыграл пять...
Число в скобках называют степенью вершины, оно показывает сколько ребер выхо...
Начать построение ребер следует с вершины В, так как это единственная вершин...
Для вершин В и Ж построены все возможные ребра Ваня (6) Толя (5) Леша (3) Ди...
Теперь однозначно определяются ребра вершины Т. С учетом ребра ВТ надо постр...
Все возможные ребра теперь построены для вершин Ж, В, Т, а также для вершин...
ОТВЕТ: Леша играл с Толей, Ваней и Димой Ваня (6) Толя (5) Леша (3) Дима (3)...
Домашнее задание §1.10.1 стр.112-114. Выучить все определения.
Ориентированный граф Граф называется ориентированным (или орграфом), если нек...
Взвешенный граф Взвешенный граф (сеть) – граф, ребрам или дугам которого пост...
Способы описания графа матрица инциденций, матрица смежности, списки связи, п...
Матрица смежности Это двумерный массив N*N.
Домашнее задание §1.10.1 стр.114-115. Выучить все определения. Решить задачи...

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

1 слайд Введение в теорию графов
Описание слайда:

Введение в теорию графов

2 слайд Задача прокладки коммуникаций 2 3 4 1 5
Описание слайда:

Задача прокладки коммуникаций 2 3 4 1 5

3 слайд Определение графа Граф - это множество точек или вершин и множество линий или
Описание слайда:

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

4 слайд Основные понятия теории графов Граф задается с помощью пары множеств: G=(V,R)
Описание слайда:

Основные понятия теории графов Граф задается с помощью пары множеств: G=(V,R) где V – множество (совокупность) вершин; R – множество рёбер, соединяющих пары вершин. V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15 Множества V и R являются конечными, если можно перечислить все ребра и все вершины графа.

5 слайд Граф G: Смежные вершины – это вершины, которые соединены рёбрами. V2 V3 V1 V4
Описание слайда:

Граф G: Смежные вершины – это вершины, которые соединены рёбрами. V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15

6 слайд Граф G: Мощность множеств V и R- количество вершин и количество ребер соответ
Описание слайда:

Граф G: Мощность множеств V и R- количество вершин и количество ребер соответственно. V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15 Мощность графа G: 5 вершин и 8 рёбер

7 слайд Граф G: Ребро и любая из его двух вершин называются инцидентными V2 V3 V1 V4
Описание слайда:

Граф G: Ребро и любая из его двух вершин называются инцидентными V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15

8 слайд Граф G: Степень вершины – количество инцидентных ей рёбер. V2 V3 V1 V4 V5 R12
Описание слайда:

Граф G: Степень вершины – количество инцидентных ей рёбер. V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15 Степень V3 – 3 Степень V5 – 4

9 слайд Граф G: Маршрут графа – это последовательность чередующихся вершин и рёбер. З
Описание слайда:

Граф G: Маршрут графа – это последовательность чередующихся вершин и рёбер. Замкнутый (циклический) маршрут – тот маршрут, у которого начальная и конечная вершины совпадают. V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15 V3R34V4R14V1R12V2R23V3 V3R35V5R25V2R12V1 Простым циклом в графе называется цикл, не проходящий ни через одну из вершин графа более одного раза.

10 слайд Задание 1. (А1 А4); (А4 А5). (А1 А2); (А2 А4); (А4 А5). (А1 А4); (А4 А2); (А2
Описание слайда:

Задание 1. (А1 А4); (А4 А5). (А1 А2); (А2 А4); (А4 А5). (А1 А4); (А4 А2); (А2 А1); (А1 А4); (А4, А5). (А1 А4); (А4 А2); (А2 А1); (А1 А3); (А3 А4); (А4, А5). Определить какая из перечисленных последовательностей маршрутом не является. ОТВЕТ Третья последовательность (А1 А4); (А4 А2); (А2 А1); (А1 А4); (А4, А5).

11 слайд a) 4 ребра; b) 6 ребер; c) 5 ребер; d) 10 ребер. Какие из этих циклов являют
Описание слайда:

a) 4 ребра; b) 6 ребер; c) 5 ребер; d) 10 ребер. Какие из этих циклов являются простыми? Назовите в графе циклы, содержащие: ОТВЕТ Задание 2.

12 слайд ОТВЕТ (AB, BC, CE, EA), (CD, DA, AB, BC), (EB, BC, CD, DE) и т.д. – простые ц
Описание слайда:

ОТВЕТ (AB, BC, CE, EA), (CD, DA, AB, BC), (EB, BC, CD, DE) и т.д. – простые циклы. (DB, BE, EA, AB, BC, CD), (EC, CA, AB, BC, CD, DE) и т.д. – циклы. (AB, BC, CD, DE, EA), (AC, CE, EB, BD, DA) и т.д. – простые циклы. (AC, CE, EB, BD, DA, AB, BC, CD, DE, EA), (EB, BD, DA, AC, CE, EA, AB, BC, CD, DE) и т.д. – циклы. Решение:

13 слайд Граф G: Маршрут называется простой цепью, если все его вершины и рёбра – разл
Описание слайда:

Граф G: Маршрут называется простой цепью, если все его вершины и рёбра – различны. Длина маршрута равна количеству ребер, входящих в него. V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15

14 слайд (А1 А4); (А4 А5). (А1 А2); (А2 А4); (А4 А5). (А1 А4); (А4 А2); (А2 А1); (А1 А
Описание слайда:

(А1 А4); (А4 А5). (А1 А2); (А2 А4); (А4 А5). (А1 А4); (А4 А2); (А2 А1); (А1 А4); (А4, А5). (А1 А4); (А4 А2); (А2 А1); (А1 А3); (А3 А4); (А4, А5). Определите, какие последовательности ребер являются маршрутами, и какие из них простые. Если последовательность не является маршрутом, укажите почему. Первая, вторая и четвертая последовательности являются путями, а третья нет, т.к. ребро (А1, А4) повторяется. Первая и вторая последовательность являются простыми путями, а четвертая нет, т.к. вершины А1 и А4 повторяются. ОТВЕТ Задание 3.

15 слайд Граф G: Граф является связным, если каждая его вершина достижима из другой ве
Описание слайда:

Граф G: Граф является связным, если каждая его вершина достижима из другой вершины. V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15 Является ли данный граф связным? Ответ поясните.

16 слайд Граф G: Вершины, не имеющие инцидентных рёбер, называются изолированными верш
Описание слайда:

Граф G: Вершины, не имеющие инцидентных рёбер, называются изолированными вершинами. Степень таких вершин нулевая. V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15 V6

17 слайд Граф, состоящий из «изолированных» вершин, называется нулевым графом Рис. 1.
Описание слайда:

Граф, состоящий из «изолированных» вершин, называется нулевым графом Рис. 1. Нулевой граф

18 слайд Графы, в которых не построены все возможные ребра, называются неполными графа
Описание слайда:

Графы, в которых не построены все возможные ребра, называются неполными графами. Рис.2. Неполный граф

19 слайд Заметим, что если полный граф имеет n вершин, то количество ребер равно n(n-
Описание слайда:

Заметим, что если полный граф имеет n вершин, то количество ребер равно n(n-1)/2 Задание. Существует ли полный граф с семью ребрами? Решение: Зная количество ребер, узнаем количество вершин. n(n-1)/2=7. n(n-1)=14. Заметим, что n и (n-1) – это два последовательных натуральных числа. Число 14 нельзя представить в виде произведения двух последовательных натуральных чисел, значит, данное уравнение не имеет решений. Следовательно, такого графа не существует. ОТВЕТ

20 слайд Задание 4. Построить граф по заданному условию: В соревнованиях по футболу уч
Описание слайда:

Задание 4. Построить граф по заданному условию: В соревнованиях по футболу участвуют 6 команд. Каждую из команд обозначили буквами А, B, C, D, E и F. Через несколько недель некоторые из команд уже сыграли друг с другом: A с C, D, F; B c C, E, F; С с A, B; D с A, E, F; E с B, D, F; F с A, B, D. ОТВЕТ

21 слайд Изображение графа Один и тот же граф может выглядеть на рисунках по-разному.
Описание слайда:

Изображение графа Один и тот же граф может выглядеть на рисунках по-разному. На рисунке 3(а,б,в) изображен один и тот же граф. Рис.3. Примеры изображения графа

22 слайд Задание 5. Определить изображают ли фигуры на рисунке один и тот же граф или
Описание слайда:

Задание 5. Определить изображают ли фигуры на рисунке один и тот же граф или нет. 1) 2) 3) ОТВЕТ Рисунок 1 и рисунок 2 являются изображениями одного графа. Рисунок 3 изображением - другого графа

23 слайд  Логические задачи
Описание слайда:

Логические задачи

24 слайд Известно, что в настоящий момент: Ваня сыграл шесть партий; Толя сыграл пять
Описание слайда:

Известно, что в настоящий момент: Ваня сыграл шесть партий; Толя сыграл пять партий; Леша и Дима сыграли по три партии; Семен и Илья сыграли по две партии; Женя сыграл одну партию. Условие задачи Требуется определить: с кем сыграл Леша. Шахматный турнир проводится по круговой системе, при которой каждый участник встречается с каждым ровно один раз, участвуют семь школьников.

25 слайд Число в скобках называют степенью вершины, оно показывает сколько ребер выхо
Описание слайда:

Число в скобках называют степенью вершины, оно показывает сколько ребер выходит из данной вершины Ваня (6) Толя (5) Леша (3) Дима (3) Семен (2) Илья (2) Женя (1) Изобразим участников турнира точками Для каждой точки укажем ее имя (по первой букве имени игрока) и количество партий, сыгранные этим игроком

26 слайд Начать построение ребер следует с вершины В, так как это единственная вершин
Описание слайда:

Начать построение ребер следует с вершины В, так как это единственная вершина, которая соединяется со всеми другими вершинами графа Ваня (6) Толя (5) Леша (3) Дима (3) Семен (2) Илья (2) Женя (1) Будем строить ребра графа с учетом степеней вершин

27 слайд Для вершин В и Ж построены все возможные ребра Ваня (6) Толя (5) Леша (3) Ди
Описание слайда:

Для вершин В и Ж построены все возможные ребра Ваня (6) Толя (5) Леша (3) Дима (3) Семен (2) Илья (2) Женя (1) Сделаем первые выводы:

28 слайд Теперь однозначно определяются ребра вершины Т. С учетом ребра ВТ надо постр
Описание слайда:

Теперь однозначно определяются ребра вершины Т. С учетом ребра ВТ надо построить четыре ребра Ваня (6) Толя (5) Леша (3) Дима (3) Семен (2) Илья (2) Женя (1) Построим следующие ребра

29 слайд Все возможные ребра теперь построены для вершин Ж, В, Т, а также для вершин
Описание слайда:

Все возможные ребра теперь построены для вершин Ж, В, Т, а также для вершин С и И Ваня (6) Толя (5) Леша (3) Дима (3) Семен (2) Илья (2) Женя (1) Пора делать новые выводы

30 слайд ОТВЕТ: Леша играл с Толей, Ваней и Димой Ваня (6) Толя (5) Леша (3) Дима (3)
Описание слайда:

ОТВЕТ: Леша играл с Толей, Ваней и Димой Ваня (6) Толя (5) Леша (3) Дима (3) Семен (2) Илья (2) Женя (1) Требовалось определить: с кем сыграл Леша. Граф к задаче построен

31 слайд Домашнее задание §1.10.1 стр.112-114. Выучить все определения.
Описание слайда:

Домашнее задание §1.10.1 стр.112-114. Выучить все определения.

32 слайд Ориентированный граф Граф называется ориентированным (или орграфом), если нек
Описание слайда:

Ориентированный граф Граф называется ориентированным (или орграфом), если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет. Если ребра ориентированы, что обычно показывают стрелками, то они называются дугами. Рис. 4. Ориентированный граф

33 слайд Взвешенный граф Взвешенный граф (сеть) – граф, ребрам или дугам которого пост
Описание слайда:

Взвешенный граф Взвешенный граф (сеть) – граф, ребрам или дугам которого поставлены в соответствие числа (вес). Вес сети равен сумме весов ее ребер. 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 9 8

34 слайд Способы описания графа матрица инциденций, матрица смежности, списки связи, п
Описание слайда:

Способы описания графа матрица инциденций, матрица смежности, списки связи, перечни ребер.

35 слайд Матрица смежности Это двумерный массив N*N.
Описание слайда:

Матрица смежности Это двумерный массив N*N.

36 слайд
Описание слайда:

37 слайд Домашнее задание §1.10.1 стр.114-115. Выучить все определения. Решить задачи
Описание слайда:

Домашнее задание §1.10.1 стр.114-115. Выучить все определения. Решить задачи (карточка).

Выбранный для просмотра документ Решение графов.doc

библиотека
материалов
Скачать материал целиком можно бесплатно по ссылке внизу страницы.

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

Граф — это набор вершин и соединяющих их ребер.

Чаще всего используется взвешенный граф, где с каждым ребром связано некоторое число (вес), оно может обозначать, например, расстояние между городами или стоимость перевозки.

Рассмотрим граф (рисунок слева), в котором 5 вершин (A, B, C, D и E); он описывается таблицей, расположенной в центре; в ней, например, число 4 на пересечении строки В и столбца С означает, что, во-первых, есть ребро, соединяющее В и С, и во-вторых, вес этого ребра равен 4; пустая клетка на пересечении строки А и столбца В означает, что ребра из А в В нет.

hello_html_m10fa2472.png

Граф по заданной таблице (она еще называется весовой матрицей) может быть нарисован по-разному; например, той же таблице соответствует граф, показанный на рисунке справа от нее.

 

Пример задания:

Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.

hello_html_19022689.png

Решение:

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
























































hello_html_4f8d758a.png

По схемам определяем кратчайшие маршруты для каждой таблицы:

1: hello_html_5cb4e84a.gifили hello_html_m54fb299d.gif, стоимость 7

2: hello_html_5cb4e84a.gifили hello_html_44ad86fc.gif, стоимость 7

3: hello_html_m26767a3e.gif, стоимость 6

4: hello_html_m76128c0.gif, стоимость 8

 

Условие «не больше 6» выполняется только для таблицы 3.

Правильный ответ – 3.

Задания

1) В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице.

hello_html_m76792a10.png

hello_html_m4934cd8a.png

 

2) В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и столбца пусто, то соответствующие населенные пун­кты не соединены автомагистралями. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта А до пункта С не больше 5». Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом любой населенный пункт должен встречаться на маршруте не более одного раза






























hello_html_m1a2b578c.png

 

3) В таблице приведена стоимость перевозки грузов между соседними станциями. Если пересечение строки и столбца пусто, то соответствующие станции не являются соседними. Укажите таблицу, для которой выполняется условие «Минимальная стоимость перевозки грузов от пункта А до пункта В не больше 3».

hello_html_19bc2ff7.png

 

4) В таблицах приведена стоимость перевозки грузов между соседними станциями. Если пересечение строки и столбца пусто, то соответствующие станции не являются соседними. Укажите номер таблицы, для которой выполняется условие «Максимальная стоимость перевозки грузов от пункта В до пункта D не больше 6».

hello_html_m2036a2c9.png

 

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

hello_html_75486d35.png

Ответы

hello_html_55356c6d.gifhello_html_m780db710.jpg

задания

Ответ

1

4

2

4

3

3

4

2

5

2


Общая информация

Номер материала: ДВ-230875

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

Курс повышения квалификации «Табличный процессор MS Excel в профессиональной деятельности учителя математики»
Курс повышения квалификации «Информационные технологии в деятельности учителя физики»
Курс повышения квалификации «Современные информационные технологии и их использование в работе преподавателей. Системы автоматизированного проектирования одежды и организация технологического процесса»
Курс повышения квалификации «Организация работы по формированию медиаграмотности и повышению уровня информационных компетенций всех участников образовательного процесса»
Курс профессиональной переподготовки «Информатика: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Облачные технологии в образовании»
Курс «1С: Предприятие 7.7»
Курс «3D Studio MAX»
Курс «WEB-ВЕРСТКА (HTML, CSS)»
Курс повышения квалификации «Сетевые и дистанционные (электронные) формы обучения в условиях реализации ФГОС по ТОП-50»
Курс профессиональной переподготовки «Информационные технологии в профессиональной деятельности: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Использование компьютерных технологий в процессе обучения в условиях реализации ФГОС»
Курс повышения квалификации «Специфика преподавания информатики в начальных классах с учетом ФГОС НОО»
Курс повышения квалификации «Введение в программирование на языке С (СИ)»
Курс профессиональной переподготовки «Теория и методика обучения информатике в начальной школе»

Благодарность за вклад в развитие крупнейшей онлайн-библиотеки методических разработок для учителей

Опубликуйте минимум 3 материала, чтобы БЕСПЛАТНО получить и скачать данную благодарность

Сертификат о создании сайта

Добавьте минимум пять материалов, чтобы получить сертификат о создании сайта

Грамота за использование ИКТ в работе педагога

Опубликуйте минимум 10 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

Свидетельство о представлении обобщённого педагогического опыта на Всероссийском уровне

Опубликуйте минимум 15 материалов, чтобы БЕСПЛАТНО получить и скачать данное cвидетельство

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

Опубликуйте минимум 20 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

Грамота за активное участие в работе над повышением качества образования совместно с проектом "Инфоурок"

Опубликуйте минимум 25 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

Почётная грамота за научно-просветительскую и образовательную деятельность в рамках проекта "Инфоурок"

Опубликуйте минимум 40 материалов, чтобы БЕСПЛАТНО получить и скачать данную почётную грамоту

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