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

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

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

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

М₄: (х₃, х₄), (х₄, х₅), (х₅, х₇), (х₇, х₃)

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

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

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

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

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

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

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

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

М₄: (х₃, х₄), (х₄, х₅), (х₅, х₇), (х₇, х₃)

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

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

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

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

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

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

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

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

М₄: (х₃, х₄), (х₄, х₅), (х₅, х₇), (х₇, х₃)

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

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

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

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

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

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

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

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

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

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

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

Для графа G = (X, A) , представленного на рисунке, описать явно остовный подграф(X, A’) , где x_i,x_j ∈X тогда и только тогда, когда i+j четно

Для графа G = (X, A) , представленного на рисунке, описать явно остовный подграф(X, A’) , где x_i,x_j ∈ A' тогда и только тогда, когда i+j нечетно