Какой граф называется деревом? Что такое дерево в информатике?

Граф-дерево является очень распространенным видом графов в информатике. Они нужны для хранения какой-либо информации в нелинейной структуре в иерархическом порядке.

Граф — это структура, состоящая из множества вершин, соединенных ребрами. Все в своей жизни видели транспортные схемы (передвижение автобусов или метро). Если эти схемы смоделировать в компьютере, то остановки и станции — это будут вершины графа, а маршрут транспорта между остановками/станциями — ребра графа.

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

Граф-дерево

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

• в самом низу вы писали свое имя и имена ваших братьев и сестер;


• чуть выше вы записывали имена ваших родителей и соединяли ваши имена с их именами линиями;


• еще выше вы писали имена ваших дедушек и бабушек, которые являются родителями ваших родителей;


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

Самое главное, все имена вы соединяли линиями зависимости между собой. Например, свое имя соединили с именами братьев и сестер и с именами своих родителей. Имена ваших родителей вы соединили с именами их братьев и сестер и с их родителями и т. д. 

В информатике, граф-дерево выглядит точно так же, как и ваше генеалогическое дерево, только вместо имен — вершины, а вместо линий, связывающих имена — ребра.

Охарактеризовать граф-дерево в информатике можно так — это связный граф, где между двумя вершинам есть единственный связный путь. Вернемся к нашему дереву. Ваше имя будет связано линиями только с вашими родителями и вашими братьями/сестрами, с другими именами дерева у вас нет прямой связи. Например, с вашими дядями, тетями, бабушками и дедушками вы будете связаны только через ваших родителей, а не напрямую. А с вашей прабабушкой или вашим прадедушкой вы будете связаны только через родителей и бабушек с дедушками.  

То есть граф-дерево в информатике следует строгой иерархии — одни элементы находятся «наверху» графа и будут называться «корнем дерева», другие элементы будут чуть ниже и будут называться «потомками», от «потомков» будут исходить «листья» — это те вершины, которые не имеют «потомков». Любой элемент верхнего уровня по отношению к нижнему уровню будет называться «предком».

Вернемся к нашему генеалогическому дереву. Бабушка с дедушкой (или прабабушка с прадедушкой, то есть в зависимости до какой глубины своих предков вы дойдете) будут корнем вашего граф-дерева (либо подкорнем, если у вас в корне будут прабабушка с прадедушкой). Ваши родители — это «потомки» вашего граф-дерева и бабушка с дедушкой для них будут «предками» вашего дерева. Вы будете «листьями» граф-дерева, потому что у вас пока нет своего потомства, как только у вас появятся дети, то вы станете «потомками» графа, а ваши дети «листьями». Ваши родители для вас будут «предками» графа.

Граф-дерево в информатике: термины

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

• корень — это самая «верхняя» вершина графа, с которой начинается сам граф, допустим ваши дедушка и бабушка, если вы начали вести генеалогическое дерево с них;


• ребро — это путь или линия связи между двумя графами, то есть это линия связи между именами в вашем дереве;


• потомок — это вершина графа, у которой есть родительская вершина, то есть это вы по отношению к своим родителям или ваши родители по отношению к вашим бабушке с дедушкой;


• родитель — это вершина графа, у которой есть потомственная или дочерняя вершина, то есть это ваши родители по отношению к вам или бабушка с дедушкой по отношению к вашим родителям;


• лист — это вершина, у которой нет потомственных вершин, а только родительские, то есть это вы, пока у вас нет своих детей;


• высота графа — это длина  к самому дальнему листу графа, допустим в вашем дереве есть ваш дядя или тетя, тогда путь от них и до вас это будет высотой графа;


• глубина графа — это длина до корня, то есть это будет путь от дяди с тетей к корню вашего дерева (бабушка с дедушкой или прабабушка с прадедушкой);


• поиск в глубину — это стратегия обхода вершин графа, целью которой является дойти максимально «глубоко» в граф-дерево, то есть если вы возьметесь исследовать ваше генеалогическое древо и попытаетесь найти информацию о родителях ваших прадедушек и прабабушек, а может и дальше;


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

Заключение

Граф-дерево встречается не только в информатике. Его очень часто используют и в жизни. Взгляните на иерархию в школе: во главе стоит директор, у него есть несколько заместителей, ниже заместителей находятся учителя и «листьями» графа будут ученики. И если эту зависимость попытаться нарисовать, то у вас получится граф-дерево. Во многих организациях и даже государствах система управления строится именно по таким графам.