Графы. Условие Фано.

Question 1

Кодирование

Answer 1

Перевод информации из одного языка в другой (запись в другом алфавите/системе символов)

Question 2

Декодирование

Answer 2

Обратный переход из 1

Question 3

Кодирование равномерное

Answer 3

Длина кода всех символов равна

Question 4

Кодирование неравномерное

Answer 4

Длина кода всех символов может быть различной

Question 5

Условие Фано

Answer 5

Никакое кодовое слово не является началом другого, что обеспечивает однозначное декодирование сообщений с начала

Question 6

Префиксный код

Answer 6

Код, в котором работает условие Фано. Декодируется однозначно

Question 7

Обратное условие Фано

Answer 7

Никакое кодовое слово не является концом другого, что обеспечивает однозначное декодирование сообщений с конца

Question 8

Постфиксный код

Answer 8

Код, в котором работает обратное условие Фано. Декодируется однозначно и только с конца

Question 9

Теория графов*

Answer 9

Раздел дискретной информатики, изучающий свойства графов

Question 10

Граф

Answer 10

Геометрическая фигура, состоящая из точек (вершин) и линий, их соединяющих (ребер).

Question 11

Обозначения графа*

Answer 11

G - имя графа
v - кол-во вершин
e - кол-во ребер

Question 12

Кратные ребра

Answer 12

Ребра, соединяющие одну и ту же пару вершин

Question 13

Петля

Answer 13

Ребро с совпадающими концами

Question 14

Изолированная вершина

Answer 14

Вершина, не являющеяся концом ни одного ребра

Question 15

Висячая вершина

Answer 15

Вершина, из которой выходит одно ребро

Question 16

Обыкновенный граф

Answer 16

Граф без кратных ребер и петель

Question 17

Степень вершины

Answer 17

Кол-во ребер, для которых она считается концом (петли считают дважды)

Question 18

Смежные ребра

Answer 18

Ребра с общей вершиной

Question 19

Псевдограф

Answer 19

Граф с петлями

Question 20

Путь

Answer 20

Последовательность смежных ребер, обычно задается перечислением вершин, по которым он пролегает

Question 21

Длина пути

Answer 21

Кол-во ребер в пути

Question 22

Цель

Answer 22

Маршрут без повторяющихся ребер

Question 23

Простая цель

Answer 23

Цель без повторяющихся вершин

Question 24

Цикл

Answer 24

Путь, в котором первая и последняя вершина совпадают

Question 25

Простой путь

Answer 25

Путь без повторяющихся вершин

Question 26

Связный граф

Answer 26

Граф, в котором любые 2 вершины соединены путем

Question 27

Пустой граф

Answer 27

Граф, состоящий только из вершин

Question 28

Изоморфные графы

Answer 28

Графы с одинаковым кол-вом вершин

Question 29

Мультиграф

Answer 29

Граф, в котором вершины соединены ребрами, что ребер > 1 (кратные ребра без петель)

Question 30

Регулярный граф

Answer 30

Граф с равными степенями всех вершин

Question 31

Полный граф

Answer 31

Граф, в котором каждые 2 вершины соединены одним ребром

Question 32

Двудольный граф

Answer 32

Граф, в котором все его вершины можно разделить на 2 множества таким образом, что каждое ребро соединяет ребро из разных множеств

Question 33

Планарный граф

Answer 33

Граф с непересекающимися ребрами

Question 34

Цикл Эйлера

Answer 34

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

Question 35

Эйлеров граф

Answer 35

Граф, в котором можно пройти все вершины, соблюдая цикл Эйлера (четное число ребер)

Question 36

Гамильтонов цикл

Answer 36

Цикл, проходящий через все вершины по одному разу

Question 37

Гамильтонов граф

Answer 37

Граф с гамильтоновым циклом

Question 38

Взвешенный граф

Answer 38

Граф с присвоенным вершинам/ребрам обозначений

Question 39

Дерево

Answer 39

Связный граф без циклов (нельзя вернуться в исходную вершину)

Question 40

Контур

Answer 40

Замкнутый путь, не проходящий дважды через одно и ту же вершину