Способи представлення графів | Тест з інформатики

Запитання 1

В галактиці "Milky Way" на планеті "Neptune" є N міст, деякі з яких з'єднані дорогами. Імператор "Maximus" галактики "Milky Way" вирішив провести інвентаризацію доріг на планеті "Neptune". Але, як виявилося, він не сильний в математиці, тому він просить вас порахувати кількість доріг.

У першому рядку задається число N (0 ≤ N ≤ 100). У наступних N рядках міститься по N чисел, кожне з яких є одиницею або нулем. Причому, якщо в позиції (i, j) квадратної матриці стоїть одиничка, то i-ий і j-ий міста з'єднані дорогами, а якщо нуль, то вони не з'єднані.

Знайдіть одне число - кількість доріг на планеті "Neptune".

5

0 1 0 0 0

1 0 1 1 0

0 1 0 0 0

0 0 0 0 0

варіанти відповідей

3

6

5

19

Немає вірного

Запитання 2

В галактиці "Milky Way" на планеті "Neptune" є N міст, деякі з яких з'єднані дорогами. Імператор "Maximus" галактики "Milky Way" вирішив провести інвентаризацію доріг на планеті "Neptune". Але, як виявилося, він не сильний в математиці, тому він просить вас порахувати кількість доріг.

У першому рядку задається число N (0 ≤ N ≤ 100). У наступних N рядках міститься по N чисел, кожне з яких є одиницею або нулем. Причому, якщо в позиції (i, j) квадратної матриці стоїть одиничка, то i-ий і j-ий міста з'єднані дорогами, а якщо нуль, то вони не з'єднані.

Знайдіть одне число - кількість доріг на планеті "Neptune".

8

0 1 0 0 1 0 1 0

1 0 0 0 0 0 0 1

0 0 0 1 1 0 0 0

0 0 1 0 1 0 1 0

1 0 1 1 0 0 0 1

0 0 0 0 0 0 1 1

1 0 0 1 0 1 0 0

0 1 0 0 1 1 0 0

варіанти відповідей

11

22

8

42

Інший варіант

Запитання 3

У підземеллі M тунелів і N перехресть, кожен тунель з'єднує якісь два перехрестя. Мишачий король вирішив поставити по світлофору в кожному тунелі перед кожним перехрестям. Напишіть програму, яка порахує, скільки світлофорів повинно бути встановлено на кожному з перехресть. Перехрестя пронумеровані числами від 1 до N.

Перший рядок вхідних даних містить два числа N і M (0 <N ≤ 100, 0 ≤ M ≤ N * (N - 1) / 2). У кожному з наступних M рядків записані по два числа i і j (1 ≤ i, j ≤ N), які означають, що перехрестя i і j з'єднані тунелем.

7 10

5 1

3 2

7 1

5 2

7 4

6 5

6 4

7 5

2 1

5 3

Потрібно вивести N чисел: k-е число означає кількість світлофорів на k-му перехресті.

Примітка. Можна вважати, що будь-які два перехрестя з'єднані не більше, ніж одним тунелем. Немає тунелів від перехрестя i до нього самого.

Рекомендація: представьте граф у графічному вигляді.

варіанти відповідей

3 3 2 2 5 2 3

1 2 3 4 5 6 7

1 2 3 4 5 6 7 8 9 10

2 3 3 5 2 5 2 2

Запитання 4

У підземеллі M тунелів і N перехресть, кожен тунель з'єднує якісь два перехрестя. Мишачий король вирішив поставити по світлофору в кожному тунелі перед кожним перехрестям. Напишіть програму, яка порахує, скільки світлофорів повинно бути встановлено на кожному з перехресть. Перехрестя пронумеровані числами від 1 до N.

Перший рядок вхідних даних містить два числа N і M (0 <N ≤ 100, 0 ≤ M ≤ N * (N - 1) / 2). У кожному з наступних M рядків записані по два числа i і j (1 ≤ i, j ≤ N), які означають, що перехрестя i і j з'єднані тунелем.

6 7

1 6

2 4

5 3

6 3

6 2

2 5

4 6

Потрібно вивести N чисел: k-е число означає кількість світлофорів на k-му перехресті.

Примітка. Можна вважати, що будь-які два перехрестя з'єднані не більше, ніж одним тунелем. Немає тунелів від перехрестя i до нього самого.

Рекомендація: представте граф у графічному вигляді.

варіанти відповідей

1 3 2 2 2 4

1 2 3 4 5 6

1 2 3 4 5 6 7

4 2 2 2 3 1

Запитання 5

За заданою квадратною матрицею n × n, яка складається із нулів і одиниць визначте, чи може дана матриця бути матрицею суміжності простого неорієнтованого графа.

5

0 0 1 0 0

0 0 1 0 1

1 1 0 0 0

0 0 0 0 0

0 1 0 0 0

варіанти відповідей

так

ні

Запитання 6

За заданою квадратною матрицею n × n, яка складається із нулів і одиниць визначте, чи може дана матриця бути матрицею суміжності простого неорієнтованого графа.

10

0 1 1 1 1 1 0 1 1 1

1 1 0 1 1 1 1 1 1 1

1 0 0 1 0 1 1 1 1 1

1 1 1 0 1 0 1 1 1 1

1 1 0 1 0 1 0 1 1 1

1 1 1 0 1 0 1 1 1 0

0 1 1 1 0 1 0 1 1 0

1 1 1 1 1 1 1 0 1 1

1 1 1 1 1 1 1 1 0 1

1 1 1 1 1 0 0 1 1 0

варіанти відповідей

так

ні

Запитання 7

За заданою матрицею суміжності неорієнтованого графа визначте, чи містить він петлі і якщо так, то скільки.

5

1 1 1 1 0

1 0 1 1 1

1 1 0 1 1

1 1 1 1 1

0 1 1 1 0

варіанти відповідей

2

не містить

1

3

4

Запитання 8

Простий неорієнтовані граф заданий матрицею суміжності, виведіть його представлення у вигляді списку ребер.

5

0 0 1 0 0

0 0 1 0 1

1 1 0 0 0

0 0 0 0 0

0 1 0 0 0

варіанти відповідей

1 3

2 3

2 5

1 1

2 2

3 3

4 4

5 5

2 4

5 3

1 2

5 2

2 3

3 4

3 5

1 5

Запитання 9

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

5 3

1 3

2 3

2 5

варіанти відповідей

0 0 1 0 0

0 0 1 0 1

1 1 0 0 1

0 0 0 0 0

0 1 1 0 0

1 1 0 1 1

1 1 0 1 0

0 0 1 1 1

1 1 1 1 1

1 0 1 1 1

0 0 0 0

0 0 0 1

1 1 0 0

0 0 0 0

Запитання 10

Неорієнтовані граф заданий матрицею суміжності. Знайдіть ступені всіх вершин графа.

5

0 0 1 0 0

0 0 1 0 1

1 1 0 0 0

0 0 0 0 0

0 1 0 0 0

варіанти відповідей

1

2

0

1

2

1

0

1

0