Выдержка из текста работы
50) Пусть в дереве две несмежные вершины, находящиеся на расстоянии 4 друг от друга, соединили новым ребром. Каково вершинное хроматическое число полученного графа?
51) Пусть в дереве две несмежные вершины, находящиеся на расстоянии 5 друг от друга, соединили новым ребром. Каково вершинное хроматическое число полученного графа?
52) Каково реберное хроматическое число дерева с максимальной степенью вершин равной k?
k – 1
k + 1
53) Пусть из простого цикла с 13 вершинами удалили две смежные вершины. Каково вершинное хроматическое число полученного графа?
54) Пусть из простого цикла с 12 вершинами удалили две смежные вершины. Каково реберное хроматическое число полученного графа?
55) Сколько внутренних граней имеет плоское колесо на n вершинах?
n – 1
n + 1
56) Пусть из полного графа на n вершинах удалили одно ребро. Каково вершинное хроматическое число полученного графа?
n –1
n + 1
57) Сколько существует неизоморфных деревьев на с 4 вершинами?
58) Чему может быть равна максимальная степень вершины в n-вершинном графе?
n –2
n – 1
n + 1
59) Чему может быть равна максимальная степень вершины в n-вершинном дереве?
n –2
n – 1
n + 1
60) Чему может быть равна максимальная степень вершины в n-вершинном простом цикле?
n – 1
61) Чему может быть равна максимальная степень вершины в n-вершиннй простой цепи?
n – 1
62) Чему соответствует элемент 1 в матрице смежности простого графа?
вершине
ребру
грани
цепи
63) В каком графе нет циклов нечетной длины?
эйлеровом
двудольном
гамильтоновом
полном
64) Вершины какого графа всегда можно покрасить в два цвета?
эйлерового
гамильтонового
двудольного
полного
65) Чему равна сумма расстояний между всеми вершинами в полном n-вершинном графе?
n(n–1)/2
n2/2
66) Сколько ребер нужно удалить из n-вершинного дерева, чтобы получился пустой граф?
n – 1
n + 1
67) Сколько красок достаточно для раскраски граней карты?
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) Если в простой цикл нечетной длины добавить произвольное ребро, то какое максимальное вершинное хроматическое число может иметь полученный граф?
82) Если в простой цикл четной длины добавить произвольное ребро, то какое максимальное вершинное хроматическое число может иметь полученный граф?
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 – 2
86) Максимальное число ребер в простом связном n-вершинном графе равно
2n – 2
n(n – 1)/2
n(n – 1)
n2/2
87) Граф, нарисованный на сфере без пересечений ребер, называется
гладким
плоским
гомеоморфным
двойственным
88) Какой из указанных графов является планарным?
полный граф на 5 вершинах
полный двудольный граф с долями 3 и 3
полный двудольный граф с долями 2 и 3
полный граф на 6 вершинах
89) Сколько ребер содержит эйлеров цикл в m-реберном графе?
m – 2
m – 1
m + 1
90) Сколько вершин содержит гамильтонов цикл в n-вершинном графе?
n – 3
n – 2
n – 1
91) Чему равно число вершин геометрически двойственного графа?
числу ребер исходного плоского графа
числу вершин исходного плоского графа
числу граней исходного плоского графа
сумме числа вершин и ребер исходного плоского графа
92) В каких графах число вершин всегда равно числу ребер?
в планарных графах
в простых циклах
в простых цепях
в реберных графах
93) Число ребер в n-вершинной звезде равно
n – 1
n + 1
94) Геометрически двойственный граф содержит петлю, если в исходном плоском графе
есть пара несмежных граней
есть пара граней, имеющие границу из более чем одного ребра
все внутренние грани смежны с бесконечной гранью
есть мост
95) Чему равно цикломатическое число простого цикла четной длины?
96) Чему равно цикломатическое число колеса на 6 вершинах?
97) Для какого графа вершинное и реберное хроматические числа оба равны 2?
для простой цепи на 6 вершинах
для простого цикла на 7 вершинах
для полного графа на 8 вершинах
для полного двудольного графа на 9 вершинах
98) Сколько компонент связности будет иметь граф, полученный удалением n – 1 ребра из n-вершинного дерева?
n – 1
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
