Discrete Math - 11.1.1 Trees

Summary

In "Discrete Math - 11.1.1 Trees," Kimberly Brehm introduces trees as a special type of graph that is both connected and has no cycles. She explains that a tree has a unique path between any two vertices. Brehm discusses concepts like rooted trees, where one vertex is the root, and uses fun examples to illustrate family-like relationships among vertices such as parent, child, and sibling. She also explains different types of trees including binary and m-ary trees, and ends with some basic tree math involving the number of vertices and edges. The video provides a solid foundation for understanding trees in discrete math.

Highlights

• Trees are a type of graph that's connected and has no cycles, providing unique pathways between nodes 🌳.
• Making one vertex the 'root' transforms a regular tree into a rooted tree, similar to a family tree genealogy 🌳.
• Vertices in rooted trees have familial roles: parents, children, and siblings, providing an intuitive understanding 🤝.
• Binary and m-ary trees are sophisticated trees with specific numbers of children per node, adding order to the structure 📊.
• In trees, the number of vertices is always one more than the number of edges, hinging on their acyclic nature 🔢.

Key Takeaways

• Trees are graphs that are connected and have no cycles; each vertex is uniquely connected to others 📚.
• Rooted trees designate a specific vertex as the root; think of this like a family tree 🌳.
• Relationships in rooted trees are similar to real-life families: parents, children, siblings 👫.
• Binary trees have a specific structure where each internal vertex ideally has two children; perfect for organizing data 💻.
• Understanding the vertex-edge relationship in trees is crucial; more vertices mean just one more edge needed 🌐.

Overview

In this engaging session, Kimberly Brehm demystifies the concept of trees in discrete math. She starts by explaining that trees are special graphs: connected and without cycles, which ensures a unique path between any two vertices. Switching to rooted trees, Brehm designates a root to add structure like family trees, expanding learners' understanding with relatable concepts.

Brehm likens tree vertices to family members with terms such as parent, child, and sibling. This analogy aids in grasping complex concepts easily. The session moves through various tree forms such as binary and m-ary trees, emphasizing structured arrangements and offering deeper insights into organizing hierarchical data.

Concluding with tree math, Brehm tackles vertex and edge relationships. She simplifies the crucial details about tree structures: every tree with 'v' vertices will invariably feature 'v-1' edges, outlining the fundamental acyclic characteristic of trees. This thorough walkthrough ensures comprehensibility in the essentials of tree structures.

Chapters

• 00:00 - 01:00: Introduction to Trees This section introduces trees as a special kind of graph characterized by being connected and having no cycles. A tree is demonstrated as each vertex connects to another without creating any cycles.
• 01:00 - 05:00: Rooted Trees and Terminology The chapter discusses the concept of rooted trees and the unique paths between vertices. It highlights that in a rooted tree, there is a single, specific path from one vertex to another, exemplified by the path from vertex 'a' to vertex 'f' via 'b'. However, introducing a cycle would alter this structure by providing multiple paths.
• 05:00 - 09:00: Special Types of Trees The chapter explores special types of trees, focusing on scenarios where a graph may no longer be considered a tree. This includes instances where a cycle is present or when there are multiple paths to reach a vertex from another vertex. When multiple trees exist within the same graph, it's referred to as a 'forest.' The explanation uses specific vertices labeled as C, D, and F to illustrate these concepts.
• 09:00 - 13:00: Properties and Basic Math of Trees This chapter discusses the concept of a forest in graph theory, which occurs when a segment connecting two parts is removed, resulting in more than one tree. It also introduces rooted trees, a special kind of tree where one vertex is designated as the root, with an example using vertex F as the root and the tree being redrawn accordingly.
• 13:00 - 16:00: Tree Math Examples The chapter discusses tree mathematics by focusing on an example where node 'f' is connected to node 'h' in a rooted tree structure. The directional nature of connectivity in rooted trees is highlighted, noting that while arrows could be used to indicate direction, they are often omitted because directionality is inherent in rooted tree representations. The narrative suggests placing the root node at the top to emphasize the hierarchical structure, followed by its connection to node 'h', and further implies additional connections from node 'h'.
• 16:00 - 18:30: Conclusion and Sections Not Covered The chapter discussed the concept of vertices, outlining a specific formation where vertex 'g' and 'i' do not connect to anything directly. However, 'a' serves as a connection point to 'b', which further connects to 'c' and 'd'. The narrative implies an analysis of graph structures or networks, emphasizing the specific connectivity between points or nodes. The conclusion highlights these connections, and notes sections that were not covered in detail within this context.

Discrete Math - 11.1.1 Trees Transcription

• 00:00 - 00:30 in this video we're going to learn about trees a tree is simply a special kind of graph and a graph is considered a tree if it is both connected and has no cycles so you can see here that i have a tree and it is connected meaning each vertex is connected in some way to another vertex on our graph and it has no cycles and another way that we could say this
• 00:30 - 01:00 is that there is a unique path from each vertex to another vertex so notice let's say i want to get from a to we'll call this f if i want to get from a to f the only way to get there is to travel well we'll just call this b just for fun travel to b and then to f now if i were to create a cycle now i could get to f
• 01:00 - 01:30 by traveling straight down we'll call that c and then down again we'll call that d and then over to f so from here we can see this is no longer a tree because a it's got a cycle and b there's more than one way to get to a particular vertex from another vertex now if we happen to have more than one tree just like in the real world then we call this a force we can see that this is the same graph that i have
• 01:30 - 02:00 above all i've done is i've taken away the segment that connects the two portions and therefore this is called a forest because i have more than one tree a special kind of tree is called a rooted tree and a rooted tree is essentially when we designate one of our vertices to be the root so just for fun let's use f to be our root so if f was our root then we would simply redraw the tree
• 02:00 - 02:30 and notice that f is connected only to h and we wouldn't have to put the arrows that we would typically do for a directed graph because a rooted tree is a directed graph notice i could put an arrow that connects f to h in that one direction but typically we don't do that because it's implied based on a rooted tree so we put the root at the top and then that connects to h h connects to three
• 02:30 - 03:00 vertices and that is to g i and a oops i should leave room and g doesn't connect to anything i doesn't connect to anything but a then would connect to b and b connects to c and d
• 03:00 - 03:30 and d connects to e so this is how i would draw the existing graph existing tree as a rooted tree with f as the root and again it's not necessary for you to put those arrows in there because they are implied because it is a rooted tree i want to take you through some terminology related to rooted trees and
• 03:30 - 04:00 we're going to sort of skip around i'm going to start here in the middle um talking about relationships among vertices so the good news is if you're familiar with the english language you already know what these words mean when it comes to families and they're the same meaning when it comes to vertices for instance a parent would be a vertex like a that has children so b and c are a's children so a is a parent and b and c are children
• 04:00 - 04:30 whereas for instance e is a parent and has i as a child but obviously e is also a child of b just like in real normal families siblings would be two children of the same parent so in this case b and c would be considered siblings ancestor would be obviously a parent or grandparent or great-grandparent in real
• 04:30 - 05:00 life and that's exactly what it is here on our graph so if i was looking at e i would say ancestors of e would include b and a whereas descendants of e would be just the child i so again ancestors are essentially above that particular vertex and descendants are directly related and below so for instance for e i could not call j
• 05:00 - 05:30 a descendant even though it is below e it's not directly connected to e so i would be the only descendant of e so that's all the family stuff so we got all of those taken care of now let's talk about leaves when you're looking at a graph your vertices must either be a leaf or an internal vertex an internal vertex just means that it has children so in our particular graph a and b and c
• 05:30 - 06:00 and g and f and e and d all of those would be considered internal vertices whereas leaves would be anything that does not have children so in this case that would be h and i and j and k so we've talked about both of those a pendant a pendant is a vertex with a
• 06:00 - 06:30 degree of one we're going to talk more about that in a little bit but for instance if i looked at h or i or j or k those all have degree 1 which happen to be leaves here but for instance if i look at c c has a degree of 2 because it's connected to both a and g so c would not
• 06:30 - 07:00 be considered a pendant let's pop back to the top before we talk about a sub tree so let's talk about a binary tree or an m airy tree when we're talking about an emery tree m is going to be replaced with a number so if you'll look at the degree of each of our um i'm sorry not the degree really we're looking at how many descendants how many children each vertex has
• 07:00 - 07:30 so a has two children b has three children c has one child and so on and so forth so when we're talking about an emery tree this would be considered a three airy tree because each vertex has at most three children if it's a full emery tree that would mean that each vertex has exactly three children so obviously this is not
• 07:30 - 08:00 a full three area tree now i could create what we call a full binary tree a full binary tree would mean that each vertex that has children has exactly two children so a b c d e f g this would be considered a full binary tree binary of course by means two so it's a two airy tree and this would be considered a full
• 08:00 - 08:30 binary tree because each vertex each internal vertex has exactly two children so the last one is a subtree and a sub tree is essentially a tree that is created um by it's kind of like our induced subgraphs of our previous lessons if i want to look at say a subtree of c then it would just be c
• 08:30 - 09:00 and g and k so it would start with c as the root node and then any descendants of c i want to talk just a bit about some of the properties of trees but i do want to point out to you that i'm not going to go through all of the vertex math we call it that goes along with a full emery tree i just don't feel it's important for our study in this course i did cover that
• 09:00 - 09:30 material in discrete math 1 in that playlist video number 80. but let's just talk real quick about the number of edges versus the number of vertices this should be fairly straightforward i've created a little table for you just so that you can see but basically however many vertices we have we're going to have one fewer edge and that makes sense because we know we can't have any cycles or loops
• 09:30 - 10:00 so we need just one distinct path from each vertex to each other to another vertex so for instance if i have just one node i don't have any edges because i can't connect a node or vertex to itself if i have two vertices there's just one way to connect those two and if i have three vertices then there's only two edges that i can possibly create so again it's pretty straightforward that
• 10:00 - 10:30 whatever number we have for v the number we have for e or the cardinality of the set of edges will be one less than that so we can either say that the cardinality of v is equal to the cardinality of the edges plus one because obviously the edges is less by one so we would have to add one or we can say in order to get the number of
• 10:30 - 11:00 edges we would take the number of vertices and subtract one let's do just a bit of tree math so what i mean is let's take a look at what we know about what we just talked about with the number of edges sorry the number of vertices being equal to the number of edges plus one or the number of edges being equal to the number of vertices minus one
• 11:00 - 11:30 so we have two separate trees t1 and t2 and for our first tree the number of edges is 11 and for our second tree the number of vertices is two times the number of vertices in the first tree and essentially we're trying to find anything that's missing which is the number of vertices in our first tree in our second tree and the number of edges in our second tree and the only thing that we're given here is that e1 is equal to 11. so obviously if i'm
• 11:30 - 12:00 trying to find v1 then it stands to reason i could take e1 plus 1 which would be 11 plus 1 or 12. so now i have the number of vertices in my first tree and i can use that to now find the number of vertices in my second tree so if v2 is equal to 2 times the number of vertices in my first tree that's 2 times
• 12:00 - 12:30 12 or 24. so my second tree has 24 vertices how many edges does it have well again the number of edges in e2 is going to be the number of vertices in v2 minus 1 which would be 24 minus 1 or 23 and again you're certainly welcome to draw any of those out that you'd like but it's not necessary we will be skipping section 11.2
• 12:30 - 13:00 applications of trees feel free to give that a read there's really nothing in there that i could cover that you can't just read on your own and section 11.3 about tree traversals we're not going to cover that either we're going to go straight to 11.4 spanning trees with a depth first search