Графы и их применение

Упражнение 1:

Номер 1

Какие деревья называются изоморфными?

Ответ:

(1) два плоских дерева называются изоморфными, если существует гомеоморфное отображение плоскости на себя, сохраняющее ориентацию, и такое, что оно отображает одно из этих деревьев в другое

(2) два плоских дерева называются изоморфными, если не существует гомеоморфное отображение плоскости на себя, сохраняющее ориентацию, и такое, что оно отображает одно из этих деревьев в другое

(3) два плоских дерева называются изоморфными, если существует гомеоморфное отображение плоскости на себя, сохраняющее ориентацию, и такое, что оно не отображает одно из этих деревьев в другое

(4) два плоских дерева называются изоморфными, если существует взаимно однозначное отображение плоскости на себя, сохраняющее ориентацию, и такое, что оно отображает одно из этих деревьев в другое

Номер 2

Какие помеченные деревья называются изоморфными?

Ответ:

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

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

(3) если существует разомкнутая цепь, проходящая через все вершины графов степени единица, то такие графы называются изоморфными

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

Номер 3

Чему равна сумма чисел, стоящих в любом из столбцов матрицы инциденций?

Ответ:

(1) сумма чисел в каждом столбце матрицы инциденций равна степени вершины, которую он характеризует

(2) сумма чисел в каждом столбце матрицы инциденций равна рангу матрицы

(3) сумма чисел в каждом столбце матрицы инциденций равна числу петель в графе

(4) сумма чисел в каждом столбце матрицы инциденций равна числу компонент графа

Упражнение 2:

Номер 1

Чему равна сумма чисел, стоящих в любой из строк матрицы инциденций  графа G?

Ответ:

(1) сумма чисел в каждой строке матрицы инциденций равна степени вершины, которую она характеризует

(2) сумма чисел в каждой строке матрицы инциденций равна рангу матрицы

(3) сумма чисел в каждой строке матрицы инциденций равна числу петель в графе

(4) сумма чисел в каждой строке матрицы инциденций равна числу компонент графа

Номер 2

Из какого графа нельзя выделить дерево, содержащее все вершины графа?

Ответ:

(1) из любого несвязного графа

(2) из графа, состоящего из четного числа компонент

(3) из пустого графа

Номер 3

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

Ответ:

(1) 146

(2) 145

(3) 100

(4) 172

Упражнение 3:

Номер 1

Граф, который может быть изображен проволочной моделью куба, =

Ответ:

(1) плоский

(2) эйлеров

(3) не плоский

Номер 2

Сколько получится кусков бумаги, если первоначально имелось m  кусков, некоторые из кусков разрезали на  n  частей, а всего было разрезано  k  кусков?

Ответ:

(1) m+(n-1)k

(2) m+(n+1)k

(3) m-(n-1)k

(4) m+(n-1)/k

Номер 3

Существует ли граф с шестью вершинами, степени которых 2, 3, 3, 4, 4, 4?

Ответ:

(1) существует

(2) не существует

(3) в графе должно быть минимум четыре вершины

(4) в графе должно быть минимум две вершины

Графы и их применение - тест 12