База ответов ИНТУИТ

Введение в теорию графов

<<- Назад к вопросам

На рисунке дан граф со взвешенными дугами, который представляет сеть допустимых маршрутов для некоторого судна. Каждая дуга имеет пометку(a, b), причем а равно выгоде, получаемой при обслуживании этого маршрута, а b – времени обслуживания маршрута. Найти, какой из перечисленных путей наиболее выгодный (в терминах скорости оборота капитала) путь судна. vn=∑ ai/ ∑ bi

(Отметьте один правильный вариант ответа.)

Варианты ответа
A →​ D →​ B →​ C →​ E →​ A
A →​ B →​ C →​ E →​ D →​ B
A →​ B →​ C →​ D →​ E →​ A(Верный ответ)
Похожие вопросы

На рисунке дан граф со взвешенными дугами, который представляет сеть допустимых маршрутов для некоторого судна. Каждая дуга имеет пометку(a, b), причем а равно выгоде, получаемой при обслуживании этого маршрута, а b – времени обслуживания маршрута. Найти, какой из перечисленных путей наиболее выгодный (в терминах скорости оборота капитала) путь судна. vn=∑ ai / ∑ bi

На рисунке дан граф со взвешенными дугами, который представляет сеть допустимых маршрутов для некоторого судна. Каждая дуга имеет пометку(a, b), причем а равно выгоде, получаемой при обслуживании этого маршрута, а b – времени обслуживания маршрута. Найти, какой из перечисленных путей наиболее выгодный (в терминах скорости оборота капитала) путь судна.

Скорость оборота капитала n -го пути судна найдем как суммарную выгоду пути, деленную на суммарное время, т. е.

vn=∑ ai/ ∑ bi

  • A →​ B →​ C →​ D →​ E →​ A
  • A →​ B →​ C →​ E →​ D →​ A.
  • A →​ D →​ B →​ C →​ E →​ A.
  • A →​ C →​ E →​ D →​ B →​ A.
  • Для графа, представленного на рисунке даны замкнутые пути:

    М1: (х2, х3), (х3, х4), (х4, х7), (х7, х2)

    М2: (х2, х3), (х3, х4), (х4, х5), (х5, х6), (х6, х2) (х2, х3), (х3, х7), (х7, х2)

    М3: (х2, х3), (х3, х4), (х4, х5), (х5, х6), (х6, х2)

    М4: (х3, х4), (х4, х5), (х5, х7), (х7, х3)

    М5: (х1, х2), (х2, х3), (х3, х4), (х4, х5), (х5, х6), (х6, х1)

    М6: (х1, х2), (х2, х3), (х3, х4), (х4, х5), (х5, х7), (х7, х6) (х6, х1)

    М7: (х2, х3), (х3, х4), (х4, х5), (х5, х7), (х7, х6), (х6, х1), (х1, х2)

    Какие из этих путей являются эйлеровыми контурами?

    Для графа, представленного на рисунке даны замкнутые пути:

    М1: (х2, х3), (х3, х4), (х4, х7), (х7, х2)

    М2: (х2, х3), (х3, х4), (х4, х5), (х5, х6), (х6, х2) (х2, х3), (х3, х7), (х7, х2)

    М3: (х2, х3), (х3, х4), (х4, х5), (х5, х6), (х6, х2)

    М4: (х3, х4), (х4, х5), (х5, х7), (х7, х3)

    М5: (х1, х2), (х2, х3), (х3, х4), (х4, х5), (х5, х6), (х6, х1)

    М6: (х1, х2), (х2, х3), (х3, х4), (х4, х5), (х5, х7), (х7, х6) (х6, х1)

    М7: (х2, х3), (х3, х4), (х4, х5), (х5, х7), (х7, х6), (х6, х1), (х1, х2)

    Какие из этих путей являются гамильтоновыми контурами?

    Для графа, представленного на рисунке даны замкнутые пути:

    М1: (х2, х3), (х3, х4), (х4, х7), (х7, х2)

    М2: (х2, х3), (х3, х4), (х4, х5), (х5, х6), (х6, х2) (х2, х3), (х3, х7), (х7, х2)

    М3: (х2, х3), (х3, х4), (х4, х5), (х5, х6), (х6, х2)

    М4: (х3, х4), (х4, х5), (х5, х7), (х7, х3)

    М5: (х1, х2), (х2, х3), (х3, х4), (х4, х5), (х5, х6), (х6, х1)

    М6: (х1, х2), (х2, х3), (х3, х4), (х4, х5), (х5, х7), (х7, х6) (х6, х1)

    М7: (х2, х3), (х3, х4), (х4, х5), (х5, х7), (х7, х6), (х6, х1), (х1, х2)

    Какие из этих путей являются контурами?

    Для графа, данного на рисунке определить между какой парой вершин большее количество путей длиной 2: A и C или B и D
    Для графа, данного на рисунке определить между какой парой вершин большее количество путей длиной 2: F и C или D и B
    Для графа, данного на рисунке определить между какой парой вершин большее количество путей длиной 2: F и C или E и C

    Для графа на рисунке даны маршруты из вершины A в вершину F:

    a) (A, B), (B, C), (C, G), (G, F)

    b) (A, K), (K, H), (H, F)

    c) (A, C), (C, E), (E, D), (D, C), (C, H), (H, F)

    d) (A, K), (K, H), (H, C), (C, K), (K, H), (H, F)

    Найти среди них простые цепи

    Для графа на рисунке даны маршруты из вершины A в вершину F:

    a) (A, B), (B, C), (C, G), (G, F)

    b) (A, K), (K, H), (H, F)

    c) (A, C), (C, E), (E, D), (D, C), (C, H), (H, F)

    d) (A, K), (K, H), (H, C), (C, K), (K, H), (H, F)

    Найти среди них цепи