Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Презентации / Презентация по информатике "Введение в теорию графов" (11 класс)

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

Идёт приём заявок на самые массовые международные олимпиады проекта "Инфоурок"

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

1. Бесплатные наградные документы с указанием данных образовательной Лицензии и Свидeтельства СМИ;
2. Призовой фонд 1.500.000 рублей для самых активных учителей;
3. До 100 рублей за одного ученика остаётся у учителя (при орг.взносе 150 рублей);
4. Бесплатные путёвки в Турцию (на двоих, всё включено) - розыгрыш среди активных учителей;
5. Бесплатная подписка на месяц на видеоуроки от "Инфоурок" - активным учителям;
6. Благодарность учителю будет выслана на адрес руководителя школы.

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

  • Информатика

Название документа Введение в теорию графов.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 из 37

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

№ слайда 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


Самые низкие цены на курсы профессиональной переподготовки и повышения квалификации!

Предлагаем учителям воспользоваться 50% скидкой при обучении по программам профессиональной переподготовки.

После окончания обучения выдаётся диплом о профессиональной переподготовке установленного образца (признаётся при прохождении аттестации по всей России).

Обучение проходит заочно прямо на сайте проекта "Инфоурок".

Начало обучения ближайших групп: 18 января и 25 января. Оплата возможна в беспроцентную рассрочку (20% в начале обучения и 80% в конце обучения)!

Подайте заявку на интересующий Вас курс сейчас: https://infourok.ru/kursy

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

УЖЕ ЧЕРЕЗ 10 МИНУТ ВЫ МОЖЕТЕ ПОЛУЧИТЬ ДИПЛОМ

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

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

Список всех тестов можно посмотреть тут - https://infourok.ru/tests

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

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