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

Видеоурок 1: Теория графов: Алгоритм Дейкстры

Лекция: Цепочки (конечные последовательности), деревья, списки, графы, матрицы (массивы), псевдослучайные последовательности

Графы, их виды

Если несколько графов соединить вместе, то можно получить дерево. Важно, чтобы соединения графов не зацикливали операции.

Графы могут быть разных видов:

• Если граф имеет направленность, то его называют ориентированным. То есть важен порядок. Например, сначала необходимо вымыть руки и только потом кушать, а не наоборот, то есть важен порядок действий.

• Если ребра графа различные по важности, то такой граф называют взвешенным. Например, при составлении алгоритмов некоторые линии могут быть короче, а другие длиннее. Причем возле каждой стоит цифра. Например, вы хотите купить компьютер, если вы пойдете в магазин возле дома, то заплатите 100 тысяч рублей, если же в центре города, то 150 тысяч рублей. Если бы данный алгоритм был написан с помощью взвешенного графа, то веточка, ведущая к покупке компьютера возле дома, была бы короче.

• Если граф объединяет несколько перечисленных видов графа, то его можно назвать полным.

• Псевдограф – граф, в котором имеются не прямые ребра.

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

• Если вершины последовательно соединяются ребрами, то их называют маршрутом. Маршрут должен иметь только одно направление.

• Если же в маршруте ребра не пересекаются, то его называют путем.

• Если путь замкнут, то он носит название цикла.

• Если при отсутствии некоторого ребра граф делиться на несколько компонент, то это ребро называется мостом.

• Если вершина имеет только одно ребро, то она называется висячей.

• Если некоторый путь проходит каждую вершину, причем единожды, то его называют гамильтоновым путем.

• Если маршрут проходит по всем ребрам единожды, то его называют эйлеровым маршрутом.

• Ели в некоторой задаче имеется последовательность, состоящая из случайных чисел, но при этом её можно вычислить с помощью логических рассуждений или формул, то такая последовательность называется псевдослучайной. Примером псевдослучайной последовательности может случить уравнение движения.