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

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

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

Для графа на рисунке даны маршруты из вершины 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, b (Верный ответ)
a, b, c
a, 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, F)

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

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

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

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

М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: F и C или D и B
Для графа, данного на рисунке определить между какой парой вершин большее количество путей длиной 2: A и C или B и D
Для графа, данного на рисунке определить между какой парой вершин большее количество путей длиной 2: F и C или E и C
Для графа G = (X, A) , представленного на рисунке, описать явно остовный подграф(X, A’) , где xi,xj ∈X тогда и только тогда, когда i+j четно
Для графа G = (X, A) , представленного на рисунке, описать явно остовный подграф(X, A’) , где xi,xj ∈ A' тогда и только тогда, когда i+j нечетно