Моделирование. Построение граф
Что нужно знать:
· граф (это набор вершин и соединяющих их ребер) и как он описывается в виде таблицы, хотя, как правило, все необходимые объяснения даны в формулировке задания
· чаще всего используется взвешенный граф, где с каждым ребром связано некоторое число (вес), оно может обозначать, например, расстояние между городами или стоимость перевозки
· рассмотрим граф (рисунок слева), в котором 5 вершин (A, B, C, D и E); он описывается таблицей, расположенной в центре; в ней, например, число 4 на пересечении строки В и столбца С означает, что, во-первых, есть ребро, соединяющее В и С, и во-вторых, вес этого ребра равен 4; пустая клетка на пересечении строки А и столбца В означает, что ребра из А в В нет
 | |||
 | |||
| A | B | C | D | Е |
A |
|
| 3 | 1 |
|
B |
|
| 4 |
| 2 |
C | 3 | 4 |
|
| 2 |
D | 1 |
|
|
|
|
Е |
| 2 | 2 |
|
|
· обратите внимание, что граф по заданной таблице (она еще называется весовой матрицей) может быть нарисован по-разному; например, той же таблице соответствует граф, показанный на рисунке справа от нее
· в приведенном примере матрица симметрична относительно главной диагонали; это может означать, например, что стоимости перевозки из В в С и обратно равны (это не всегда так)
· желательно научиться быстро (и правильно) строить граф по весовой матрице и наоборот
пример задания:
1) таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую.
| A | B | C | D |
A |
|
| 1 | 2 |
B |
|
| 2 | 3 |
C | 1 | 2 |
| 5 |
D | 2 | 3 | 5 |
|
1) | 2) | 3) | 4) |
|
|
|
|
В данном задании анализируем таблицу сопоставляя каждый вариант – значению в таблице
1. первый подходит, но проверим остальные варианты
2. из А в С -5, значит не верно!
3. из С в Д – 2 тоже не верно!
4. из А в В дороги нет, тоже не верно!
Ответ: 1 (вариант ответа).
Задание № 2
Если построим таблицу протяженности дорог то можно наглядно проанализировать удаленные пункты
| А | B | C | D | E |
A |
| 5 |
| 9 |
|
B | 5 |
|
|
| 9 |
C |
|
|
| 7 | 8 |
D | 9 |
| 7 |
| 6 |
E |
| 9 | 8 | 6 |
|
А-D-С -16 ИЛИ ABEC- 22
A D E – 15 ИЛИ A B E – 14
B A D – 14 ИЛИB E D – 15
BEC– 17 ИЛИ BADC– 21
Ответ наиболее удален пункт В от пункта С и кратчайшее расстояние между ними 17.
Ответ:3 (вариант ответа)
Скачать:
| Вложение | Размер |
|---|---|
 lekciya_3.doc | 101 КБ |
Предварительный просмотр:
Лекция № 3
Моделирование. Построение граф.
Что нужно знать:
- граф (это набор вершин и соединяющих их ребер) и как он описывается в виде таблицы, хотя, как правило, все необходимые объяснения даны в формулировке задания
- чаще всего используется взвешенный граф, где с каждым ребром связано некоторое число (вес), оно может обозначать, например, расстояние между городами или стоимость перевозки
- рассмотрим граф (рисунок слева), в котором 5 вершин (A, B, C, D и E); он описывается таблицей, расположенной в центре; в ней, например, число 4 на пересечении строки В и столбца С означает, что, во-первых, есть ребро, соединяющее В и С, и во-вторых, вес этого ребра равен 4; пустая клетка на пересечении строки А и столбца В означает, что ребра из А в В нет
1
2
4
2
3
A
B
C
D
E
1
2
4
2
3
A
B
C
D
E
A | B | C | D | Е | |
A | 3 | 1 | |||
B | 4 | 2 | |||
C | 3 | 4 | 2 | ||
D | 1 | ||||
Е | 2 | 2 |
- обратите внимание, что граф по заданной таблице (она еще называется весовой матрицей) может быть нарисован по-разному; например, той же таблице соответствует граф, показанный на рисунке справа от нее
- в приведенном примере матрица симметрична относительно главной диагонали; это может означать, например, что стоимости перевозки из В в С и обратно равны (это не всегда так)
- желательно научиться быстро (и правильно) строить граф по весовой матрице и наоборот
пример задания:
- таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую.
A | B | C | D | |
A | 1 | 2 | ||
B | 2 | 3 | ||
C | 1 | 2 | 5 | |
D | 2 | 3 | 5 |
1) | 2) | 3) | 4) |
3 5 2 A D B С 1 2 | 3 5 1 D A B С 1 2 | 2 1 A C D B 5 3 | C 2 1 A D B 5 3 2 |
В данном задании анализируем таблицу сопоставляя каждый вариант – значению в таблице
- первый подходит, но проверим остальные варианты
- из А в С -5, значит не верно!
- из С в Д – 2 тоже не верно!
- из А в В дороги нет, тоже не верно!
Ответ: 1 (вариант ответа).
Задание № 2
Если построим таблицу протяженности дорог то можно наглядно проанализировать удаленные пункты
А | B | C | D | E | |
A | 5 | 9 | |||
B | 5 | 9 | |||
C | 7 | 8 | |||
D | 9 | 7 | 6 | ||
E | 9 | 8 | 6 |
А-D-С -16 ИЛИ A B E C - 22
A D E – 15 ИЛИ A B E – 14
B A D – 14 ИЛИ B E D – 15
B E C – 17 ИЛИ BA D C – 21
Ответ наиболее удален пункт В от пункта С и кратчайшее расстояние между ними 17.
Ответ:3 (вариант ответа)