Генеалогическое дерево

На рисунке 2.17 показано библейское генеалогическое дерево.

Граф без цикла называется лесом. Вершины степени 1 в дереве называются листьями.

Деревья - очень удобный инструмент представления информации самого разного вида.

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

Очевидно, что графический способ представления графов непригоден для ПК. Поэтому существуют другие способы представления графов.

В теории графов применяются

1. Матрица инцинденций. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующнго рёбрам. Для ориентированного графа столбец, соответствующий дуге (х, y) содержит - 1 в строке, соответствующей вершине х и 1, в строке, соответствующей вершине у. Во всех остальных 0. Петлю, т.е. дугу (х, х) можно представлять иным значением в строке х, например, 2. Если граф неориентированный, то столбец, соответствуюший ребру (х, у) содержит 1, соответствующие х и у и нули во всех остальных строках.

2. Матрица смежности. Это матрица n× n где n - число вершин, где bij = 1, если существует ребро, идещее из вершины х в вершину у и bij = 0 в противном случае.

Составим матрицы инциндентности и смежности для следующего непрерывного графа (рис. 2.18)

Матрица инцидентности

Матрица смежности