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

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

Номер 1

Для графа, представленного на рисунке 1 построить матрицу достижимости R а X₁ X₂ X₃ X₄ X₅
X₁ 1 1 1 1 1
R= X₂ 0 0 1 1 1
X₃ 0 0 1 1 0
X₄ 0 0 0 1 0
X₅ 0 0 0 1 1
б X₁ X₂ X₃ X₄ X₅
X₁ 1 1 1 1 1
R= X₂ 0 0 1 1 1
X₃ 0 0 0 1 0
X₄ 0 0 0 0 0
X₅ 0 0 0 1 0 в X₁ X₂ X₃ X₄ X₅
X₁ 1 1 1 1 1
R= X₂ 0 1 1 1 1
X₃ 0 0 1 1 0
X₄ 0 0 0 1 0
X₅ 0 0 0 1 1

Ответ:

(1) б

(2) а

(3) в

Номер 2

Какая из представленных матриц достижимости соответствует графу на рисунке 1?
а X₁ X₂ X₃ X₄ X₅ X₆
X₁ 0 0 0 1 1 1
R= X₂ 1 0 1 1 1 1
X₃ 1 0 0 1 1 1
X₄ 1 0 0 0 1 1
X₅ 1 0 0 1 0 1
X₆ 1 0 0 1 1 0
б X₁ X₂ X₃ X₄ X₅ X₆
X₁ 1 0 0 1 1 1
R= X₂ 1 1 1 1 1 1
X₃ 1 0 1 1 1 1
X₄ 1 0 0 1 1 1
X₅ 1 0 0 1 1 1
X₆ 1 0 0 1 1 1 в X₁ X₂ X₃ X₄ X₅ X₆
X₁ 1 1 1 1 1 1
R= X₂ 0 1 0 0 0 0
X₃ 0 1 1 0 0 0
X₄ 1 1 1 1 1 1
X₅ 1 1 1 1 1 1
X₆ 1 1 1 1 1 1

Ответ:

(1) а

(2) б

(3) в

Номер 3

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

Ответ:

(1) Х₁

(2) Х₂

(3) Х₁ и Х₂

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

Номер 1

Для графа, приведенного на рисунке 1, найти матрицу контрдостижимости. а X₁ X₂ X₃ X₄ X₅
X₁ 1 0 0 0 0
Q= X₂ 1 1 0 0 0
X₃ 1 1 1 0 0
X₄ 1 0 1 1 1
X₅ 1 1 0 0 1
б X₁ X₂ X₃ X₄ X₅
X₁ 1 0 0 0 0
Q= X₂ 1 1 0 0 0
X₃ 1 1 1 0 0
X₄ 1 1 1 1 1
X₅ 1 1 0 0 1 в X₁ X₂ X₃ X₄ X₅
X₁ 1 0 0 0 0
Q= X₂ 1 1 0 0 0
X₃ 1 1 1 0 0
X₄ 1 1 1 1 0
X₅ 1 1 0 0 1

Ответ:

(1) а

(2) в

(3) б

Номер 2

Какая из представленных  матриц контрдостижимости соответствует графу на рис. 1?
а X₁ X₂ X₃ X₄ X₅ X₆
X₁ 0 0 0 1 1 1
Q= X₂ 1 0 1 1 1 1
X₃ 1 0 0 1 1 1
X₄ 1 0 0 0 1 1
X₅ 1 0 0 1 0 1
X₆ 1 0 0 1 1 0
б X₁ X₂ X₃ X₄ X₅ X₆
X₁ 1 0 0 1 1 1
Q= X₂ 1 1 1 1 1 1
X₃ 1 0 1 1 1 1
X₄ 1 0 0 1 1 1
X₅ 1 0 0 1 1 1
X₆ 1 0 0 1 1 1 в X₁ X₂ X₃ X₄ X₅ X₆
X₁ 1 1 1 1 1 1
Q= X₂ 0 1 0 0 0 0
X₃ 0 1 1 0 0 0
X₄ 1 1 1 1 1 1
X₅ 1 1 1 1 1 1
X₆ 1 1 1 1 1 1

Ответ:

(1) а

(2) б

(3) в

Номер 3

Для графа, представленного на рисунке  построить матрицу контрдостижимости и определить какая из вершин достижима для наибольшего числа вершин графа.

Ответ:

(1) Х₁

(2) Х₄

(3) Х₂

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

Номер 1

Для графа, представленного на рисунке, найти: вершины, входящие в путь между вершинами  х₁ и  х₇.

Ответ:

(1) {х₁, х₂, х₃, х₄ }

(2) {х₁, х₂, х₄, х₇}

(3) { х₁, х₂, х₃, х₄, х₇}

Номер 2

Для графа, представленного на рисунке, найти: вершины, входящие в путь между вершинами  х₁ и х₆.

Ответ:

(1) {х₁, х₂, х₃, х₄, х₆, х₇}

(2) {х₁, х₂, х₃, х₄, х₇}

(3) {х₁, х₂, х₅, х₄ }

Номер 3

Для графа, представленного на рисунке, найти: вершины, входящие в путь между вершинами  х₁и х₃.

Ответ:

(1) {х₁, х₂, х₃, х₇}

(2) {х₁, х₂, х₃, х₄ , х₇}

(3) {х₁, х₂, х₃, х₄}

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

Номер 1

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

Ответ:

(1) между F и A

(2) между D и B

(3) между E и C

Номер 2

Для графа, данного на рисунке  найти количество путей длиной 2 между всеми вершинами графа.

Ответ:

(1) 8

(2) 18

(3) 13

Номер 3

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

Ответ:

(1) одинаковое количество

(2) между D и B

(3) между F и C

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

Номер 1

Для графа, данного на рисунке найти между какими вершинами наибольшее число путей длиной 3.

Ответ:

(1) между D и B

(2) между A и D

(3) между A и C

Номер 2

Для графа, данного на рисунке найти количество путей длиной 3 между всеми вершинами графа.

Ответ:

(1) 13

(2) 9

(3) 11

Номер 3

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

Ответ:

(1) между Aи C

(2) одинаковое количество

(3) между B и D

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

Номер 1

Для графа, данного на рисунке найти количество путей длиной 4 между всеми вершинами графа

Ответ:

(1) 14

(2) 24

(3) 15

Номер 2

Для графа, данного на рисунке найти между какими вершинами наибольшее число путей длиной 4.

Ответ:

(1) между B и A

(2) между A и C

(3) между D и C

(4) между D и B

Номер 3

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

Ответ:

(1) между F и C

(2) одинаковое количество

(3) между E и C

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