5 липня о 18:00Вебінар: «Щоденні-3» та «Щоденні-5»: незамінна частина уроку в Новій українській школі

Способи представлення графів

Додано: 11 січня
Предмет: Інформатика, 9 клас
10 запитань
Запитання 1

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


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

5

0 1 0 0 0

1 0 1 1 0

0 1 0 0 0

0 1 0 0 0

0 0 0 0 0


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

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

3

6

5

19

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

Запитання 2

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


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

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


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

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

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

2

0

1


1

1

1

1

2

1

0

1

0

Створюйте онлайн-тести
для контролю знань і залучення учнів
до активної роботи у класі та вдома

Створити тест