[Discrete Mathematics] Trees

Подписаться 273 тыс.

Просмотров 207 тыс.

50% 1

We look at a subset of graphs called trees.
Visit our website: bit.ly/1zBPlvm
Subscribe on RU-vid: bit.ly/1vWiRxW
-Playlists-
Discrete Mathematics 1: • Discrete Math (Sets, L...
Discrete Mathematics 2: • Discrete Math (Countin...
-Recommended Textbooks-
Discrete and Combinatorial Mathematics (Grimaldi): amzn.to/2T0iC53
Discrete Mathematics (Johnsonbaugh): amzn.to/2Hh7H41
Discrete Mathematics and Its Applications (Rosen): amzn.to/3lUgrMI
Book of Proof (Hammack): amzn.to/35eEbVgLike us on Facebook: on. 1vWwDRc
Submit your questions on Reddit: bit.ly/1GwZZrP
Hello, welcome to TheTrevTutor. I'm here to help you learn your college courses in an easy, efficient manner. If you like what you see, feel free to subscribe and follow me for updates. If you have any questions, leave them below. I try to answer as many questions as possible. If something isn't quite clear or needs more explanation, I can easily make additional videos to satisfy your need for knowledge and understanding.

Опубликовано:

24 авг 2015

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 38

@chrissolace 3 года назад

Thank you for the helpful video! I had a little trouble at 6:00 but i realized that all you were doing was rearranging (e' = e - 1) and (v' = v - 1) into (e' + 1 = e) and (v' + 1 = v) and then plugged it into the earlier equation (e = v - 1)! It probably took me a bit because I am just a visual learner and I needed to see all the steps. (I'm also typing this out just in case anyone else has the same issue as me later on!)

@user-qv7on3dl9y 2 месяца назад

Probably also worth reiterating that this is a proof around the theorem e = v-1. The final part of the proof begins from where e=v-1 is written. e' + 1 which is equivalent to e = v' + 1 which is equivalent to v then we - 1 (which is representing our hypothesis of e = v-1). Think of each line as a edging together closer and close to the proof. Note the +1-1 cancels out and we are left with e' + 1 = v' which essentially says for a tree if you need the number of vertices add 1 to the number of edges. In the final line we are essentially delivering the final proof statement that if we know the previous (for a tree if you need the number of vertices add 1 to the number of edges) then it is fair to conclude if we remove 1 from the total vertices we are left with the formula e' = v' - 1 essentially finishing the proof that to get the edges we deduct the 1 from the number of vertices. Sorry for the bad english I am at home sick.

@tasfiatabassum5130 8 лет назад

thanks a lot, it really helped me, thank u for giving so much of time in teaching all these topic.

@badass2485 7 лет назад

These tutorials have really been very helpful! Thank you sir for explaining the concepts and making them crystal clear! I'm really surprised of the fact that u just have 15k subscribers u seriously deserve to have a lot more.

@jagritiyadavv 4 года назад

114k now :)

@andromedaghostgames 2 года назад

@@jagritiyadavv 209k now

@mvsdprosniper Год назад

@@andromedaghostgames hey babe

@hinaafzal1254 7 лет назад

Thnx for uploading all of ur videos are like diamond to me..thnx it helped a lot

@shoukathali1768 2 года назад

I like everything bout this channel except : he doesn't make playlists and I can't find the order to watch the videos.

@maheshkumargupta8041 6 лет назад

Show by means of an example that a simple diagraph in which exactly one node has indegree 0 and every other node has indegree 1 is not necessary a directed tree?

@chetankawarkhe9902 5 лет назад

which software is this in you video????

@maheshkumargupta8041 6 лет назад

How many different directed trees are there with three nodes ????

@anakinkylo.thepomenerianan9084 Год назад

Awesome you can also use Eulers formula to prove a tree has n-1 edges since the region is 1(infinite space) and trees are planar r=e-v+2, r=1 & v=n . However I like the way you proved it makes more senser

@benjaminandersson2572 Год назад

3:01 Do you mean cycle? Or is loop = cycle in your terminology?

@dacianbonta2840 3 года назад

@5:16 Whif the vertex has more than one edge coming outta it? well, the graph disconnects, but proving THAT complicates things. better unleash Euler's Bazooka (v-e+r=2, with r=1). giving the desired answer. I mean, what's the use of developing Euler's Bazooka (moar like Euler's Panzerfaust, amirite) if you don't use it?

@hanyi5867 7 лет назад

if e >= 1 shouldnt there be at least two vertices instead of one?

@shubhochowdhury6898 4 года назад

It is not possible to create a tree with one vertex.

@lyndongingerich1482 4 года назад

@@shubhochowdhury6898 Why not? A single vertex is a connected graph with no simple circuits.

@wolfcompany2 3 года назад

@@lyndongingerich1482 Thats a loop, itself is a circuit... special type of circuit

@lyndongingerich1482 3 года назад

@@wolfcompany2 Interesting. Thanks!

@ericgill1812 6 лет назад

Hey man, what if you delete a vertex with a degree of 2? Doesn't that throw the proof of e=v-1 out of whack? Thanks

@Trevtutor 6 лет назад

But then you would have an isolated vertex below it (the deleted vertex's daughter) and thus it would no longer be a single tree.

@ericgill1812 6 лет назад

Of course, thanks for your reply!

@tomh6667 4 года назад

@@Trevtutor That's true, but you glossed over that a bit. The proof didn't seem very robust as a result, IMO. I realize that you have limited time in a video when you're trying to cover material, but just trying to throw out some (hopefully) constructive criticism.

@valeriereid2337 4 месяца назад

Thanks for this.

@hodgsontetteh4058 5 лет назад

man i got an A thanks man for yr help

@tryingtolearn2966 7 лет назад

I am having difficulty with the proof by induction. The basis step talks about |e|=0. and then you show that if the property already holds for some tree, then it'll hold for a **smaller** tree. But this is not the same as the "k+1" step. for this proof to be complete, don't you need to start from the largest possible tree instead of the smallest possible tree?

@Trevtutor 7 лет назад

You show that it holds for the smallest possible tree (e=0), then for some arbitrary e=k+1, you show that it can be broken down into components e

@tryingtolearn2966 7 лет назад

Thanks! I am still a bit confused as to what is going on around time 6:05. The way I understand it, is that you apply the induction hypothesis to the bigger tree (using e'+1), and from that, you show about e'. by the way, my I ask which tools you're using to produce these beautiful videos? software? devices?

@commenting000 3 года назад

@@tryingtolearn2966 Really, it's just that if you assume the tree you're working with is consistent with e = v - 1, then by removing an edge, the resulting tree also seems to show the same properties. All you need to do is prove that this resulting tree actually does follow the hypothesis, and to prove that, you just need to remove an edge from it and prove that the next tree also follows it. Eventually, you'll stumble upon the base case tree that has already been proven to have the wanted consistency, which creates a chain reaction. Remember, all trees start out with 1 vertice. By adding an edge, you must also add a vertice that it will connect to, keeping the degrees of each individual vertice = 1.