Аноним

Дерево: различия между версиями

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
Строка 4: Строка 4:
<math>T_{1}, \, T_{2}, \ldots, \, T_{d}</math> каждое из которых само является
<math>T_{1}, \, T_{2}, \ldots, \, T_{d}</math> каждое из которых само является
деревом. Множества
деревом. Множества
<math>T_{1}, \, T_{2}, \ldots, \, T_{d}</math>называются [[поддерево|''поддеревьями'']] [[корень|корня]]. Если порядок в этих деревьях существен, дерево называется [[упорядоченным деревом|упорядоченным деревом]], в противном случае оно иногда называется неупорядоченным деревом. Дерево может быть представлено как [[граф|граф]], в котором корневая вершина представлена вершиной, соединенной [[дуга|дугами]] с вершинами, представляющими корни каждого из ее поддеревьев. Таким
<math>T_{1}, \, T_{2}, \ldots, \, T_{d}</math>называются [[поддерево|''поддеревьями'']] [[корень|корня]]. Если порядок в этих деревьях существен, дерево называется [[упорядоченное дерево|упорядоченным деревом]], в противном случае оно иногда называется неупорядоченным деревом. Дерево может быть представлено как [[граф|граф]], в котором корневая вершина представлена вершиной, соединенной [[дуга|дугами]] с вершинами, представляющими корни каждого из ее поддеревьев. Таким
образом, в терминах теории графов можно дать другое определение ([[ориентированное дерево|ориентированного]]) дерева: дерево --- это [[бесконтурный орграф|ориентированный бесконтурный
образом, в терминах теории графов можно дать другое определение ([[ориентированное дерево|ориентированного]]) дерева: дерево --- это [[бесконтурный орграф|ориентированный бесконтурный
граф]] такой, что, во-первых, существует единственная вершина, в которую не входит ни одна дуга (эта вершина называется корнем), во-вторых, в каждую из оставшихся вершин входит ровно одна дуга, и, в-третьих, существует единственный путь из корня в любую другую вершину.
граф]] такой, что, во-первых, существует единственная вершина, в которую не входит ни одна дуга (эта вершина называется корнем), во-вторых, в каждую из оставшихся вершин входит ровно одна дуга, и, в-третьих, существует единственный путь из корня в любую другую вершину.