You get a bonus - 1 coin for daily activity. Now you have 1 coin

Tree (graph theory)

Lecture



A tree is a connected acyclic graph. [1] Connectivity means the presence of paths between any pair of vertices, acyclicity — the absence of cycles, and the fact that there is only one path between pairs of vertices.

A forest is an ordered set of ordered trees.

Oriented (directed) tree is an acyclic digraph (a directed graph that does not contain cycles), in which only one vertex has zero degree of entry (no arcs lead to it), and all other vertices have degree of entry 1 (they lead along exactly one arc ). A node with a zero degree of entry is called the root of a tree, and peaks with a zero degree of outcome (from which no arc comes) are called terminal vertices or leaves . [2]

The root tree is a tree in which one vertex is selected (the root of the tree). Formally, the root tree is defined as a finite set Tree (graph theory) one or more nodes with the following properties:

  1. there is one root of a tree Tree (graph theory)
  2. the remaining nodes (with the exception of the root) are distributed among Tree (graph theory) disjoint sets Tree (graph theory) , and each of the sets is a root tree; trees Tree (graph theory) are called subtrees of this root Tree (graph theory)

Related definitions

  • The node degree is the number of outgoing arcs (or, otherwise, the number of node subtrees).
  • A leaf node ( leaf , terminal vertex ) is a node with degree 1 (that is, a node into which only one edge leads; in the case of an oriented tree, a node into which only one arc leads and not a single arc goes).
  • The branch node is a non-leaf node.
  • Node level - path length from root to node. You can define recursively:
  1. tree root level Tree (graph theory) equals 0;
  2. the level of any other node is one greater than the root level of the nearest subtree of the tree Tree (graph theory) containing this node.
  • A tree with a marked top is called a root tree .
    • Tree (graph theory) tier wood Tree (graph theory) - many tree nodes, at the level Tree (graph theory) from the root of the tree.
    • partial order on vertices: Tree (graph theory) if vertices Tree (graph theory) and Tree (graph theory) different and top Tree (graph theory) lies on the (unique!) elementary chain connecting the root to the vertex Tree (graph theory) .
    • root subtree with root Tree (graph theory) - subgraph Tree (graph theory) .
    • In a context where a tree is supposed to have a root, a tree without a selected root is called free .
  • A spanning tree (s) is a subgraph of a given graph containing all its vertices and is a tree. The edges of the graph, not included in the core, are called chords of the graph with respect to the core.
  • An irreducible tree is a tree in which there are no vertices of degree 2.
  • A forest is a set (usually ordered) that does not contain a single non-intersecting tree or contains several non-intersecting trees.

Binary tree

Tree (graph theory)

A simple binary tree of size 9 and height 3, with a root of value 2. This tree is not balanced and not sorted.

The term binary tree (it is also a binary tree ) has several meanings:

  • A non-oriented tree in which the degrees of the vertices do not exceed 3.
  • An oriented tree in which the outgoing degrees of the vertices (the number of outgoing edges) do not exceed 2.
  • Abstract data structure used in programming. Data structures such as a binary search tree, binary heap, red-ebony, AVL-tree, Fibonacci heap, etc. are based on a binary tree.

N-ary trees

N-ary trees are defined by analogy with a binary tree. For them, there are also oriented and non-oriented cases, as well as corresponding abstract data structures.

  • An N-ary tree (non-oriented) is a tree (normal, non-oriented) in which the degrees of the vertices do not exceed N + 1.
  • An N-ary tree (oriented) is an oriented tree in which the outgoing degrees of the vertices (the number of outgoing edges) do not exceed N.

Properties [edit]

  • The tree has no multiple edges and loops.
  • Any tree with Tree (graph theory) vertices contains Tree (graph theory) edge. Moreover, a finite connected graph is a tree if and only if Tree (graph theory) where Tree (graph theory) - the number of vertices Tree (graph theory) - the number of edges of the graph.
  • A graph is a tree if and only if any two different vertices of it can be connected by a single simple chain.
  • Any tree is uniquely determined by the distances (the length of the smallest chain) between its terminal (degree 1) vertices.
  • Any tree is a bichromatic graph. Any tree whose vertex set is at most countable is a planar graph.
  • For any three vertices of the tree, the paths between the pairs of these vertices have exactly one common vertex.

Tree Counting

Main article: Cayley's theorem on the number of trees

  • The number of different trees that can be built on Tree (graph theory) numbered vertices equal to Tree (graph theory) ( Cayley's theorem [3] ).
  • Generating function

Tree (graph theory)

for the number Tree (graph theory) nonisomorphic rooted trees with Tree (graph theory) vertices satisfies the functional equation

Tree (graph theory) .

  • Generating function

Tree (graph theory)

for the number Tree (graph theory) non-isomorphic trees with Tree (graph theory) vertices can be represented using the enumeration series for root trees:

Tree (graph theory)

  • With Tree (graph theory) the following asymptotics is true

Tree (graph theory)

Where Tree (graph theory) and Tree (graph theory) certain constants Tree (graph theory) , Tree (graph theory) .

Tree coding

The tree can be encoded with sets of zeros and ones. Consider, for example, laying wood on a plane. Starting from any vertex, we move along the edges of the tree, turning at each vertex to the nearest edge to the right and turning back at the terminal vertices of the tree. Passing along some edge, we write Tree (graph theory) when moving along the edge for the first time and Tree (graph theory) when moving along the edge a second time (in the opposite direction). If a Tree (graph theory) - the number of edges of the tree, then through Tree (graph theory) steps we will return to the original vertex, passing along each edge twice. The resulting sequence from Tree (graph theory) and Tree (graph theory) (tree code) length Tree (graph theory) allows you to uniquely recover not only the tree itself Tree (graph theory) but its laying on the plane. Arbitrary tree correspond to several such codes. In particular, the following rough estimate for the number of trees with Tree (graph theory) tops:

Tree (graph theory)

created: 2015-01-06
updated: 2021-11-27
132955



Rating 8 of 10. count vote: 3
Are you satisfied?:


avatar
21.3.2020 21:24

Такая кодировка мне понятна, доступна. Учусь кодить. Пишу html графы деревьев.

avatar
21.3.2020 21:42

что значит html графы ?

avatar
22.3.2020 15:13

https://code.sololearn.com/WZTTXNB4wCy1/?ref=app

avatar
22.3.2020 15:15

Наверное, правильнее сказать не графы, а схемы деревьев.

avatar
22.3.2020 15:57

Да, существует большое количество библиотек для визуализации графов,
а вообще т.к понятие граф растяжимое в прямом смысле (один и тот же граф можно изобразить -
визуализировать бесконечным количесвтом образов),
существуют специальные теории и алгоритмы визуализации графов,
например можно прочитать тут
https://intellect.icu/sposoby-vizualizatsii-grafov-silovye-algoritmy-vizualizatsii-grafov-9034


еще есть даже Non-SQL для работы с графами в том числе с визуализацией
вот пример такой БД
http://console.neo4j.org/
https://neo4j.com/

Визуализация гибкого force-directed графа осуществляется с использованием метода численного интегрирования Верле библиотека JS https://github.com/d3/d3

библиотека https://www.graphviz.org/

и другие


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Discrete Math. Set theory. Graph theory. Combinatorics.

Terms: Discrete Math. Set theory. Graph theory. Combinatorics.