Анализ моделей объектов.
материал для подготовки к егэ (гиа) по информатике и икт (9 класс)

Слайд 1

Слайд 2

Граф – это набор вершин и связей между ними, называющихся рёбрами: Граф, отображающий дороги между поселками

Слайд 3

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

Слайд 4

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

Слайд 5

Дерево – это связный граф без циклов (замкнутых участков).

Слайд 6

Взвешенные графы и весовая матрица У взвешенных графов указан «вес ребра»:

Слайд 7

Из взвешенных графов получается весовая матрица, обратное преобразование тоже возможно.

Слайд 8

ПОИСК КРАТЧАЙШЕГО ПУТИ (ПЕРЕБОР) Определение кратчайшего пути между пунктами A и D

Слайд 9

Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице: Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. A B C D E A 1 B 1 2 2 7 C 2 3 D 2 4 E 7 3

Слайд 10

Решение. Найдём все варианты маршрутов из A в E и выберем самый короткий. Из пункта A можно попасть в пункт B. Из пункта B можно попасть в пункты C, D, E. Из пункта C можно попасть в пункт E. Из пункта D можно попасть в пункт E. A—B: длина маршрута 1 км. A—B—C—E: длина маршрута 6 км. A—B—D—E: длина маршрута 7 км. A—B—E: длина маршрута 8 км. Самый короткий путь: A—B—C—E. Длина маршрута 6 км. Ответ: 6.

Слайд 11

Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице: Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. A B C D E A 4 7 B 4 1 5 C 7 1 3 D 5 3 1 E 1

Слайд 12

Решение. Найдём все варианты маршрутов из A в E и выберем самый короткий. Из пункта A можно попасть в пункты B, С. Из пункта B можно попасть в пункты C, D. Из пункта C можно попасть в пункт D. Из пункта D можно попасть в пункт E. A—B—C—D—E: длина маршрута 9 км. A—B—D—E: длина маршрута 10 км. A—C—D—E: длина маршрута 11 км. Самый короткий путь: A—B—C—D—E. Длина маршрута 9 км. Ответ: 9.