дипломы,диссертации,курсовые,контрольные,рефераты,отчеты на заказ

Специальные главы математики. Часть 2.
Теория графов
Пермякова
Томск-2000

Указаны только правильные ответы, другие варианты можно узнать скачав файл из архива → Дис_мат2.АОИ.

Тема: Основные понятия и определения
дипломы,курсовые,рефераты,контрольные,диссертации,отчеты на заказ

№ 1
Граф без петель называется
• мультиграфом.

№ 2
В орграфе G вершина x смежна вершине y если
• в графе G есть дуга (x,y).

№ 3
В орграфе G вершина x инцидентна дуге v если
• вершина x либо начало дуги v, либо конец дуги v.

№ 4
Для любого неорграфа истинно выражение “Если вершина x смежна вершине y, то и вершина y смежна вершине x”
• Да.

№ 5
В любом произвольном неорграфе число вершин нечетной степени
• всегда четно.

№ 6
Дан граф G:

Чему равна степень вершины x1?
• 3

№ 7
Дан орграф G:

Чему равна полустепень захода вершины x1?
• 2

№ 8
Для любого орграфа всегда истинно выражение “Любая вершина графа смежна сама себе”
• Нет.

№ 9
Дан орграф G:

Чему равна полустепень исхода вершины x1?
• 4

№ 10
Граф с петлями и кратными ребрами называется
• псевдографом.

Тема: Операции над графами. Специальные виды графов. Орграфы и бинарные отношения

№ 1
Дан граф G

и граф G1
суграф графа
• граф G1 - суграф графа G;
• граф G1 - собственный подграф графа G.

№ 2
Дан граф G:

• граф G не является двудольным графом.

№ 3
Число ребер полного графа на n вершинах равно:
• (n*(n-1)) / 2.

№ 4
Граф K2,3 изображен на рисунке

• в

№ 5
Дан граф G

и граф G1
собственный подграф графа
• граф G1 - собственный подграф графа G.

№ 6
Дан граф G

и граф G1
результат стягивания графа
• граф G1 - результат стягивания графа G.

№ 7
Орграф G
рефлексивность, транзитивность, симметричность
представляет отношение, обладающее свойствами
• рефлексивности, транзитивности, симметричности.

№ 8
Орграф G
отношение строгого порядка
представляет бинарное отношение, являющееся отношением
• строгого порядка.

№ 9
Транзитивное замыкание графа G

представлено на рисунке
Транзитивное замыкание графа
• б

№ 10
Сколько пар элементов содержит бинарное отношение, заданное графом G?
бинарное отношение
• 5

Тема: Представление графов в ЭВМ

№ 1
Матрица смежности произвольного неорграфа есть
• квадратная симметричная матрица, элементы главной диагонали которой равны нулю.

№ 2
Матрица A(n× n) (n - количество вершин графа), элементы которой определяются следующим образом
матрица смежности
называется:
• матрицей смежности.

№ 3
Дана матрица смежности
A=0110
1100
0111
1110
Граф, по которому построена матрица смежности является
• орграфом.

№ 4
Дана матрица смежности неорграфа G
матрица смежности неорграфа
Сколько вершин и сколько ребер в графе G?
• 4; 4

№ 5
Дана матрица инцидентности орграфа G
матрица инцидентности орграфа
Чему равны полустепени захода и исхода вершины x3?
• 2; 2

№ 6
Матрица инцидентности неорграфа G(X,V), |X|= 7, |V|= 4 есть
• матрица В(7x4).

№ 7
Дан неорграф G

Выберите его матрицу инцидентности:

№ 8
Дан неорграф G(X,V), |X|= 3, |V|= 5. Чему равна размерность одного из массивов, составляющих список ребер графа?
• 10

№ 9
Выберите структуру смежности, соответствующую графу

• x1 : x2;
x2 : x3, x1;
x3 : x2;
x4 :

№ 10
Матрица B(nxm)(n - количество вершин графа, m- количество ребер графа), элементы которой определяются следующим образом
bij={1, если вершина i инцидентна ребру j;
0, в противном случае
называется:
• матрицей инцидентности неорграфа.

Тема: Изоморфизм и планарность

№ 1
Графы, изоморфные графу G


№ 2
Плоские графы

№ 3
Планарные графы


№ 4
Сколько подграфов нужно построить, чтобы проверить, планарен ли граф с n вершинами (по критерию Понтрягина-Куратовского)?
• Cn5.

№ 5
Сколько подграфов нужно построить, чтобы проверить, планарен ли граф с числом вершин, равным 7?
• 21

№ 6
Сколько подграфов нужно построить, чтобы проверить, планарен ли граф с числом вершин, равным 8?
• 56

№ 7
Выберите все графы, изоморфные графу G


№ 8
Плоские графы

№ 9
Планарные графы



Тема: Маршруты на графах. Основные понятия и определения. Эйлеровы цепи и циклы

№ 1
Маршрут в орграфе, конечная и начальная вершина которого совпадают, называется
• контуром.

№ 2
Является ли путь M1=x1x2x3x1x4 простым путем?
• Нет.

№ 3
Дан неорграф G

Укажите простой путь и простой цикл, построенный на графе G.
• M2=x1x2x3x1;
• M3=x1x3x4x2.

№ 4
Маршрут в неорграфе, конечная и начальная вершина которого совпадают, называется
• циклом.

№ 5
Маршрут в орграфе, конечная и начальная вершина которого не совпадают, называется
• путем.

№ 6
Маршрут в неорграфе, конечная и начальная вершина которого не совпадают, называется
• цепью.

№ 7
Дан неорграф G

Укажите путь и цикл, построенные на графе G и не являющиеся простыми.
• M1=x1x2x4x3x2x3;
• M3=x1x3x4x3x1.

№ 8
Эйлеровым циклом называется
• цикл, проходящий по всем ребрам графа ровно по одному разу.

№ 9
Для того, чтобы в графе существовала эйлерова цепь необходимо и достаточно, чтобы
• ровно две вершины имели нечетные степени.

№ 10
Выберите графы, которые можно изобразить, не отрывая руки от бумаги:


Тема: Связность графа

№ 1
Бинарное отношение, описываемое орграфом G, имеет следующие классы эквивалентности K2=K3=K4={2,3,4},K1={1}. Будет ли такой орграф сильносвязным?
• Нет.

№ 2
Чему равно число компонент связности графа G?

• 3

№ 3
Дан орграф G

Орграф G
• слабо связный.

№ 4
Сколько “сильных компонент” имеет граф G?

• 3

№ 5
Каркасом графа G

является граф, изображенный на рисунке

№ 6
Сколько “сильных компонент” имеет граф G?

• 1

№ 7
Дан орграф G

Орграф G
• сильно связный.

№ 8
Дан орграф G

Орграф G
• не связный.

№ 9
Чему равно число компонент связности графа G?

• 2

№ 10
Чему равно число компонент связности графа G?

• 4

Тема: Понятие достижимости и взаимодостижимости

№ 1
Дан неорграф G

Чему равно множество достижимости вершины x1?
• Rx1={x1,x4,x2,x3}.

№ 2
Найдите множество контрдостижимости вершины x3 графа G:

• Rx3-1={x1,x2x3,x4}.

№ 3
Отношение взаимодостижимости на графе есть
• отношение эквивалентности.

№ 4
Матрица достижимости связного неорграфа есть
• матрица, все элементы которой - единичные.

№ 5
Элементы матрицы взаимодостижимости sij орграфа могут быть получены следующим образом: (aij - элементы матрицы смежности, rij - элементы матрицы достижимости, qij - элементы матрицы контрдостижимости)
• sij=rij,qij.

№ 6
Дан орграф G

Матрица достижимости орграфа G может быть вычислена по формуле:
• R=E+A+A²+A³.

№ 7
Сколько компонент связности имеет неорграф, заданный своей матрицей достижимости
R=10110
01001
10100
10011
01011
• 2

№ 8
Найдите множество достижимости вершины x3 графа G:

• Rx3={x2,x3}.

№ 9
Найдите множество контрдостижимости вершины x2 графа G:

• Rx2-1={x1,x2x3,x4}.

№ 10
Найдите множество достижимости вершины x4 графа G:

• Rx4={x2x3,x4}.

Тема: Метрики связного неорграфа

№ 1
Дан неорграф G

Диаметр графа G равен:
• 2

№ 2
Дан неорграф G

Радиус графа G равен:
• 1

№ 3
Неорграф G задан матрицей минимальных расстояний

Центрами графа G являются вершины:
• x1x3.

№ 4
Дан неорграф G

Диаметр графа G равен:
• 2

№ 5
Неорграф G задан матрицей минимальных расстояний

Чему равен диаметр графа G?
• 2

№ 6
Неорграф G задан матрицей минимальных расстояний

Чему равен радиус графа G?
• 1

№ 7
Дан неорграф G

Чему равен диаметр графа?
• 3

№ 8
Дан неорграф G

Чему равен радиус графа?
• 2

№ 9
Дан неорграф G

Чему равен диаметр графа?
• 3

№ 10
Дан неорграф G

Чему равен радиус графа?
• 1

Тема: Алгоритмы на графах

№ 1
Для выделения компонент связности можно использовать
• алгоритм обхода графа “в глубину”.

№ 2
Минимальный путь в неорграфе между заданными вершинами x и y может быть найден с помощью
• волнового алгоритма.

№ 3
Дан неорграф G

Для отыскания минимального пути из вершины x1 в вершину x5 использовали волновой алгоритм. Во фронт волны какого уровня войдет вершина x5?
• 2

№ 4
Для поиска минимального пути в нагруженном орграфе между заданными вершинами x и y используется
• алгоритм Форда.

№ 5
Алгоритм Дейкстры ищет минимальный путь между заданными вершинами x и y
• и в нагруженном орграфе и в нагруженном неорграфе.

№ 6
Вершины дерева G

размечены с помощью алгоритма:
• обхода дерева “в глубину”.

№ 7
Дан граф G

и его остовное дерево Т

Остовное дерево Т построено при помощи
• обхода дерева “в ширину”.

№ 8
Вершины дерева G

размечены с помощью алгоритма:
• обхода дерева “в ширину”.

№ 9
Дан граф G

и его остовное дерево Т

Остовное дерево Т построено при помощи
• обхода дерева “в глубину”.

№ 10
Дан неорграф G

Для отыскания минимального пути из вершины x1 в вершину x5 использовали волновой алгоритм. Во фронт волны какого уровня войдет вершина x5?
• 3

Тема: Деревья

№ 1
Сколько можно построить различных деревьев на пяти вершинах?
• 125

№ 2
Сколько ребер в дереве с пятью вершинами?
• 4

№ 3
В произвольном дереве можно выделить
• только простую цепь.

№ 4
Дано дерево G

Правильные высказывания:
• x8,x9,x7 - листы дерева;
• x2 - корень дерева;
• x2,x4,x5 - ствол дерева.

№ 5
Между выбранными двумя вершинами x и у произвольного дерева можно построить:
• единственную простую цепь.

№ 6
В любом дереве
• хотя бы две висячие вершины.

№ 7
Число различных деревьев, построенных на n вершинах равно
• nn-2.

№ 8
Дан код дерева G К=(1,1,2,3). Сколько вершин в дереве G?
• 6

№ 9
Дано дерево G

Запишите код дерева (через запятую).
• 4,4,6,7,7

№ 10
Дан код дерева К=(2,2,3,3,7,7). Данному коду соответствует дерево

Тема: Остовные деревья. Цикломатика графа

№ 1
Цикломатическое число графа G

равно
• 2

№ 2
Связность графа не меняется при удалении
• циклового ребра.

№ 3
Выберите графы, являющиеся остовными деревьями графа G


№ 4
Сколько ребер необходимо удалить из графа G

для получения остовного дерева?
• 4

№ 5
Нагруженный граф задан матрицей весов

Минимальный остов графа содержит ребра:
• (x5,x3)(x5,x1)(x1,x2)(x5,x4).

№ 6
Цикломатическое число графа не меняется при удалении
• перешейка.

№ 7
Дан неорграф G

Каково количество циклов, входящих в независимый базис?
• 3

№ 8
Дан неорграф G

Каково количество циклов, входящих в независимый базис?
• 4

№ 9
Сколько ребер необходимо удалить из графа G

для получения остовного дерева?
• 5

№ 10
Неорграф задан матрицей смежности

Сколько ребер в остовном дереве графа?
• 4


на главную база по специальностям база по дисциплинам статьи