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

Упражнение 1:

Номер 1

Построить все возможные пути длиной 2 в графе, изображенном на рисунке для вершин A  и E.

Ответ:

(1) A → B → B, A → В → C, E → F → A, E → B → B, E → B → C, E → F → D

(2) A → В → C, E → F → A, E → B → C, E → F → D

(3) A → В → C, E → F → A, E → B → B, E → B → C, E → F → D

Номер 2

Построить все возможные пути длиной 2 в графе, изображенном на рисунке  для вершин   A  и D.

Ответ:

(1) A → В → C, D → E → F, D → F → D

(2) A → B → B, A → В → C, D → E → F, D → F → D, D → F → A, D → E → B

(3) A → В → C, D → E → F

Номер 3

Построить все возможные пути длиной 2 в графе, изображенном на рисунке  для вершин E  и B

Ответ:

(1) E → F → A, E → B → B, E → B → C, E → F → D, B → В → C

(2) E → F → A, E → B → C, E → F → D

(3) E → F → A, E → B → C, E → F → D, B → В → C

Упражнение 2:

Номер 1

Построить  орцепи максимальной длины из вершин A  и  B графа,  изображенного на рисунке

Ответ:

(1) (A, B) → (B, C), (B, С)

(2) (A, B) → (B, C), (B, B) → (B, C)

(3) (A, B) → (B, B) → (B, C), (B, B) → (B, C)

Номер 2

Построить  орцепи максимальной длины из вершин D  и  B графа,  изображенного на рисунке

Ответ:

(1)

(B, C),  (D, E) →  (E, F) →  
 →  (F, D) →  (D, F) →  (F, A) →  (A, B)  → (B, C)

(2)

 (B, B) →  (B, C),  (D, E) →  (E, F) →  
 →  (F, D) →  (D, F) →  (F, A) →  (A, B) →  (B, B)  → (B, C)

(3)

(B, B) →  (B, C),  (D, E) →  (E, F) →  
 →  (F, D) →  (D, F) →  (F, A) →  (A, B)  → (B, C)

Номер 3

Построить  орцепи максимальной длины из вершин E  и F графа,  изображенного на рисунке

Ответ:

(1) (E, F) → (F, D) → (D, F) → (F, A) → (A, B) → (B, C), (F, D) →

(2)

(E, F) →  (F, D) →  (D, F) →  (F, A) →  (A, B) →  (B,B)  → (B, C), (F, D) →  (D, F) →  (F, A) →  (A, B) →  (B, B)  → (B, C)

(3)

(E, F) →  (F, D) →  (D, F) →  (F, A) →  (A, B)  → (B, C), (F, D) →  (D, F) →  (F, A) →  (A, B)  → (B, C)

Упражнение 3:

Номер 1

Построить простые орцепи максимальной длины из  вершин  A  и  B графа, изображенного на рисунке

Ответ:

(1) (A, B) → (B, B) → (B, C), (B, C)

(2) (A, B) → (B, B) → (B, C), (B, B) → (B, C)

(3) (A, B) → (B, C), (B, C)

Номер 2

Построить простые орцепи максимальной длины из  вершин  A  и  D  графа, изображенного на рисунке

Ответ:

(1)

(A, B) →  (B, C),  (D, E) →  (E, F) →  (F, A) →  (A, B) →  (B, C)

(2)

(A, B) →  (B, C), (D, E) →  (E, F) →  (F, A) →  (A, B) →  (B, B)  →   (B, C)

(3) (A, B) → (B, B) → (B, C), (D, E) → (E, F) → (F, A) → (A, B) → (B, C)

Номер 3

Построить простые орцепи максимальной длины из  вершин  F  и  E  графа, изображенного на рисунке

Ответ:

(1) (E, F) → (F, A) → (A, B) → (B, B) → (B, C), (F, A) → (A, B) → (B, C)

(2) (E, F) → (F, A) → (A, B) → (B, C), (F, A) → (A, B) → (B, C)

(3) (E, F) → (F, A) → (A, B) → (B, C), (F, A) → (A, B) → (B, B) → (B, C)

Упражнение 4:

Номер 1

Для графа на рисунке даны маршруты из вершины  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)


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

Ответ:

(1) a, b

(2) a, b, c

(3) a, b, c, d

Номер 2

Для графа на рисунке даны маршруты из вершины  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)


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

Ответ:

(1) a, c

(2) a, b

(3) a, b, c

Номер 3

Для графа на рисунке даны маршруты из вершины A в вершину F:
         a) (A, B), (B, C), (C, F) 


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


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


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

Ответ:

(1) a, b, c

(2) a, b

(3) a

Упражнение 5:

Номер 1

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

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

v_n=∑ a_i/ ∑ b_i

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) 3

(2) 1

(3) 2

(4) 4

Номер 2

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

Ответ:

(1) A → D → B → C → E → A

(2) A → B → C → E → D → B

(3) A → B → C → D → E → A

(4) A → C → E → D → B → A

Номер 3

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

Ответ:

(1) A → B → C → D → E → A

(2) A → B → C → E → D → B

(3) A → D → B → C → E → A

Упражнение 6:

Номер 1


        Для графа, представленного на рисунке  даны замкнутые пути:
        М₁: (х₂, х₃), (х₃, х₄), (х₄, х₇), (х₇,   х₂)
         М₂: (х₂, х₃), (х₃, х₄), (х₄, х₅), (х₅, х₆),    (х₆, х₂) (х₂, х₃), (х₃, х₇), (х₇, х₂)
         М₃: (х₂, х₃), (х₃, х₄), (х₄, х₅), (х₅, х₆), (х₆, х₂)
         М₄: (х₃, х₄), (х₄, х₅), (х₅, х₇), (х₇, х₃)


         М₅: (х₁, х₂), (х₂, х₃), (х₃, х₄), (х₄, х₅), (х₅, х₆), (х₆, х₁)


         М₆: (х₁, х₂), (х₂, х₃), (х₃, х₄), (х₄, х₅), (х₅, х₇), (х₇, х₆) (х₆, х₁)


         М₇: (х₂, х₃), (х₃, х₄), (х₄, х₅), (х₅, х₇), (х₇, х₆), (х₆, х₁), (х₁, х₂)


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

Ответ:

(1) контурами являются: M₁, M₂,M₃, М₄, М₅, М₆, М₇

(2) контурами являются: M₁, M₃, М₄, М₅, М₆, М₇

(3) контурами являются: M₁, M₂, М₄, М₅, М₆

Номер 2


        Для графа, представленного на рисунке  даны замкнутые пути:
        М₁: (х₂, х₃), (х₃, х₄), (х₄, х₇), (х₇,   х₂)
         М₂: (х₂, х₃), (х₃, х₄), (х₄, х₅), (х₅, х₆),    (х₆, х₂) (х₂, х₃), (х₃, х₇), (х₇, х₂)
         М₃: (х₂, х₃), (х₃, х₄), (х₄, х₅), (х₅, х₆), (х₆, х₂)
         М₄: (х₃, х₄), (х₄, х₅), (х₅, х₇), (х₇, х₃)


         М₅: (х₁, х₂), (х₂, х₃), (х₃, х₄), (х₄, х₅), (х₅, х₆), (х₆, х₁)


         М₆: (х₁, х₂), (х₂, х₃), (х₃, х₄), (х₄, х₅), (х₅, х₇), (х₇, х₆) (х₆, х₁)


         М₇: (х₂, х₃), (х₃, х₄), (х₄, х₅), (х₅, х₇), (х₇, х₆), (х₆, х₁), (х₁, х₂)


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

Ответ:

(1) гамильтоновыми контурами являются:

 М₆, М₇

(2) гамильтоновыми контурами являются: М₄, М₆

(3) гамильтоновыми контурами являются: M₂, М₄, М₆, М₇

Номер 3


        Для графа, представленного на рисунке  даны замкнутые пути:
        М₁: (х₂, х₃), (х₃, х₄), (х₄, х₇), (х₇,   х₂)
         М₂: (х₂, х₃), (х₃, х₄), (х₄, х₅), (х₅, х₆),    (х₆, х₂) (х₂, х₃), (х₃, х₇), (х₇, х₂)
         М₃: (х₂, х₃), (х₃, х₄), (х₄, х₅), (х₅, х₆), (х₆, х₂)
         М₄: (х₃, х₄), (х₄, х₅), (х₅, х₇), (х₇, х₃)


         М₅: (х₁, х₂), (х₂, х₃), (х₃, х₄), (х₄, х₅), (х₅, х₆), (х₆, х₁)


         М₆: (х₁, х₂), (х₂, х₃), (х₃, х₄), (х₄, х₅), (х₅, х₇), (х₇, х₆) (х₆, х₁)


         М₇: (х₂, х₃), (х₃, х₄), (х₄, х₅), (х₅, х₇), (х₇, х₆), (х₆, х₁), (х₁, х₂)


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

Ответ:

(1) эйлеровыми контурами являются M₂, М₇

(2) эйлеровыми контурами являются М₄, М₆

(3) эйлеровых контуров нет

Упражнение 7:

Номер 1

Для графа, представленного на рисунке  построить гамильтоновы и эйлеровы циклы.

Ответ:

(1) эйлеров цикл –(F, C), (C, A), (A, F), (F, E), (E, D), (D, C), (C, B), (B, D) или

(D, C), (C, B), (B, D), (D, E), (E, F), (F, C), (C, A), (A, F)

(2) гамильтонов цикл :

(A, C),  (C, B), (B, D), (D, E), 
(E, F), (F, A)

; эйлеров цикл отсутствует

(3) гамильтонов цикл отсутствует, эйлеров цикл отсутствует

Номер 2

Для графа, представленного на рисунке  построить гамильтоновы и эйлеровы циклы.

Ответ:

(1) гамильтонов цикл отсутствует, эйлеров цикл – (х₁, х₂), (х₂, х₃), (х₃, х₄), (х₄, х₆), (х₆, х₅), (х₅, х₁)

(2) гамильтоновы циклы:(х₁, х₂), (х₂, х₃), (х₃, х₄), (х₄, х₆), (х₆, х₅), (х₅, х₁) или (х₅, х₁), (х₁, х₂), (х₂, х₃), (х₃, х₄), (х₄, х₆), (х₆, х₅); эйлеров цикл отсутствует

(3) гамильтонов цикл:(х₁, х₂), (х₂, х₃), (х₃, х₄), (х₄, х₆), (х₆, х₅), (х₅, х₁) ; эйлеров цикл:

(х₅, х₁), (х₁, х₂),  (х₂, х₃), (х₃, х₄), (х₄, х₆), (х₆, х₅)

Номер 3

Для графа, представленного на рисунке   построить гамильтонов цикл и эйлеров путь.

Ответ:

(1) гамильтонов цикл: A → B → C → D → E → A; эйлеров цикл:

 B  →  C  →  D  →  A  →  B  →  D  →  E  →  A  →  C

(2) гамильтонов цикл: A → B → D → C → A → E; эйлеров цикл:

 B  →  C  →  D  →  A  →  B  →  D  →  E  →  A  →  C

(3) гамильтонов цикл: A → B → C → D → E → A; эйлеров цикл:

 A  → B  →  C  →  D  →  A  →  C  →  B  →  D  →  E  →  A

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