Question

1. Чем ориентированный граф отличается от неориентированного? 2. Чем отличается путь от маршрута? 3. Чем отличается контур от цикла? 4. Как задается матрица смежности? 5. Как реализуется операция удаления вершины в графе? 6. Что такое нагруженный граф? 7. Что такое кратчайший путь в ориентированном графе? 8. Что такое дерево? 9. Что такое бинарное дерево? 10. Что такое рекурсивная функция?

Answer 1

1. Чем ориентированный граф отличается от неориентированного?

В ориентированном рёбрам присвоено направление.

2. Чем отличается путь от маршрута?

Путь - это маршрут, в котором все рёбра различны.

3. Чем отличается контур от цикла?

Контур - цикл в ориентированном графе.

4. Как задается матрица смежности?

Это матрица размера $n\times n$, где $n$ - число вершин, в которой на $ij$-месте стоит число рёбер из вершины $i$ в вершину $j$.

5. Как реализуется операция удаления вершины в графе?

Удаляется вершина и все рёбра, соединяющие удаляемую вершину с другими вершинами.

6. Что такое нагруженный граф?

Граф, в котором каждому ребру назначен вес - какое-то число.

7. Что такое кратчайший путь в ориентированном графе?

Путь из начальной вершины в конечную, длина которого минимальна.

8. Что такое дерево?

Связный граф без циклов.

9. Что такое бинарное дерево?

Дерево, в котором каждый родитель имеет не более двух потомков.

10. Что такое рекурсивная функция?

Функция, значения которой зависят от других значений этой же функции.

Answer 2

1. Ориентированный граф отличается от неориентированного тем, что в ориентированном графе рёбра имеют направление, т.е., они указывают от одной вершины к другой. В неориентированном графе рёбра не имеют направления и связывают вершины взаимно, что означает, что связь между вершинами двунаправленна.

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

3. Контур - это замкнутый путь в графе, который начинается и заканчивается в одной и той же вершине, и он не проходит по одному и тому же ребру более одного раза. Цикл - это контур, который также не проходит по одному и тому же ребру более одного раза, но может содержать несколько вершин.

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

5. Операция удаления вершины из графа включает в себя удаление вершины и всех рёбер, связанных с этой вершиной. Если это приводит к разрыву графа, то также могут удаляться и некоторые другие вершины или рёбра для поддержания связности.

6. Нагруженный граф - это граф, в котором каждому ребру приписан числовой вес или стоимость. Эти веса могут представлять различные характеристики, такие как расстояние, стоимость перехода, пропускная способность и так далее.

7. Кратчайший путь в ориентированном графе - это путь между двумя вершинами, который имеет наименьшую суммарную стоимость (сумму весов рёбер) среди всех возможных путей между этими вершинами.

8. Дерево - это связный ациклический граф, который состоит из вершин и рёбер, соединяющих эти вершины. Деревья используются в различных областях, таких как информатика, биология, иерархическая структура данных и другие.

9. Бинарное дерево - это дерево, в котором каждая вершина имеет не более двух потомков. У каждой вершины может быть левый и правый потомок, и эти потомки могут быть пустыми (null) или содержать данные.

10. Рекурсивная функция - это функция, которая вызывает саму себя внутри своего определения. Рекурсия часто используется в программировании для решения задач, которые могут быть разбиты на более мелкие подзадачи. Рекурсивная функция должна иметь условие завершения, чтобы избежать бесконечного вызова.