Misplaced Pages

#361638

44-673: This is a family tree of the main line of descent of Confucius ( Chinese : 孔子世家大宗 ). The title of Duke of Song and "Duke Who Continues and Honours the Yin " ( 殷紹嘉公 ) were bestowed upon Kong An ( 孔安 (東漢) by the Eastern Han dynasty because he was part of the Shang dynasty's legacy. This branch of the Confucius family is a separate branch from the line that held the title of Marquis of Fengsheng village and later Duke Yansheng. Along with

88-456: A tree-sequence , which has been described as the largest "human family tree". Tree (graph theory) In graph theory , a tree is an undirected graph in which any two vertices are connected by exactly one path , or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by at most one path, or equivalently an acyclic undirected graph, or equivalently

132-556: A disjoint union of trees. A directed tree, oriented tree, polytree , or singly connected network is a directed acyclic graph (DAG) whose underlying undirected graph is a tree. A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest. The various kinds of data structures referred to as trees in computer science have underlying graphs that are trees in graph theory, although such data structures are generally rooted trees. A rooted tree may be directed, called

176-408: A pedigree or ancestry chart . Family trees are often presented with the oldest generations at the top of the tree and the younger generations at the bottom. An ancestry chart, which is a tree showing the ancestors of an individual and not all members of a family, will more closely resemble a tree in shape, being wider at the top than at the bottom. In some ancestry charts, an individual appears on

220-480: A directed rooted forest, either making all its edges point away from the root in each rooted tree—in which case it is called a branching or out-forest—or making all its edges point towards the root in each rooted tree—in which case it is called an anti-branching or in-forest. The term tree was coined in 1857 by the British mathematician Arthur Cayley . A tree is an undirected graph G that satisfies any of

264-420: A directed rooted tree, either making all its edges point away from the root—in which case it is called an arborescence or out-tree —or making all its edges point towards the root—in which case it is called an anti-arborescence or in-tree. A rooted tree itself has been defined by some authors as a directed graph. A rooted forest is a disjoint union of rooted trees. A rooted forest may be directed, called

308-417: A leaf from that vertex. The height of the tree is the height of the root. The depth of a vertex is the length of the path to its root ( root path ). The depth of a tree is the maximum depth of any vertex. Depth is commonly needed in the manipulation of the various self-balancing trees, AVL trees in particular. The root has depth zero, leaves have height zero, and a tree with only a single vertex (hence both

352-471: A parent must be born before their child, an individual cannot be their own ancestor, and thus there are no loops. In this regard, ancestry forms a directed acyclic graph . Nevertheless, graphs depicting matrilineal descent (mother-daughter relationships) and patrilineal descent (father-son relationships) do form trees. Assuming no common ancestor, an ancestry chart is a perfect binary tree , as each person has exactly one mother and one father; these thus have

396-419: A parent of v . A descendant of a vertex v is any vertex that is either a child of v or is (recursively) a descendant of a child of v . A sibling to a vertex v is any other vertex on the tree that shares a parent with v . A leaf is a vertex with no children. An internal vertex is a vertex that is not a leaf. The height of a vertex in a rooted tree is the length of the longest downward path to

440-454: A regular structure. A Descendant chart, on the other hand, does not, in general, have a regular structure, as a person can have any number of children or none at all. Family trees have been used to document family histories across time and cultures throughout the world. In Africa, the ruling dynasty of Ethiopia claimed descent from King Solomon via the Queen of Sheba . Through this claim,

484-439: A root and leaf) has depth and height zero. Conventionally, an empty tree (a tree with no vertices, if such are allowed) has depth and height −1. A k -ary tree (for nonnegative integers k ) is a rooted tree in which each vertex has at most k children. 2-ary trees are often called binary trees , while 3-ary trees are sometimes called ternary trees . An ordered tree (alternatively, plane tree or positional tree )

SECTION 10

#1732773117362

528-420: A root, a tree without any designated root is called a free tree . A labeled tree is a tree in which each vertex is given a unique label. The vertices of a labeled tree on n vertices (for nonnegative integers n ) are typically given the labels 1, 2, …, n . A recursive tree is a labeled rooted tree where the vertex labels respect the tree order (i.e., if u < v for two vertices u and v , then

572-451: Is a harder problem. No closed formula for the number t ( n ) of trees with n vertices up to graph isomorphism is known. The first few values of t ( n ) are Otter (1948) proved the asymptotic estimate with C ≈ 0.534949606... and α ≈ 2.95576528565... (sequence A051491 in the OEIS ). Here, the ~ symbol means that This is a consequence of his asymptotic estimate for

616-434: Is a rooted tree in which an ordering is specified for the children of each vertex. This is called a "plane tree" because an ordering of the children is equivalent to an embedding of the tree in the plane, with the root at the top and the children of each vertex lower than that vertex. Given an embedding of a rooted tree in the plane, if one fixes a direction of children, say left to right, then an embedding gives an ordering of

660-451: Is a tree in which there is no vertex of degree 2 (enumerated at sequence A000014 in the OEIS ). A forest is an undirected acyclic graph or equivalently a disjoint union of trees. Trivially so, each connected component of a forest is a tree. As special cases, the order-zero graph (a forest consisting of zero trees), a single tree, and an edgeless graph, are examples of forests. Since for every tree V − E = 1 , we can easily count

704-431: Is acyclic. As with directed trees, some authors restrict the phrase "directed forest" to the case where the edges of each connected component are all directed towards a particular vertex, or all directed away from a particular vertex (see branching ). A rooted tree is a tree in which one vertex has been designated the root. The edges of a rooted tree can be assigned a natural orientation, either away from or towards

748-467: Is both connected and acyclic. Some authors restrict the phrase "directed tree" to the case where the edges are all directed towards a particular vertex, or all directed away from a particular vertex (see arborescence ). A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that

792-407: Is often very limited. Forms of family trees are also used in genetic genealogy . In 2022, scientists reported the largest detailed human genetic genealogy, that unifies human genomes from many sources for insights about human history , ancestry and evolution and demonstrates a novel computational method for estimating how human DNA is related via a series of 13 million linked trees along the genome,

836-691: Is that of the Lurie lineage—which includes Sigmund Freud and Martin Buber —and traces back to Lurie, a 13th-century rabbi in Brest-Litovsk, and from there to Rashi and purportedly back to the legendary King David , as documented by Neil Rosenstein in his book The Lurie Legacy . The 1999 edition of the Guinness Book of Records recorded the Lurie family in the "longest lineage" category as one of

880-411: Is the multinomial coefficient A more general problem is to count spanning trees in an undirected graph , which is addressed by the matrix tree theorem . (Cayley's formula is the special case of spanning trees in a complete graph .) The similar problem of counting all the subtrees regardless of size is #P-complete in the general case ( Jerrum (1994) ). Counting the number of unlabeled free trees

924-657: The Keita dynasty of Mali, for example, have had their pedigrees sung by griots during annual ceremonies since the 14th century. Meanwhile, in Nigeria, many ruling clans—most notably those descended from Oduduwa —claim descent from the legendary King Kisra . Here too, pedigrees are recited by griots attached to the royal courts. In some pre-contact Native American civilizations , genealogical records of ruling and priestly families were kept, some of which extended over several centuries or longer. There are extensive genealogies for

SECTION 20

#1732773117362

968-669: The Tree of Jesse in medieval art, used to illustrate the Genealogy of Christ in terms of a prophecy of Isaiah (Isaiah 11:1). Possibly the first non-biblical use, and the first to show full family relationships rather than a purely patrilineal scheme, was that involving family trees of the classical gods in Boccaccio 's Genealogia Deorum Gentilium ("On the Genealogy of the Gods of

1012-404: The "one more vertex than edges" relation. It may, however, be considered as a forest consisting of zero trees. An internal vertex (or inner vertex) is a vertex of degree at least 2. Similarly, an external vertex (or outer vertex, terminal vertex or leaf) is a vertex of degree 1. A branch vertex in a tree is a vertex of degree at least 3. An irreducible tree (or series-reduced tree)

1056-474: The Gentiles"), whose first version dates to 1360. In addition to familiar representations of family history and genealogy as a tree structure, there are other notable systems used to illustrate and document ancestry and descent. An Ahnentafel ( German for "ancestor table") is a genealogical numbering system for listing a person's direct ancestors in a fixed sequence of ascent: and so on, back through

1100-858: The Torah, the Kohanim are descended from Aaron . Genetic testing performed at the Technion has shown that most modern Kohanim share common Y-chromosome origins, although there is no complete family tree of the Kohanim. In the Islamic world, claimed descent from Muhammad greatly enhanced the status of political and religious leaders; new dynasties often used claims of such descent to help establish their legitimacy. Elsewhere, in many human cultures, clan and tribal associations are based on claims of common ancestry, although detailed documentation of those origins

1144-432: The center to portray four or five generations, which reflect the natural growth pattern of a tree as seen from the top but sometimes there can be great-great-grandparents or more. In a descendant tree, living relatives are common on the outer branches and contemporary cousins appear adjacent to each other. Privacy should be considered when preparing a living family tree. The image of the tree probably originated with that of

1188-486: The children. Conversely, given an ordered tree, and conventionally drawing the root at the top, then the child vertices in an ordered tree can be drawn left-to-right, yielding an essentially unique planar embedding. Cayley's formula states that there are n trees on n labeled vertices. A classic proof uses Prüfer sequences , which naturally show a stronger result: the number of trees with vertices 1, 2, …, n of degrees d 1 , d 2 , …, d n respectively,

1232-515: The descendants of the other Four Sages (Confucius, Mencius , Zengzi , and Yan Hui ), the descendants of Confucius still determine part of their children's given names using this generation poem given to them by the Ming dynasty Jianwen Emperor and extended by later emperors: 希言公彥承，宏聞貞尚衍； 興毓傳繼廣，昭憲慶繁祥； 令德維垂佑，欽紹念顯揚； 建道敦安定，懋修肇彝常； 裕文煥景瑞，永錫世緒昌。 Family tree Genealogical data can be represented in several formats, for example, as

1276-663: The family traced their descent back to the House of David . The genealogy of Ancient Egyptian ruling dynasties was recorded from the beginnings of the Pharaonic era c.  3000 BC to the end of the Ptolomaic Kingdom ; although this is not a record of one continuously linked family lineage, and surviving records are incomplete. Elsewhere in Africa, oral traditions of genealogical recording predominate. Members of

1320-824: The first millennium BC; with claimed or mythological origins reaching back further. Roman clan and family lineages played an important part in the structure of their society and were the basis of their intricate system of personal names. However, there was a break in the continuity of record-keeping at the end of Classical Antiquity . Records of the lines of succession of the Popes and the Eastern Roman Emperors through this transitional period have survived, but these are not continuous genealogical histories of single families. Refer to descent from antiquity . Many noble and aristocratic families of European and West Asian origin can reliably trace their ancestry back as far as

1364-493: The following equivalent conditions: If G has finitely many vertices, say n of them, then the above statements are also equivalent to any of the following conditions: As elsewhere in graph theory, the order-zero graph (graph with no vertices) is generally not considered to be a tree: while it is vacuously connected as a graph (any two vertices can be connected by a path), it is not 0-connected (or even (−1)-connected) in algebraic topology, unlike non-empty trees, and violates

Family tree of Confucius in the main line of descent - Misplaced Pages Continue

1408-413: The generations. Apart from the subject or proband , who can be male or female, all even-numbered persons are male, and all odd-numbered persons are female. In this scheme , the number of any person's father is double the person's number, and a person's mother is double the person's number plus one. This system can also be displayed as a tree: A fan chart features a half circle chart with concentric rings:

1452-405: The label of u is smaller than the label of v ). In a rooted tree, the parent of a vertex v is the vertex connected to v on the path to the root; every vertex has a unique parent, except the root has no parent. A child of a vertex v is a vertex of which v is the parent. An ascendant of a vertex v is any vertex that is either the parent of v or is (recursively) an ascendant of

1496-457: The left and his or her ancestors appear to the right. Conversely, a descendant chart, which depicts all the descendants of an individual, will be narrowest at the top. Beyond these formats, some family trees might include all members of a particular surname (e.g., male-line descendants). Yet another approach is to include all holders of a certain office, such as the Kings of Germany , which represents

1540-508: The mid to late first millennium AD; some claiming undocumented descent from Classical Antiquity or mythological ancestors. In Europe, for example, the pedigree of Niall Noígíallach would be a contender for the longest, through Conn of the Hundred Battles ( fl. 123 AD) ; in the legendary history of Ireland, he is further descended from Breogán , and ultimately from Adam, through the sons of Noah. Another very old and extensive tree

1584-437: The number of trees that are within a forest by subtracting the difference between total vertices and total edges. V − E = number of trees in a forest. A polytree (or directed tree or oriented tree or singly connected network ) is a directed acyclic graph (DAG) whose underlying undirected graph is a tree. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that

1628-470: The oldest-known living families in the world today. Family trees and representations of lineages are also important in religious traditions. The biblical genealogies of Jesus also claim descent from the House of David, covering a period of approximately 1000 years. In the Torah and Old Testament, genealogies are provided for many biblical persons, including a record of the descendants of Adam. Also according to

1672-502: The reliance on marriage to link dynasties together. The passage of time can also be included to illustrate ancestry and descent. A time scale is often used, expanding radially across the center, divided into decades. Children of the parent form branches around the center and their names are plotted in their birth year on the time scale. Spouses' names join children's names and nuclear families of parents and children branch off to grandchildren, and so on. Great-grandparents are often in

1716-429: The root to v passes through u . A rooted tree T that is a subgraph of some graph G is a normal tree if the ends of every T -path in G are comparable in this tree-order ( Diestel 2005 , p. 15). Rooted trees, often with an additional structure such as an ordering of the neighbors at each vertex, are a key data structure in computer science; see tree data structure . In a context where trees typically have

1760-403: The root, in which case the structure becomes a directed rooted tree. When a directed rooted tree has an orientation away from the root, it is called an arborescence or out-tree ; when it has an orientation towards the root, it is called an anti-arborescence or in-tree . The tree-order is the partial ordering on the vertices of a tree with u < v if and only if the unique path from

1804-498: The ruling dynasties of China, but these do not form a single, unified family tree. Additionally, it is unclear at which point(s) the most ancient historical figures named become mythological. In Japan, the ancestry of the Imperial Family is traced back to the mythological origins of Japan. The connection to persons from the established historical record only begins in the mid-first millennium AD. The longest family tree in

Family tree of Confucius in the main line of descent - Misplaced Pages Continue

1848-474: The subject is the inner circle, the second circle is divided in two (each side is one parent), the third circle is divided in four, and so forth. Fan charts depict paternal and maternal ancestors. While family trees are depicted as trees, family relations do not in general form a tree in the strict sense used in graph theory , since distant relatives can mate. Therefore, a person can have a common ancestor on both their mother's and father's side. However, because

1892-512: The world is that of the Chinese philosopher and educator Confucius (551–479 BC), who is descended from King Tang (1675–1646 BC). The tree spans more than 80 generations from him and includes more than 2 million members. An international effort involving more than 450 branches around the world was started in 1998 to retrace and revise this family tree. A new edition of the Confucius genealogy

1936-682: Was printed in September 2009 by the Confucius Genealogy Compilation Committee , to coincide with the 2560th anniversary of the birth of the Chinese thinker. This latest edition was expected to include some 1.3 million living members who are scattered around the world today. Before the Dark Ages , in the Greco-Roman world, some reliable pedigrees dated back perhaps at least as far as the first half of

#361638