Бинарные деревья
Самым наглядным способом представления информации является ее представление рисунками или графиками. Поэтому при решении многих математических задач используются специальные рисунки (схемы), называемые графами.
Граф представляет собой множество точек – вершин графа, соединенных между собой отрезками – ребрами графа.
Термин граф впервые появился в работах венгерского математика Д.Кенига в 1936 году, хотя ряд задач по теории графов был решен еще Л.Эйлер в XVIII веке.
Примером графа может служить схема линии метрополитена, карта автомобильных или железных дорог. Эти дороги можно рассматривать как ребра, соединяющие города или станции – вершины такого графа.
Вершины графа обычно нумеруются или обозначаются прописными латинскими буквами: A. B, C, … Любой граф можно описать или задать перечислением вершин и ребер. Наиболее удобный способ такого задания – с помощью матрицы смежности, в которой строки и столбцы соответствуют вершинам графа, а значения элементов – длине ребер, соединяющих эти вершины. Если длина ребер не задается, то наличие ребра обозначается единицей, а его отсутствие – нулем.
Например, граф:
задается матрицей смежности:
A B C D
A
B
C
D
Как видно, это симметричная матрица.
Граф называется ориентированным (орграф), если на каждом его ребре указано направление, то есть о каждой его вершине можно сказать, какие ребра из нее выходят, а какие входят:
Для этого ориентированного графа матрица смежности имеет вид:
Дата добавления: 2015-08-08; просмотров: 692;