Моделювання. Побудова граф

Що потрібно знати :

  • граф (це набір вершин і ребер, що з'єднують їх) і як він описується у вигляді таблиці, хоча, як правило, всі необхідні пояснення дано у формулюванні завдання
  • найчастіше використовується зважений граф, де з кожним ребром пов'язане деяке число (вага), воно може означати, наприклад, відстань між містами або вартість перевезення
  • розглянемо граф (малюнок зліва), у якому 5 вершин (A, B, C, D та E); він описується таблицею, що у центрі; у ній, наприклад, число 4 на перетині рядка і стовпця З означає, що, по-перше, є ребро, що з'єднує В і С, і по-друге, вага цього ребра дорівнює 4; порожня клітина на перетині рядка А і стовпця означає, що ребра з А в В немає
  • Зверніть увагу, що граф по заданій таблиці (вона ще називається ваговою матрицею) може бути намальований по-різному; наприклад, тій же таблиці відповідає граф, показаний на малюнку праворуч від неї
  • у наведеному прикладі матриця симетрична щодо головної діагоналі; це може означати, наприклад, що вартість перевезення з У С і назад рівні (це не завжди так)
  • бажано навчитися швидко (і правильно) будувати граф за ваговою матрицею та навпаки

1) таблиці наведено вартість перевезення пасажирів між сусідніми населеними пунктами. Вкажіть відповідну схему.

1/Temp/msohtml1/01/clip_image007.gif" /> У даному завданні аналізуємо таблицю зіставляючи кожен варіант - значення в таблиці

1. перший підходить, але перевіримо інші варіанти

2. з А в С -5, значить не так!

3. із С у Д – 2 теж не правильно!

4. з А в дороги немає, теж не вірно!

Відповідь: 1 (варіант відповіді).

Завдання № 2

Якщо збудуємотаблицю протяжності доріг можна наочно проаналізувати віддалені пункти

А-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 (варіант відповіді)

Моделювання. Побудова граф.

Що потрібно знати:

  1. граф (це набір вершин і ребер, що з'єднують їх) і як він описується у вигляді таблиці, хоча, як правило, всі необхідні пояснення дано у формулюванні завдання
  2. найчастіше використовується зважений граф, де з кожним ребром пов'язане деяке число (вага), воно може означати, наприклад, відстань між містами або вартість перевезення
  3. розглянемо граф (малюнок зліва), у якому 5 вершин (A, B, C, D та E); він описується таблицею, що у центрі; у ній, наприклад, число 4 на перетині рядка і стовпця З означає, що, по-перше, є ребро, що з'єднує В і С, і по-друге, вага цього ребра дорівнює 4; порожня клітина на перетині рядка А і стовпця означає, що ребра з А в В немає