Тест из 100 вопросов по дисциплине "Дискретная математика" (Для какого графа его геометрически двойственный граф будет мультиребром? Какой из указанных графов является не планарным?)

Вопросы по дискретной математике

1) Для какого графа его геометрически двойственный граф будет мультиребром?

для простой цепи для простого цикла для звезды для колеса

2) Каково наименьшее число ребер, которые нужно удалить из полного n-вершинного графа для того, чтобы получить несвязный граф?

1

2

n – 1

n – 2

3) Каково наименьшее число ребер, которые нужно удалить из n-вершинного дерева для того, чтобы получить несвязный граф?

1

2

n – 2

n – 1

4) Каково наименьшее число ребер, которые нужно удалить из n-вершинного простого цикла  для того, чтобы получить несвязный граф?

1

2

n – 2

n – 1

5) Каково наименьшее число вершин, которые нужно удалить из n-вершинного простого цикла  для того, чтобы получить несвязный граф?

1

2

n – 2

n – 1

6) Каково наименьшее число вершин, которые нужно удалить из n-вершинной звезды для того, чтобы получить несвязный граф?

1

2

n – 2

n – 1

7) Каково наименьшее число ребер, которые нужно удалить из n-вершинной звезды для того, чтобы получить несвязный граф?

1

2

n – 2

n – 1

8) Минимальное число ребер в простом связном n-вершинном графе равно

n – 2

n – 1

n

n(n – 1)/2

9) Реберный граф простого цикла изоморфен

колесу простой цепи полному графу простому циклу

10) Какой граф из перечисленных на одном числе вершин содержит больше ребер?

простая цепь простой цикл полный двудольный граф полный граф

11) В каком графе из указанных (число вершин более 4) есть точно две вершины степени 1?

звезда простой цикл простая цепь колесо

12) Количество связных компонент в связном n-вершинном графе равно

0

1

2

n

13) Чему равно вершинное хроматическое число простого цикла на 23 вершинах?

2

3

4

19

14) Чему равна вершинная связность простого цикла на 23 вершинах?

1

2

3

12

15) Сколько висячих вершин содержит звезда на n вершинах?

2

n –2

n – 1

n

16) Наибольшее хроматическое число плоских n-вершинных графов не превосходит

1

2

3

4

17) Чему равно вершинное хроматическое число n-вершинных деревьев?

1

2

3

n –1

18) Какой n-вершинный граф содержит больше точек сочленения?

звезда простая цепь простой цикл колесо

19) Какой n-вершинный граф содержит больше мостов?

полный граф звезда простой цикл колесо

20) Чему равен диаметр полного n-вершинного графа?

1

2

n – 1

n

21) Чему равен диаметр полного n-вершинного двудольного графа?

1

2

n – 1

n

22) Чему равен диаметр n-вершинной звезды?

1

2

n – 1

n

23) Чему равен диаметр n-вершинной простой цепи?

1

2

n – 1

n

24) Чему равен диаметр n-вершинного простого цикла (n четно)?

2

n/2

n – 1

n

25) Чему равно реберное хроматическое число n-вершинной звезды?

1

2

n – 1

n

26) Сколько неизоморфных остовных подграфов имеет n-вершинный простой цикл?

1

2

n – 1

n

27) Сколько неизоморфных остовных подграфов имеет n-вершинное дерево?

1

2

n – 1

n

18) Сколько неизоморфных графов можно получить удалением одного ребра из n-вершинного простого цикла?

1

2

n – 1

n

29) Сколько неизоморфных графов можно получить удалением одного ребра из n-вершинной звезды?

1

2

n – 1

n

30) Сколько неизоморфных графов можно получить удалением одного ребра из n-вершинной простой цепи (n четно)?

2

n/2

n – 1

n

31) Чему равно цикломатическое число связного n-вершинного графа с n ребрами?

1

2

n – 1

n

32) Чему равно цикломатическое число графа, получаемого добавлением одного ребра в n-вершинное дерево?

1

2

n – 1

n

33) Какой граф может иметь все вершины с нечетной степенью?

эйлеров граф гамильтонов граф простая цепь полный граф с нечетным числом вершин

34) Когда полный n-вершинный графа с числом вершин более 3 содержит мост?

всегда никогда

n четное

n нечетное

35) Когда полный n-вершинный графа содержит точку сочленения?

всегда никогда

n четное

n нечетное

36) Когда простой n-вершинный цикл содержит мост?

всегда никогда

n четное

n нечетное

37) Сколько компонент связности будет иметь граф, получаемый из связного графа удалением вершины степени 1?

0

1

2

3

38) Сколько компонент связности будет иметь граф, получаемый из связного графа удалением висячего ребра?

1

2

3

4

39) Когда полный двудольный граф с долями из n и m вершин будет эйлеровым?

n и m оба нечетные

n и m оба четные

n четное, m нечетное

n нечетное, m четное

40) Какой набор чисел не может быть реализован степенями вершин графа?

2 2 2 2 2 2

2 2 2 3 3 3

2 2 2 2 3 3

3 3 3 3 3 3

41) Какое наименьшее число ребер нужно добавить к n-вершинному пустому графу, чтобы получить связный граф?

n/2

n – 2

n – 1

n

42) Сколько компонент связности содержит дополнение полного n-вершинного графа?

n/2

n – 2

n – 1

n

43) Какой набор степеней вершин в 6-вершинной звезде?

2 2 2 2 1 1

3 2 2 1 1 1

4 2 1 1 1 1

5 1 1 1 1 1

44) Какой из указанных графов является не планарным?

полный граф на 3 вершинах  полный граф на 4 вершинах полный граф на 5 вершинах полный двудольный граф с долями 2 и 3

45) Какой из указанных графов является не планарным?

полный граф на 4 вершинах полный двудольный граф с долями 2 и 3

полный двудольный граф с долями 3 и 3

колесо на 10 вершинах

46) Сколько ребер содержит дополнение полного n-вершинного графа?

0

n/2

n

n(n –1)/2

47) Пусть лес состоит из 2 деревьев, содержащих по 10 вершин. Каково наименьшее число ребер, которое нужно добавить, чтобы граф стал связным?

1

2

5

10

48) Чему равно число ребер геометрически двойственного графа?

числу ребер исходного плоского графа числу вершин исходного плоского графа числу граней исходного плоского графа сумме числа вершин  и ребер исходного плоского графа

49) Чему равно число граней геометрически двойственного графа?