Chapter 1 | The Beauty of Graph Theory
ฝัง
- เผยแพร่เมื่อ 31 ก.ค. 2024
- 0:00 Intro
0:28 Definition of a Graph
1:47 Neighborhood | Degree | Adjacent Nodes
3:16 Sum of all Degrees | Handshaking Lemma
6:29 Graph Traversal | Spanning Trees | Shortest Paths
11:49 The Origin of Graph Theory
14:10 A Walk through Königsberg
15:34 Path | Cycle | Trail | Circuit | Euler Trail | Euler Circuit
18:47 Euler's Theorems
19:42 Kinds of Graphs
20:05 The 4 Main-Types of Graphs
20:38 Complete Graph
22:10 Euler Graph
22:21 Hamilton Graph
22:41 Bipartite Graph | k-partite Graph
23:42 Disconnected Graph
23:46 Forest | Tree
24:01 Binary Tree | Definitions for Trees
24:47 Ternary Tree
24:59 Applications of Binary Trees (Fibonacci/Quick Sort)
26:15 Complete Binary Tree
26:50 Full Binary Tree
27:02 Degenerated Binary Tree
27:14 Perfect Binary Tree
27:24 Balanced Binary Tree
27:40 Array | Stack | Queue
29:12 Doubly Linked List | Time Complexity
32:07 Binary Search Tree
36:34 Red-Black Tree
38:12 AVL Tree
39:05 Heap
39:45 Heap Sort
41:35 Naive Representation of Graphs
42:27 Adjacency Matrix | Undirected Unweighted Graph
43:27 Adjacency List | Undirected Unweighted Graph
44:17 Representation of a Directed Unweighted Graph
44:38 Representation of Weighted Graphs
Blender Models:
▶ Wooden Table: sketchfab.com/3d-models/woode...
SVG/PNG graphic files:
▶ Some PNG figures have been created with ProCreate
▶ Power Pole: lovepik.com/image-450075031/e...
▶ SVG Man Icon: www.onlinewebfonts.com/icon/5...
Music:
▶ Vincent Rubinetti
Download the music on Bandcamp:
vincerubinetti.bandcamp.com/a...
Stream the music on Spotify: open.spotify.com/playlist/3zN...
▶ Lullaby - Cooper Cannell
▶ • Free Piano Intro Music...
Sound effects: mixkit.co/free-sound-effects/
Animations have been created with Manim, Blender and Adobe Premiere Pro.
Manim: docs.manim.community/en/stable/
#graphtheory #graphs
For once youtube recommended something so underrated yet so awesome, loved every second of this!
An amazing high-quality video. This was very helpful, thanks.
I like the fact you included the history of graph theory in the video. Not even introductory texts do that.
i don't generally comment but: its a wonderful video i am amazed how you would have created such a complex video, must have used Manim, also it would have taken lot of research. cant believe that i am the first person to comment. thanks for this video it created a spark of interest in me for learning more about the topic as my university is teaching me. anyway thanks for this video and i hope your video and channel grows. ❤ Love from India 🇮🇳🕉.
Thank you very much for your kind words! I'm glad you enjoyed the video. There's much more to come, and yes, I used Manim for most of the animations in this video.
The ancient religions , Buddhism Hinduism etc, have long understood the interconnected nature af the universe and how nodes and strings connect all points in space and time, there is so much beauty in mathematics, I wish I had a deeper understanding, great video.
Anyone that posts a 45 minute manim animation about math immediately has my subscription. I don't even care what subject it was in! :D
Lovely video btw :)
Great video. Would recommend as a refresher for any student taking an advanced algorithms course or even discrete math
Please keep producing more content like this? It is such a wonderful supplement to my math studies!
Excellent one. Can't wait for chapter 2. For undirected unweighted graph, Adjacency Sets instead of Adjacency Lists are also helpful.
I don't remember when I first heard about graph, but we studied them in my CS degree and they quickly became one of my favorite topic in math and CS
You broke it down to very understandable bits and supported them with animations showing the points very clearly. Well done!
Amazing work , the quality of the video is fabulous! Thank you for this masterpiece
Clear amd to the point: great work. Respect!
This was incredible, waiting for part 2!!
Feels lucky to be an early viewer. Manim animations are so cool 🥹
Very well done introduction to graph theory, the visuals were key to following the concepts and building intuition. Can't wait to see what you have in store for the following chapters!
You have a new sub. I'm totally hyped for your next video bro. You did an awesome job
this is SOOOOOO beautifully animated and you put in so much work doing this AMAziNG JOB
This video is amazing the right mixture of theoremes and graph visualizzations! I hope u will continue the serie!
This channel only having 920 subs is absolutely criminal
35 subscribers more in 45 minutes. With videos like this is just a matter of time.
Love this man ❤ seems like the algorithm's loving it today too
Such a great resource. Good job!
Thank you for the video! It gave me a lot of ideas! Subscribed, waiting for the next one!
This is a great effort. Looking forward to many more videos from you.
This was the best video on the topic my professors should have try to incorporate things in this manner to make it interesting and easy to understand
Thanks a lot for creating such quality content.❤
cant wait for chapter 2
Quality work , keep this up, subbed
This course is amazing. Thanks for your work
I knew from the start I'd want to watch the whole thing, so I set aside some time and I did! I think everyone should appreciate those moments when the animation plays and lets whatever you have just learned to sink in. Excellent presentation. Universities should start taking notes before they become obsolete lol
what an amazing video lecture! Ty very much!
I am currently reading a book about graph theory and am very thankful for this video series.
I am not Computer science student, I am a programmer, but I love to watch every single graph theory tutorial in YT, i have watched many,
after sometime I started to notice how teachers lecture the graph theory and how, in which order they introduce the theme and which illustrations or animations they use.
It's simply fascinating that graph theory pushes teachers forward to animate didactically, I wonder one day to be one of them.
I just clicked casually and finished it, thanks for wonderful explanation ..
This video is so cool...I'm honestly surprised you had under 200 subscribers, guess I'm here early!!
wooow, thank you!!!
the explanation is awesome!!
These videos are fantastic.
Awesome really appreciate the series on graph theory. Instand subscribed. Keep it going 👍
Im amazed at this video, great job really!
Graph theory got me hooked on mathematics and is one of the reasons I decided to double major in Mathematics. Thanks for the video
Great video. Thanks.
Nice. Infinite graphs, esp trees, are popping up recently in my research because of their connection to metric geometry. I Plan to make some videos on them.
🎯 Key Takeaways for quick navigation:
00:08 *📊 Graph Theory Introduction*
- Definition of a graph: nodes/vertices and edges
- Introduction to undirected, unweighted graphs
- Application of graphs in modeling real-world problems
03:07 *🧮 Degrees and Properties of Graphs*
- Explanation of node degree in a graph
- Observation of the even sum of degrees in graphs
- Relationship between sum of degrees and number of edges
06:08 *🔍 Graph Traversal Algorithms*
- Overview of graph traversal algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS)
- Explanation of BFS and its applications, such as shortest paths
- Introduction to DFS and its use in generating mazes
10:59 *🗺️ Graph Theory Applications*
- Application of graph theory in navigation systems like Google Maps
- Importance of minimum spanning trees in electricity distribution networks
- Examples of graph theory problems in real-world scenarios like pizza delivery routes
12:14 *🕰️ Origin of Graph Theory*
- Historical background: Leonard Euler's contribution to graph theory
- Exploration of the Seven Bridges of Königsberg problem
- Abstracting real-world problems to lay the foundation of graph theory
16:03 *🔑 Fundamental Graph Theory Definitions*
- Definitions of path, cycle, trail, circuit, Euler trail, and Euler circuit
- Clarification of terminology and distinctions between different types of graph walks
- Introduction to Eulerian and Hamiltonian graphs
20:05 *📊 Types of Graphs*
- Classification of graphs into undirected/unweighted, directed/unweighted, undirected/weighted, and directed/weighted
- Introduction to complete graphs and their properties
- Mention of other important graph types like Eulerian and Hamiltonian graphs
22:51 *🔴 Bipartite Graphs and Other Graph Types*
- Definition and properties of bipartite graphs
- Generalization of partitioning nodes into disjoint sets
- Brief overview of other graph types including forests and trees
24:15 *🌳 Explanation of Binary Trees and Their Applications*
- Binary trees are hierarchical data structures where each node can have at most two children, used in various applications like visualizing recursive algorithms and sorting methods.
- Different types of binary trees include binary, ternary, complete, full, degenerated, and perfect binary trees, each with specific properties and applications.
27:56 *📚 Introduction to Basic Data Structures*
- Basic data structures like arrays, stacks, and queues play vital roles in algorithms such as graph traversal.
- Arrays store elements identified by an index, while stacks and queues follow last-in-first-out (LIFO) and first-in-first-out (FIFO) principles, respectively.
29:30 *🔍 Understanding Time Complexity and Operations on Linked Lists*
- Linked lists and doubly linked lists allow immediate access to elements via pointers, with time complexities varying for insertion, deletion, and searching operations.
- Time complexity measures the algorithm's performance concerning input size, typically denoted using Big O notation.
32:02 *🌲 Exploring Binary Search Trees and Their Properties*
- Binary search trees maintain a hierarchical order, enabling efficient searching, insertion, and deletion operations with time complexity dependent on the tree's height.
- Properties like the binary search tree property and balancing criteria determine the efficiency of operations on binary search trees.
36:44 *🌈 Advancements: Red-Black Trees and AVL Trees*
- Red-black trees and AVL trees are self-balancing binary search trees, ensuring logarithmic time complexity for operations by maintaining specific properties.
- These trees offer improved efficiency compared to basic binary search trees, albeit with considerations for insertion complexities.
39:05 *⛏️ Overview of Heaps and Their Applications*
- Heaps, including max heaps and min heaps, provide efficient structures for sorting algorithms like heap sort, with elements arranged hierarchically based on their values.
- Max heaps prioritize the largest element at the root, while min heaps prioritize the smallest element.
41:44 *📊 Efficient Graph Representation Techniques*
- Graphs can be represented using adjacency matrices or adjacency lists, each offering advantages based on memory efficiency and ease of implementation.
- Adjacency matrices store edge connections in a square matrix format, while adjacency lists use arrays of lists to represent edges efficiently.
Made with HARPA AI
Amazing explanation !
Thanks, learn something new today 😊
Great graphics. Thanks for mentioning the software we ca use to make animated graphics.
this outrageously good
Amazing video, next one about graph neural nets please!
Great video :)
Bring more baby!!!!!
That's great👍👍
I Loved Your Content & Eagerly Waiting for Further Lectures Please Complete Graph Theory Deeply Don't Quit Please Please
Thank you very much for the kind words!
I won't quit; I'm absolutely on it, but unfortunately it takes a lot of time. My initial goal was to finish Chapter 2 at the end of April, but I think it will delay a bit.
@@CC_ACADEMY Could you please tell us what you are planning to cover in chapter 2?
@@kunalsuri8316 Chapter 1 was basically an introduction to graph theory. Now we'll consider algorithms in more detail. My main focus in the next video lies on algorithms to compute Euler trails, Euler circuits, Hamilton paths and Hamilton cycles. In this context, we'll also deal with the knight's tour problem (see my latest Short) and some other topics.
Oh ... this channel is good.
This has the same feel as Mandelbrots fractal geometry of nature :)
I did not understand anything but its a great video nonetheless. Great job!
Not for kids .. It's a college level stuff
great
It's true that dense matrix libraries like numpy waste space with zeros using adjacency matrices, but there are sparse matrix libraries that only store the "non-zero" values, like SuiteSparse:GraphBLAS and it's Python binding python-graphblas. This opens up a rich vein of algebraic operations that can be used on graphs using different semirings. For example the "tropical semiring" where addition is substituted with the "min" function and multiplication is substituted with the "plus" function can be used for many different kinds of optimization problems like finding the shortest path in a graph, here's an example in this video th-cam.com/video/JUbXW_f03W0/w-d-xo.html
This is better than my 4 year bachelor and 2 year master 😂😂😂😂😂😂😂😂
Stop lying....
❤
Bro I loved this video! Can you share the source code for the animations?
Hey super great video, very instructive :))
I am an IT college student and would like to visualise mathematical concepts in graphics like you do. What kind of 3D software do you use?
I'm glad you like it :) Nearly all animations in this video have been created with Manim: docs.manim.community/en/stable/
Sometimes I also used Blender, see e.g., from 14:18 to 15:42.
In general, everything I used can always be found in the description.
Curious to one day hear about hypergraphs and Stephen Wolfram's Theory of Everything!
Hypergraphs are indeed very interesting and could be covered at some point in this series. Thank you for the suggestion!
Wow the adjancy matrix being a metric for these special graphs is amazing. Can you use it to translate problems from graph theory to or from problems in linear algebra ?
What's very interesting in my opinion is that the eigenvalues of a graph's adjacency matrix can reveal important properties of the graph. It’s for instance possible to tell whether a graph is bipartite [see 22:49] only by considering all eigenvalues of the corresponding adjacency matrix. In fact, this would be a great topic for a Short, thank you!
@@CC_ACADEMY amazing, thanks for the reply!!
17:48 So, an Euler trail is just a regular trail that involves strictly all nodes. The definitions are the same, to my understanding, because distinct edges implies they're walked on exactly once and this same phrase is used below. Am I wrong?
Edit: I meant edges but wrote nodes in the first sentence
😅
A trail is a walk such that all its edges are distinct. An Euler trail is a trail that visits EACH EDGE of the underlying graph (not each node) exactly once.
Hear from 16:58 and take a look at the trails in the animations!
In a graph similar to the Königsberg graph, an Euler trail should visit all bridges, while a simple trail should only avoid repeating bridges.
You can remember: If 'Euler' is in front of a trail or circuit, it means immediately visiting all edges of the graph.
@@CC_ACADEMY Huge respect for taking the time to comment. My assumption was right, but for whatever reason I typed 'nodes' instead of 'edges'. I should stop watching these types of videos at midnight haha
Please make a playlist on information theory.
Indeed a very interesting field, but the focus for now lies primarily on fundamental graph theory algorithms and theorems.
How can I reach out to you? I'm trying to create a tree categorization of types of graphs!
At the moment, it's unfortunately not possible to contact me directly as I'm very busy with my university responsibilities and the preparation of future videos.
But maybe this will change in the future.
Will you make video about Lie thoery one day?
I honestly don't know at the moment. The focus in the early future will lie primarily on the fundamental graph theory algorithms and theorems.
Just sliding in here to say that there IS a reason that "graphs" from graph theory and "graphs" of functions share a name; it isn't a coincidence.
The graph of a function F is simply the *set of ordered pairs* (x,y) such that F(x)=y.
And what is a (directed) graph, in graph theory? Again, a *set of ordered pairs*, ie a set of directed edges. Ignore disconnected nodes, but still.
A graph of a function is a special case of a graph-theory graph. And when you plot the function, the picture is just a drawing of the adjacency matrix of the graph, albeit a continuous one rather than the typical discrete matrices we see.
Euler path/circuit is also referred to as a “Hamiltonian path/circuit”
No, while both concepts deal with traversing graphs, the key difference lies in whether every edge (Euler) or every node (Hamiltonian) is visited exactly once.
When is the next episode?
I am working on it as fast as I can, but creating a video of this length takes its time. The next episode will be published within the next 2 months. But there will (probably) be a trailer released before that. After reading all of your kind comments, I'm going to try to make it extra special.
Where are the other chapters?
The production of such a video takes a lot of time. I'm working on 'Chapter 2' as fast as I can, but it will probably take 1-2 months to finish.
Gave up trying to watch this between advertisements every other minute
I'm sorry to hear that, but I have (to my knowledge) no influence over this. At this point I have nothing to do with any kinds of advertisements.
Thank you❤🎉
FUCKING GLORIOUS