kopilkaurokov.ru - сайт для учителей

Создайте Ваш сайт учителя Курсы ПК и ППК Видеоуроки Олимпиады Вебинары для учителей

  1. Главная
  2. Информатика
  3. Презентации
  4. Методическая разработка "Графы. Поиск путей в графе".

Методическая разработка "Графы. Поиск путей в графе".

Нажмите, чтобы узнать подробности

В мультимедийной   презентации  на  тему   "Графы. Поиск путей в графе"  содержится  теоретический материал:  Граф и его элементы. Основные понятия.  

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

Для закрепления нового материала  учащимся предложены задачи в формате ЕГЭ.

Данная разработка может быть использована при подготовке учащихся к сдаче ЕГЭ.

Вы уже знаете о суперспособностях современного учителя?
Тратить минимум сил на подготовку и проведение уроков.
Быстро и объективно проверять знания учащихся.
Сделать изучение нового материала максимально понятным.
Избавить себя от подбора заданий и их проверки после уроков.
Наладить дисциплину на своих уроках.
Получить возможность работать творчески.

Просмотр содержимого документа
«Методическая разработка "Графы. Поиск путей в графе". »

ГРАФЫ. ПОИСК ПУТЕЙ В ГРАФЕ. Автор: Сергеенкова И.М., ГБОУ Школа № 1191, г. Москва

ГРАФЫ.

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

Автор: Сергеенкова И.М.,

ГБОУ Школа № 1191, г. Москва

Дуга графа Дуга графа ребро графа Граф и его элементы. Основные понятия. Граф  – это совокупность объектов со связями между ними.  Объекты рассматриваются как вершины, или узлы графа, а связи – как дуги, или ребра. Ребро графа называется дугой , если одна из его вершин считается начальной , другая – конечной . Вершина графа Вершина графа Б А В Вершина графа Основные элементы графа состоят из вершин графа, ребер графа и дуг графа .  Сочетание этих элементов определяет понятия: неориентированный граф, ориентированный граф и смешанный граф .

Дуга графа

Дуга графа

ребро графа

Граф и его элементы. Основные понятия.

Граф  – это совокупность объектов со связями между ними. 

Объекты рассматриваются как вершины, или узлы графа,

а связи – как дуги, или ребра.

Ребро графа называется дугой , если одна из его вершин считается начальной , другая – конечной .

Вершина

графа

Вершина

графа

Б

А

В

Вершина

графа

Основные элементы графа состоят из вершин графа, ребер графа и дуг графа .  Сочетание этих элементов определяет понятия: неориентированный граф, ориентированный граф и смешанный граф .

Неориентированный граф  – это граф, для каждого ребра которого несуществен порядок двух его конечных вершин. 4 5 6 1 2 3

Неориентированный граф  – это граф, для каждого ребра которого несуществен порядок двух его конечных вершин.

4

5

6

1

2

3

Ориентированный граф  –  это граф, для каждого ребра которого существенен порядок двух его конечных вершин. Пара вершин может соединяться двумя или более ребрами (дугами одного направления), такие ребра называются кратными. 2 4 1 5 3

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

Пара вершин может соединяться двумя или более ребрами (дугами одного направления), такие ребра называются кратными.

2

4

1

5

3

Смешанный граф  – это граф, содержащий как ориентированные, так и неориентированных ребра. Любой из перечисленных видов графа может содержать одно или несколько ребер, у которых оба конца сходятся в одной вершине, такие ребра называются петлями.  2 1 2 1 5 5 3 4 3 4 Путем в графе называют конечную последовательность вершин, в которой каждая вершина соединена ребром с последующей в последовательности вершин. Длиной пути во взвешенном графе называют сумму длин звеньев этого пути. Количество  k  ребер в пути называется длиной пути. Путь называют циклом , если в нем первая и последняя вершины совпадают.

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

2

1

2

1

5

5

3

4

3

4

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

Длиной пути во взвешенном графе называют сумму длин звеньев этого пути. Количество  k  ребер в пути называется длиной пути. Путь называют циклом , если в нем первая и последняя вершины совпадают.

12 Задачи на поиск путей в Графе Задача 1. На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G, H, K, L, M. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город M ? C B E F M A H G L K Решение

12

Задачи на поиск путей в Графе

Задача 1.

На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G, H, K, L, M. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.

Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город M ?

C

B

E

F

M

A

H

G

L

K

Решение

Решение задачи 1. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та – с го­ро­да М. N X   — ко­ли­че­ство раз­лич­ных путей из го­ро­да А в город X, N — общее число путей. В

Решение задачи 1.

  • Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та – с го­ро­да М.

N X   — ко­ли­че­ство раз­лич­ных путей из го­ро­да А в город X, N — общее число путей. В "М" можно при­е­хать из C, F, L или H, по­это­му

N = N M  = N C  + N F  + N  H  + N  L  (1)

C

F

M

H

L

C B 2. Ана­ло­гич­но: N C  = N B ; N F  = N E ; N H  = N F  + N G ; N L  = N K . E F A M G H L K 3. До­ба­вим еще вер­ши­ны: N B  = N A  = 1; N E  = N B  + N A  + N G  = 1 + 1 + 2 = 4; N G  = N A  + N K  = 1 + 1 = 2; N K  = N A  = 1.

C

B

2. Ана­ло­гич­но:

N C  = N B ;

N F  = N E ;

N H  = N F  + N G ;

N L  = N K .

E

F

A

M

G

H

L

K

3. До­ба­вим еще вер­ши­ны:

N B  = N A  = 1;

N E  = N B  + N A  + N G  = 1 + 1 + 2 = 4;

N G  = N A  + N K  = 1 + 1 = 2;

N K  = N A  = 1.

4. Пре­об­ра­зу­ем вер­ши­ны: N C  = N B  = 1; N F  = N E  = 4; N H  = N F  + N G  = 4 + 2 = 6; N L  = N K  = 1. C B E F A M H G L K 5. Под­ста­вим в фор­му­лу (1): N = N К  = 1 + 4 + 6 + 1 = 12 Ответ: 12

4. Пре­об­ра­зу­ем вер­ши­ны:

N C  = N B  = 1;

N F  = N E  = 4;

N H  = N F  + N G  = 4 + 2 = 6;

N L  = N K  = 1.

C

B

E

F

A

M

H

G

L

K

5. Под­ста­вим в фор­му­лу (1):

N = N К  = 1 + 4 + 6 + 1 = 12

Ответ: 12

Задача 2 . На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж, З, И. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город И? Д Б Ж В A И Е Г З Решение

Задача 2 .

На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж, З, И. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.

Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город И?

Д

Б

Ж

В

A

И

Е

Г

З

Решение

Решение задачи 2 . 1. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та – с го­ро­да И . N X  — ко­ли­че­ство раз­лич­ных путей из го­ро­да А в город X, N — общее число путей. В

Решение задачи 2 .

1. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та – с го­ро­да И . N X  — ко­ли­че­ство раз­лич­ных путей из го­ро­да А в город X, N — общее число путей. В "И" можно при­е­хать из Д, Ж, или З, по­это­му N = N И  = N Д  + N Ж  + N  З  (1)

Д

И

Ж

З

2. Ана­ло­гич­но: N Д  = N Б ; N Ж  = N Б  + N В  + N Е ; N З  = N Ж  + N Е . Б Д И А Ж В З Г Е 3. . До­ба­вим еще вер­ши­ны: N Б  = N А  = 1; N В  = N А  + N Г  = 1 + 1 = 2; N Е  = N В  + N Г  = 2 + 1 = 3; N Г  = N А  = 1.

2. Ана­ло­гич­но:

N Д  = N Б ; N Ж  = N Б  + N В  + N Е ; N З  = N Ж  + N Е .

Б

Д

И

А

Ж

В

З

Г

Е

3. . До­ба­вим еще вер­ши­ны:

N Б  = N А  = 1;

N В  = N А  + N Г  = 1 + 1 = 2;

N Е  = N В  + N Г  = 2 + 1 = 3;

N Г  = N А  = 1.

4. Пре­об­ра­зу­ем пер­вые вер­ши­ны с уче­то зна­че­ний вто­рых: N Д  = N Б  = 1; N Ж  = N Б  + N В  + N Е  = 1 + 2 + 3 = 6; N З  = N Ж  + N Е  = 6 + 3 = 9. Д Б И A Ж В Г Е З 5. Под­ста­вим в фор­му­лу (1): N = N К  = 1 + 6 + 9 = 16. Ответ: 16

4. Пре­об­ра­зу­ем пер­вые вер­ши­ны с уче­то зна­че­ний вто­рых:

N Д  = N Б  = 1;

N Ж  = N Б  + N В  + N Е  = 1 + 2 + 3 = 6;

N З  = N Ж  + N Е  = 6 + 3 = 9.

Д

Б

И

A

Ж

В

Г

Е

З

5. Под­ста­вим в фор­му­лу (1):

N = N К  = 1 + 6 + 9 = 16. Ответ: 16

Задача 3. На ри­сун­ке изоб­ра­же­на схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G, H, K, L, M. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город M? L B C G A M F D H E K Решение

Задача 3.

На ри­сун­ке изоб­ра­же­на схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G, H, K, L, M. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.

Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город M?

L

B

C

G

A

M

F

D

H

E

K

Решение

Решение задачи 3. 1. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та — с го­ро­да M. Пусть N X  — ко­ли­че­ство раз­лич­ных путей из го­ро­да А в город X, N — общее число путей. В город M можно при­е­хать из L, G, F, H или K, по­это­му N = N M  = N L  + N G +N F + N H  + N K ;(*) 2.Ана­ло­гич­но: N L  = N F + N G  = 5 + 5 = 10; N G  = N F  = 5; N H  = N F  = 5; N K  = N F  + N E  + N H  = 5 + 1 + 5 = 11; N F  = N A  + N B  + N C  + N D  + N E  = = 5. 4. Под­ста­вим в фор­му­лу : 3. До­ба­вим еще вер­ши­ны: N B  = N A  = 1; N = N M  = 10 + 5 + 5 + 11 + 5 = 36. N C  = N A  = 1; N D  = N A  = 1; N E  = N A  = 1. Ответ: 36.

Решение задачи 3.

1. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та — с го­ро­да M. Пусть N X  — ко­ли­че­ство раз­лич­ных путей из го­ро­да А в город X, N — общее число путей. В город M можно при­е­хать из L, G, F, H или K, по­это­му N = N M  = N L  + N G +N F + N H  + N K ;(*)

2.Ана­ло­гич­но:

N L  = N F + N G  = 5 + 5 = 10;

N G  = N F  = 5;

N H  = N F  = 5;

N K  = N F  + N E  + N H  = 5 + 1 + 5 = 11;

N F  = N A  + N B  + N C  + N D  + N E  = = 5.

4. Под­ста­вим в фор­му­лу :

3. До­ба­вим еще вер­ши­ны:

N B  = N A  = 1;

N = N M  = 10 + 5 + 5 + 11 + 5 = 36.

N C  = N A  = 1;

N D  = N A  = 1;

N E  = N A  = 1.

Ответ: 36.

Решите самостоятельно: 1). На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж, И, К, Л. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город Л? Б Е Д E B A Л К Г Ж Ответ: 30

Решите самостоятельно:

1).

На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж, И, К, Л. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.

Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город Л?

Б

Е

Д

E

B

A

Л

К

Г

Ж

Ответ: 30

2). На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город Ж? В Ж Г Б Е А Д Ответ: 11

2).

На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.

Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город Ж?

В

Ж

Г

Б

Е

А

Д

Ответ: 11

3). На ри­сун­ке изоб­ра­же­на схема до­ро­г, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G, H, K, L, M. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город M? F B K C М H А D L G E Ответ: 12

3).

На ри­сун­ке изоб­ра­же­на схема до­ро­г, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G, H, K, L, M. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.

Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город M?

F

B

K

C

М

H

А

D

L

G

E

Ответ: 12

Задание на дом: На рисунке изображена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город M? G B C H А F M K D L E

Задание на дом:

На рисунке изображена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города

А в город M?

G

B

C

H

А

F

M

K

D

L

E

Источники информации:

Источники информации:

  • http:// www.compress.ru/Archive/CP/2007/1/18/10.gif
  • http:// kpolyakov.narod.ru/school/ege.htm
  • http :// inf.reshuege.ru/test?theme=203
  • http:// inf.reshuege.ru/get_file?id=3029


Получите в подарок сайт учителя

Электронная тетрадь по информатике 9...

Электронная тетрадь по информатике 11...

Информатика 11 класс (Беларусь)

Электронная тетрадь по информатике 5...

Информатика и ИКТ 11 класс (к учебнику...

Информатика 8 класс ФГОС

Информатика 7 класс ФГОС

Информатика 11 класс ФГОС

Предмет: Информатика

Категория: Презентации

Целевая аудитория: 11 класс

Скачать
Методическая разработка "Графы. Поиск путей в графе".

Автор: Сергеенкова Ирина Михайловна

Дата: 18.11.2014

Номер свидетельства: 132517

Похожие файлы

object(ArrayObject)#863 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(99) "Новый образовательный стандарт - мой творческий поиск"
    ["seo_title"] => string(54) "novyi_obrazovatiel_nyi_standart_moi_tvorchieskii_poisk"
    ["file_id"] => string(6) "374844"
    ["category_seo"] => string(16) "nachalniyeKlassi"
    ["subcategory_seo"] => string(12) "meropriyatia"
    ["date"] => string(10) "1483275461"
  }
}

object(ArrayObject)#885 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(146) "Календарно-тематическое планирование по изо3 класс УМК "Начальная школа XXI века""
    ["seo_title"] => string(78) "kaliendarnotiematichieskoieplanirovaniiepoizo3klassumknachalnaiashkolaxxivieka"
    ["file_id"] => string(6) "267598"
    ["category_seo"] => string(16) "nachalniyeKlassi"
    ["subcategory_seo"] => string(12) "planirovanie"
    ["date"] => string(10) "1450416286"
  }
}

object(ArrayObject)#863 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(102) "Рабочая программа по технологии для неделимых классов. "
    ["seo_title"] => string(63) "rabochaia-proghramma-po-tiekhnologhii-dlia-niedielimykh-klassov"
    ["file_id"] => string(6) "117183"
    ["category_seo"] => string(12) "tehnologiyad"
    ["subcategory_seo"] => string(12) "planirovanie"
    ["date"] => string(10) "1412709638"
  }
}

object(ArrayObject)#885 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(136) "Рабочая программа внеурочной деятельности  «Наглядная геометрия» 5 класс "
    ["seo_title"] => string(84) "rabochaia-proghramma-vnieurochnoi-dieiatiel-nosti-naghliadnaia-ghieomietriia-5-klass"
    ["file_id"] => string(6) "161664"
    ["category_seo"] => string(10) "matematika"
    ["subcategory_seo"] => string(12) "planirovanie"
    ["date"] => string(10) "1422266039"
  }
}

object(ArrayObject)#863 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(108) "Рабочая программа по технологии 7-8 классы 2015-2016 учебный год"
    ["seo_title"] => string(73) "rabochaia-proghramma-po-tiekhnologhii-7-8-klassy-2015-2016-uchiebnyi-ghod"
    ["file_id"] => string(6) "247552"
    ["category_seo"] => string(12) "tehnologiyad"
    ["subcategory_seo"] => string(12) "planirovanie"
    ["date"] => string(10) "1446571717"
  }
}

Перейти в личный кабинет

Полезное для учителя


Получите в подарок сайт учителя

Видеоуроки для учителей

Курсы для учителей

Распродажа видеоуроков!
1270 руб.
2110 руб.
Смотреть все комплекты
Курсы ПК и ППК для учителей!
Смотреть все курсы
ПОЛУЧИТЕ СВИДЕТЕЛЬСТВО МГНОВЕННО

Добавить свою работу

* Свидетельство о публикации выдается БЕСПЛАТНО, СРАЗУ же после добавления Вами Вашей работы на сайт

Удобный поиск материалов для учителей

Проверка свидетельства