Задание графа

Граф может задаваться в виде рисунка, аналитически, в виде матрицы. Выше приводилось задание графа в виде рисунка. Анали­тическое задание состоит в задании элементов множества вершин Е={е₁, е₂,... е_n} и множества ребер U = {u₁, u₂,... u_m}.

Для выполнения различного рода формальных преобразований над графами удобно использовать их матричные задания. Матрица А размерностью n ´ n называется матрицей смежности графа G(E, U), если ее элементы образованы по правилу: элемент матрицы а_ij= m, если вершины е_i и е_j соединены m ребрами, и а_ij=0, если эти вершины не связаны ребрами. Матрица смежности имеет число строк и столбцов, равное количеству вершин графа.

Матрица А размерностью n ´ m называется матрицей инцидент­ности графа G(E, U), если ее элементы образованы по правилу: элемент матрицы b_ij=1, если вершина е_i инцидентна ребру u_j и b_ij=0 в про­тивном случае. Так как каждое ребро инцидентно двум вершинам, то в каждой строке этой матрицы ровно два ненулевых элемента.

1. Дерево - это связный граф без циклов.

2. Дерево - это связный граф, в котором при N вершинах всегда ровно N-1 ребро.

3. Дерево - это граф, между любыми двумя вершинами которого существует ровно один путь.

Аналогичным образом определяется и ориентированное дерево - как орграф, в котором между любыми двумя вершинами существует не более одного пути.

Корневое дерево - это ориентированное дерево, в котором можно выделить вершины трех видов: корень, листья (другое их название: терминальные вершины) и остальные вершины (нетерминальные); причем должны выполняться два обязательных условия:

1.из листьев не выходит ни одна дуга; из других вершин может выходить сколько угодно дуг;

2.в корень не заходит ни одна дуга; во все остальные вершины заходит ровно по одной дуге.

Традиционно в математике и в родственных ей науках (в том числе и в теоретическом программировании) деревья «растут» вниз головой: это делается просто для удобства наращивания листьев в случае необходимости. Таким образом, на рисунках корень дерева оказывается самой верхней вершиной, а листья - самыми нижними.

Предок вершины v - это вершина, из которой исходит дуга, заходящая в вершину v. Потомок вершины v - это вершина, в которую заходит дуга, исходящая из вершины v. В этих терминах можно дать другие определения понятиям корень и лист: у корня нет предков, у листа нет потомков.

Бинарное дерево - это корневое дерево, каждая вершина которого имеет не более двух потомков. В таком случае иногда говорят о левом потомке и правом потомке для текущей вершины.

Высота корневого дерева - это максимальное количество дуг, отделяющих листья от корня. Если дерево не взвешенное, то его высота - это просто расстояние от корня до самого удаленного листа.

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