Математическая вертикаль. Графы

Тест на проверку основных понятий, связанных с темой графы: ребра, вершины, связность, степень вершин.

Задание 1

Какое максимальное число ребер может быть в графе на 150 вершинах?

Задание 2

Вася выписал в ряд степени всех вершин графа. Какие наборы чисел он мог написать?

Задание 3

На рисунке изображен граф. Найдите степень вершины D.

Задание 4

На рисунке изображен граф. Заполните таблицу: а) сколько у него вершин; б) сколько у него ребер; в) запишите степени вершин в порядке возрастания через пробел. Например: 1 2 2 4 4 5 5

Задание 5

В графе n вершин, степень каждой вершины равна k. Чему НЕ могут быть равны n и k? Выберите все варианты.

Задание 6

Сколько компонент связности в изображенных графах?

Задание 7

На рисунке изображен граф. Найдите степень вершины С.

Задание 8

На каких рисунках изображен связный граф?

Задание 9

В графе вершины пронумерованы числами от 2 до 10, причем вершины соединены ребром, если числа, записанные в них, не взаимно просты. Сколько компонент связности в этом графе?

Задание 10

Рассмотрим граф, вершины которого соответствуют натуральным числам от 1 до 12. Две вершины в нашем графе будут соединены ребром тогда и только тогда, когда разность соответствующих чисел делится на 3. Сколько компонент связности в этом графе?

Задание 11

В некотором графе 5 вершин, степени которых равны 4; 2; 2; 1; 3. Сколько ребер в этом графе?

Задание 12

В некотором государстве 10 городов и 20 дорог. Авиалиния есть между двумя городами в том и только в том случае, если между ними нет дороги. Сколько авиалиний в таком государстве?