- Главная
- Информатика
- Подготовка к ЕГЭ. Информатика
Содержание
- 2. Цель: научиться выполнять задание №5 из ЕГЭ Что нужно знать: 1) В принципе, особых дополнительных знаний,
- 3. Рассмотрим граф (рисунок слева), в котором 5 вершин (A, B, C, D и E); он описывается
- 4. Задача: Между населенными пунктами А,B,C,D,E,F построены дороги, протяженность которых приведена в таблице. (Отсутствие числа в таблице
- 5. 2) Дальше действуем так же, как показано при решении следующих далее разобранных задач; причем из всех
- 6. Граф- это набор вершин и соединяющих их ребер. Взвешенный граф- где с каждым ребром связано некоторое
- 8. Скачать презентацию
Цель: научиться выполнять задание №5 из ЕГЭ
Что нужно знать:
1) В
Цель: научиться выполнять задание №5 из ЕГЭ
Что нужно знать: 1) В
2)Полезно знать, что такое граф
3)Чаще всего используется взвешенный граф
4)желательно научиться быстро (и правильно) строить граф по весовой матрице и наоборот
Рассмотрим граф (рисунок слева), в котором 5 вершин (A, B, C,
Рассмотрим граф (рисунок слева), в котором 5 вершин (A, B, C,
Обратите внимание, что граф по заданной таблице (она еще называется весовой матрицей) может быть нарисован по-разному; например, той же таблице соответствует граф, показанный на рисунке справа от нее
В приведенном примере матрица симметрична относительно главной диагонали; это может означать, например, что стоимости перевозки из В в С и обратно равны (это не всегда так)
Задача: Между населенными пунктами А,B,C,D,E,F построены дороги, протяженность которых приведена в
Задача: Между населенными пунктами А,B,C,D,E,F построены дороги, протяженность которых приведена в
Решение:
1)Поскольку нас интересуют только маршруты, НЕ проходящие через пункт В, столбец и строку, соответствующие этому пункту, можно удалить из таблицы:
2) Дальше действуем так же, как показано при решении следующих далее
2) Дальше действуем так же, как показано при решении следующих далее
3)первый шаг от А (в скобках указаны длины маршрутов):
АС (4), AD (8)
прямой маршрут AF не рассматриваем, потому что он не проходит через пункт E
4)второй шаг
ACD (7), ADC (11), ADE (13)
маршрут ADF не рассматриваем, потому что он не проходит через пункт E
5)третий шаг:
ACDE (12), ADEF (18)
маршрут ADEF дошел до пункта назначения;
маршрут ADC продолжать не имеет смысла, потому что из C можно проехать только в пункты A и D, где мы уже были;
маршрут ACDF не рассматриваем, потому что он не проходит через пункт E
6)четвертый шаг:
ACDEF(17)
7)этот маршрут тоже дошел до пункта назначения, его длина меньше, чем для предыдущего, его и выбираем
8)Ответ: 17.
Граф- это набор вершин и соединяющих их ребер.
Взвешенный граф- где с
Граф- это набор вершин и соединяющих их ребер.
Взвешенный граф- где с
Запомнить!