Графы (информатика)

ДЕМО 2013. А2. Между населёнными пунктами  A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.) 

Определите длину кратчайшего пути между пунктами  A и F (при условии, что передвигаться можно только по построенным дорогам).

1) 11

2) 12

3) 13

4) 18 

Цель урока:

уметь находить кратчайший путь

План нахождения кратчайшего пути

представленную в табличной форме в граф

Определить все пути в графе

Определить кратчайший путь.

ДЕМО 2013. А2. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.) Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам). 1) 11 2) 12 3) 13 4) 18  

A

A

B

B

3

C

3

C

D

D

E

7

7

E

4

F

4

F

7

7

5

5

2

2

3

3

1) 11 3) 13 2) 12 4) 18

25.12.16

Графы

Цель урока: уметь находить кратчайший путь

A2

План нахождения кратчайшего пути

• Преобразовать информацию, представленную в табличной форме в граф
• Определить все пути в графе
• Определить кратчайший путь

ДЕМО 2014. А2. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.) Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам). 1) 12 2) 13 3) 14 4) 15  

A

A

B

B

C

2

2

C

D

4

4

D

E

6

E

6

3

F

3

F

16

3

16

3

4

4

9

9

3

3

1) 12 3) 14 2) 13 4) 15

A

16

2

4

C

B

F

6

3

3

3

9

D

E

4

A2

Домашнее задание ДЕМО 2012. А2. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.) Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам). 1) 9 2) 10 3) 11 4) 12  

A

A

B

B

2

C

2

C

4

D

D

4

E

1

1

E

F

F

7

3

3

7

4

4

3

3

2

2

1) 11 3) 13 2) 12 4) 18

План нахождения кратчайшего пути

• Преобразовать информацию, представленную в табличной форме в граф
• Определить все пути в графе
• Определить кратчайший путь

• Я вспомнил, что такое …
• Я могу на основе табличной информационной модели построить … и определить …
• На основе анализа всех путей в графе я могу делать заключение о том …

Вырази свое настроение

• Мне все понятно, у меня все получается!

• У меня еще есть ошибки, но я стараюсь!

• Я ничего не понимаю,

у меня ничего не получается!

Боксеры с твердою походкой

Не моют пол зубною щеткой.

Кто моет пол зубною щеткой,

Тот наделен душою кроткой.

Кто пол мыть щеткой не желает,

Суровым нравом обладает.

Суровый нрав у тех бывает,

Кто книжек вовсе не читает.

Фосс враг книжек и газет,

Ответь, боксер он или нет?