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

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

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

1

2

3

4

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

1

2

3

4

52) Каково реберное хроматическое число дерева с максимальной степенью вершин равной k?

2

k – 1

k

k + 1

53) Пусть из простого цикла с 13 вершинами удалили две смежные вершины. Каково вершинное хроматическое число полученного графа?

1

2

3

4

54) Пусть из простого цикла с 12 вершинами удалили две смежные вершины. Каково реберное хроматическое число полученного графа?

1

2

3

4

55) Сколько внутренних граней имеет плоское колесо на n вершинах?

n/2

n – 1

n

n + 1

56) Пусть из полного графа на n вершинах удалили одно ребро. Каково вершинное хроматическое число полученного графа?

n/2

n –1

n

n + 1

57) Сколько существует неизоморфных деревьев на с 4 вершинами?

1

2

3

4

58) Чему может быть равна максимальная степень вершины в n-вершинном графе?

n –2

n – 1

n

n + 1

59) Чему может быть равна максимальная степень вершины в n-вершинном дереве?

n –2

n – 1

n

n + 1

60) Чему может быть равна максимальная степень вершины в n-вершинном простом цикле?

1

2

3

n – 1

61) Чему может быть равна максимальная степень вершины в n-вершиннй простой цепи?

2

3

4

n – 1

62) Чему соответствует элемент 1 в матрице смежности простого графа?

вершине ребру грани цепи

63) В каком графе нет циклов нечетной длины?

эйлеровом двудольном гамильтоновом полном

64) Вершины какого графа всегда можно покрасить в два цвета?

эйлерового гамильтонового двудольного полного

65) Чему равна сумма расстояний между всеми вершинами в полном n-вершинном графе?

2n

n(n–1)/2

n²

n²/2

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

n/2

n – 1

n + 1

2n

67) Сколько красок достаточно для раскраски граней карты?

1

2

3

4

68) Граф, в котором степени всех вершин четные, называется

реберным двойственным эйлеровым гамильтоновым

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

2 2 2 2 2 2

3 3 3 3 3 3

1 1 1 1 1 5

2 2 2 2 2 6

79) Какой граф будет эйлеровым, но не гамильтоновым?

простой цикл на 7 вершинах колесо на 8 вершинах два треугольника, имеющие одну общую вершину полный граф на 10 вершинах

80) Какой граф будет гамильтоновым, но не эйлеровым?

простой цикл на 7 вершинах колесо на 8 вершинах два треугольника, имеющие одну общую вершину полный граф на 9 вершинах

81) Если в простой цикл нечетной длины добавить произвольное ребро, то какое максимальное вершинное хроматическое число может иметь полученный граф?

2

3

4

5

82) Если в простой цикл четной длины добавить произвольное ребро, то какое максимальное вершинное хроматическое число может иметь полученный граф?

2

3

4

5

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

от 3 до n – 1

только 3

только n – 3

только n – 1

84) Какие степени могут иметь вершины в плоской n-вершинной триангуляции?

от 3 до n – 1

только 3

только n – 3

только n – 1

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

n – 1

n

n/2

n – 2

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

2n – 2

n(n – 1)/2

n(n – 1)

n²/2

87) Граф, нарисованный на сфере без пересечений ребер, называется

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

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

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

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

полный граф на 6 вершинах 

89) Сколько ребер содержит эйлеров цикл в m-реберном графе?

m – 2

m – 1

m

m + 1

90) Сколько вершин содержит гамильтонов цикл в n-вершинном графе?

n – 3

n – 2

n – 1

n

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

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

92) В каких графах число вершин всегда равно числу ребер?

в планарных графах в простых циклах в простых цепях в реберных графах

93) Число ребер в n-вершинной звезде равно

n – 1

n

n + 1

2n

94) Геометрически двойственный граф содержит петлю, если в исходном плоском графе

есть пара несмежных граней есть пара граней, имеющие границу из более чем одного ребра все внутренние грани смежны с бесконечной гранью есть мост

95) Чему равно цикломатическое число простого цикла четной длины?

1

2

3

4

96) Чему равно цикломатическое число колеса на 6 вершинах?

2

3

4

5

97) Для какого графа вершинное и реберное хроматические числа оба равны 2?

для простой цепи на 6 вершинах для простого цикла на 7 вершинах для полного графа на 8 вершинах для полного двудольного графа на 9 вершинах

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

1

n – 1

n

n + 1

99) Какой набор степеней вершин в 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

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

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