Новая Школа - онлайн-школа подготовки к ЕГЭ
Задача Задача №3828136
А
Аноним
11 часов назад · публичный вопрос
А
Аноним

реши 7 и нарисуй графики

Ответ нейросети
11 часов назад

Краткий ответ: минимальную стоимость обеспечивает третья компания: \(6\). Лучший маршрут — \(A\to E\to B\): \(4+2=6\). У первой и второй компаний минимум по \(7\).

Как читать таблицу. Каждая непустая клетка вне диагонали — это ребро графа: например, \(A-C=3\) означает дорогу \(A-C\) стоимостью \(3\). Таблицы симметричны, поэтому графы неориентированные. \(D\) — концевая станция: из неё можно уехать только в \(A\), поэтому в маршрут \(A\to B\) она не входит.

Графы компаний

1-я компания

        B
       / \
     4/   \2
     /     \
A ──3── C ──2── E
│
1
│
D

Рёбра: \(A-C=3\), \(A-D=1\), \(B-C=4\), \(B-E=2\), \(C-E=2\).

Возможные маршруты:

  • \(A-C-B=3+4=7\)
  • \(A-C-E-B=3+2+2=7\)

Минимум: \(7\).

2-я компания

          B
          │4
          │
D ──1── A ──3── C
         \     /
         1\   /2
           \ /
            E

Рёбра: \(A-C=3\), \(A-D=1\), \(A-E=1\), \(B-C=4\), \(C-E=2\).

Маршруты:

  • \(A-C-B=3+4=7\)
  • \(A-E-C-B=1+2+4=7\)

Минимум: \(7\).

3-я компания

          C ──4── B
         / \     /
       3/   \2  /2
       /     \ /
      A ──4── E
      │
      1
      │
      D

Рёбра: \(A-C=3\), \(A-D=1\), \(A-E=4\), \(B-C=4\), \(B-E=2\), \(C-E=2\).

Маршруты:

  • \(A-C-B=3+4=7\)
  • \(A-C-E-B=3+2+2=7\)
  • \(A-E-B=4+2=6\)

Минимум: \(6\).

Проверка: \(7\), \(7\), \(6\). Значит, минимальную стоимость даёт компания 3.

Обсуждение

4 сообщения
А
Аноним

реши 7 и нарисуй графики

Нейросеть11 часов назад

Ответ: минимальную стоимость обеспечивает третья компания — \(6\).
Оптимальный маршрут: \(A \to E \to B\), стоимость \(4+2=6\).

Ниже — графы трёх компаний. Числа на рёбрах — стоимости перевозок; пустая клетка в таблице означает отсутствие дороги. Вершина \(D\) — концевая, через неё к \(B\) попасть нельзя.

1-я компания

        B
       / \
     4/   \2
     /     \
A --3-- C --2-- E
|
1
|
D

Рёбра: \(A-C=3,\ A-D=1,\ B-C=4,\ B-E=2,\ C-E=2\).

Маршруты \(A\to B\):

  • \(A\to C\to B=3+4=7\);
  • \(A\to C\to E\to B=3+2+2=7\).

Минимум: 7.


2-я компания

        B
        |
        4
        |
A --3-- C --2-- E
| \             /
1  \----1------/
|
D

Рёбра: \(A-C=3,\ A-D=1,\ A-E=1,\ B-C=4,\ C-E=2\).

Маршруты \(A\to B\):

  • \(A\to C\to B=3+4=7\);
  • \(A\to E\to C\to B=1+2+4=7\).

Минимум: 7.


3-я компания

        B
       / \
     4/   \2
     /     \
A --3-- C --2-- E
| \             /
1  \-----4-----/
|
D

Рёбра: \(A-C=3,\ A-D=1,\ A-E=4,\ B-C=4,\ B-E=2,\ C-E=2\).

Маршруты \(A\to B\):

  • \(A\to C\to B=3+4=7\);
  • \(A\to C\to E\to B=3+2+2=7\);
  • \(A\to E\to B=4+2=6\).

Минимум: 6.

Значит, минимальную стоимость перевозок из \(A\) в \(B\) обеспечивает третья компания.

А
Аноним

нарисуй в тетради

Нейросеть11 часов назад

В тетрадь переносим три схемы-графа и короткий расчёт. Ответ: 3-я компания, \(6\), маршрут \(A\to E\to B\).

Важно: числа на рёбрах — это стоимости, а не длины. В масштабе рисовать не надо, достаточно аккуратной схемы «точки + линии с числами».


1) Первая компания

Что соединить: \(A\!-\!C=3\), \(A\!-\!D=1\), \(B\!-\!C=4\), \(B\!-\!E=2\), \(C\!-\!E=2\).

Точки по клеткам (вправо; вниз от левого верхнего угла схемы): \(A(0;4)\), \(C(3;3)\), \(B(6;0)\), \(E(8;2)\), \(D(0;7)\).

        B
       / \
     4/   \2
     /     \
A --3-- C --2-- E
|
1
|
D

Маршруты \(A\to B\): \(3+4=7\); \(3+2+2=7\). Минимум 7.


2) Вторая компания

Что соединить: \(A\!-\!C=3\), \(A\!-\!D=1\), \(A\!-\!E=1\), \(B\!-\!C=4\), \(C\!-\!E=2\).

Точки: \(A(0;3)\), \(B(5;0)\), \(C(4;4)\), \(E(8;6)\), \(D(0;7)\).

      B
      |
      4
      |
A --3-- C
| \      \
1  \1     \2
|   \      \
D    \------ E

Маршруты: \(A\to C\to B=3+4=7\); \(A\to E\to C\to B=1+2+4=7\). Минимум 7.


3) Третья компания

Что соединить: \(A\!-\!C=3\), \(A\!-\!D=1\), \(A\!-\!E=4\), \(B\!-\!C=4\), \(B\!-\!E=2\), \(C\!-\!E=2\).

Точки: \(A(0;4)\), \(C(3;2)\), \(B(7;0)\), \(E(7;5)\), \(D(0;7)\).

        B
       / \
     4/   \2
     /     \
A --3-- C   |
|        \  |
1         2\|
|           E
D          /
         4
        /
       A

Маршруты: \(A\to C\to B=3+4=7\); \(A\to C\to E\to B=3+2+2=7\); \(A\to E\to B=4+2=6\).

Вывод: \(\min\{7;\,7;\,6\}=6\) — минимальную стоимость даёт третья компания, маршрут \(A\to E\to B\) обведи двойной линией.

Точка \(D\) — «тупик» (из неё есть только дорога в \(A\)), поэтому в маршрут \(A\to B\) она не входит.