Introduction to Graph Theory: A Computer Science Perspective

In this video, I introduce the field of graph theory. We first answer the important question of why someone should even care about studying graph theory through an application perspective. Afterwards, we introduce definitions and essential terminology in graph theory, followed by a discussion of the types of graphs you may encounter. We then define several ways to represent graphs as a data structure and finish off the video with a discussion of what types of interesting problems you can ask about graphs to help motivate the ideas in future videos.
Typo correction: at 5:12 the vertex set V should be {0, 1, 2, 3, 4} instead of {0, 1, 2, 3, 4, 5} (there is no vertex 5).
Big thanks to Dániel László Bertalan for making the closed captions for this video!
The sudoku example was inspired by this incredible reddit visualization: / visualizing_the_sudoku...
Support: / reducible
This video wouldn't be possible without the open source manim library created by 3blue1brown: github.com/3b1b/manim
Here is link to the repository that contains the code used to generate the animations in this video: github.com/nipunramk/Reducible
Music:
October by Kai Engel freemusicarchive.org/music/Ka...
November by Kai Engel
freemusicarchive.org/music/Ka...
Cobweb Morning by Kai Engel
freemusicarchive.org/music/Ka...

[@OliFarhaan]

I was unable to take admission to an engineering college to pursue Software Engineering due to my financial conditions. But I never lost hope I am studying on my own self and I feel privileged that I came to know about your channel. Thank you so much for such valuable content.

[@realdealholyfield9616]

Are you indian or paki?

[@harrykekgmail]

I wish you success

[@OliFarhaan]

@@harrykekgmail I wish you too :)

[@robertalbus4430]

I am a self-taught software developer with an established career. you can do this too. university is not required. the best advice to all readers is to start with web dev because it is the easiest path to starting a career. then on your own time study CS and interesting problems - because of this you will gain a fabulous education and your career will advance. good luck Ali Farhan

[@chafikthewarrior]

I am an autodidact Data Scientist, i started with Web development and i did everything using only google, no school. You can do it but you need to be 10 times better than the others may god help you in your journey.

[@einsteinnewton7121]

3Blue1Brown of Computer Science. Brilliant video.

[@vijaykumarreddyalavala3713]

Absolutely.

[@IsaacJoshi]

When I was watching this I thought hmm why does 3B1B's voice sound different

[@genericusername1243]

haha even i thought so

[@gauravarya8952]

Absolutely Brother. Such nice content in this vast ocean of copy cat junks.

[@kenhaley4]

@@KonigKlack They are. He gives credit in the notes below the video.

[@gauravnikam8843]

Introduction :- 0:00 Why Study Graph :- 1:33 Definition :- 4:35 Terminologies :- 5:22 Types of Graph :- 8:32 Representation :- 10:15 Graph Problems :- 12:44

[@watchableraven3517]

Pro-tip: if you put the timestamps on the left, they'll line up better.

[@youssefel-mahdy922]

I think it is the best video on KZbin that discuss and give an existing introduction about graph theory. It was my duty to thank you for this video!

[@zamoqi]

4 years into software engineering and had to refresh the knowdlegd on this. SO far the best explanation of such complex and abstract for many topic graphs. A true GEM video. Thanks!

[@AlessandroBottoni]

This is by far the best video regarding graph theory I have seen in my (quite long) life. Extremely clear, extremely accurate and extremely useful. As "Einstein Newton" here said 8 months ago, this can be considered the 3Blue1Brown of Computer Science. Congratulations!

[@truffleshuffle314]

I was about to say that!

[@FunMining]

This is a great channel, definitely will get much more recognitions in the future!

[@vladchira521]

I'm from the future! You were right. Just discovered this channel and I love it.

[@rushianokun]

It's happening

[@omaryahia]

I agree :)

[@PhysicsMosses]

I am from far future

[@gytzero]

Just found this, from the farer future

[@symonzhu9153]

wow never would've thought about sudoku like this - that's awesome!

[@KoraxLP]

Your videos are absolutely amazing ! Especially your recursion video helped me immensely. Looking forward to more of your work. Keep going, this channel is going to be big! The video quality is just soo goood.

[@Reducible]

Thank you! Glad you find these videos helpful and yup I have so many ideas for content so don't plan on stopping any time soon :)

[@L1Q]

thank you SO MUCH for always providing representation of everything in terms of data structures. this is a differences between a topic being complete jargon and an actually making practical sense

[@alonebuthappy33]

This is going to be one of the most popular study channel in the future ♥️

[@Thegamer-kf8zz]

I love the mission of this channel! We need more interesting ways to delve into computer science for people who don’t want to sit down for 2 hours to understand fundamental (often complex) computer science topics!!! KEEP UP THE GOOD WORK!

[@aakdani11]

Dude the way of explained this topic is so amazing and you made it look so easy to understand, It is so hard to understand this topic from books for someone like me. Thanks alot for your help. GOD bless!!

[@adriantee5219]

Beautifully explained and easily understandable to someone who knows little to nothing about graph theory or computer science. Keep up the good work!

[@partimecat]

Thank you for this video, I’ve been having a hard time motivating myself to start studying the graph theory chapter for my discrete math class, and this has helped me to finally open my textbook!

[@markomozina7894]

Another great one. Can’ t wait for more:)

[@milajoy945]

Man!... your animations blow my mind 🤯 brilliantissime!!! Please keep doing them. I spent a moment on YT to find something understandable about graphs... and I found you! Thank you very much 🙏🏻🙏🏻

[@machinimaaquinix3178]

The amount of time and care taken to produce this video shows. This is my first time on this channel and i'm looking forward to going through it more.

[@MrKyltpzyxm]

I like the little bit at the end regarding the path through each vertex only once. Welcome to graph theory 101. After some foundational examples let's jump straight to proving that P=NP. lol

[@thobiaslarsen8336]

Never seen a solution to a sodoku with graph theory! I just learned this to prepare for some competetive programming, I knew it was possible to solve using some disgusting nested for loops, but never knew graph would be a solution. Thank you!

[@trumanh1453]

Explain theories with clear diagrams and clear pronunciation. Great !

[@antontsvil245]

Im just can't thank you enough, this video was so enlightening that actually gives me a hope, it proves that I am able to learn and understand hard concept w/o expensive education. Eventually I would become a programmer. Thank you from the bottom of my heart

[@hasanrants]

hats off, the production quality is mind boggling.

[@fatimameryam6215]

Brilliant elegant explanation, wow. Thank you one thousand times !

[@daniahmed]

This was your first video that i saw amd let me say I'll always come here whenever there'll be a new math concept in CS that i want to understand. Cheers👍

[@aramwis]

I'm so happy I got here. I'm a completely new to all of this yet I cam out understanding every single thing you just said. That was amazing. Thsnk you so much

[@rmt3589]

This is amazing! Reminded me of Vector Art, Wave Function Collapse, and Neuronets a lot. I have learned a lot, and deffinately want to learn way more!

[@hiryu87]

Superb breakdown of the subject. Had no idea before the video and now I really understand if fundamentally.

[@shubhkhandelwal4822]

Thank you for existing!

[@Kyle-xk2rb]

As a CS student this is really good content. Love all the videos you make!

[@sooniesleardamer3871]

Keep on going! Your channel is just amazing! (Watching from France)

[@rangbuzz]

Brilliantly explained the concept of graph theory. Thank you.

[@LowLevelLemmy]

Just discovered your channel. I'm about to binge everything you've made.

[@ankitshaw6307]

Amazing Explanation !! You explained such a complex topic in so easy to understand language. I learnt a lot today and also found out interesting ways to visualize a graph. Thank you !!!

[@bradleyli1569]

Awesome video! Can't wait to see more videos like this being posted!

[@sliddjur]

As a network engineer, this is really interesting! I visualize my networks with python and networkx and dot-graphs. Really fun!

[@robertcormia7970]

This was GREAT! I'm boning up on graph theory for cheminformatics, and this is providing a great foundation!

[@shreyageek]

What a clean video anyone can understand from images itself Thanks a lot for this

[@wittyhumour29]

Great Introduction to Graph Theory. Amazing Explanation.

[@mdegaris1972]

Beautifully explained. Thank you!

[@SebastianLopez-nh1rr]

I came here because of 3B1B, please keep up the good work. You've got great potential.

[@NaveenKumar-os8dv]

If everyone was like you, study wouldn't not be tough. Thank you for this video and graph theory explanation. What you made is not just knowledge, but enlightment for me. You do it like its a cake to you, and I actually understand your explanation.

[@reubenvandermerwe480]

Great video. Simple and easy to understand, and yet it gives a great overview of graph theory concepts.

[@MythicalMaestro69]

Imagine Every Single Teacher in The World Teach Like HIM!! I mean there is no Teacher in my College who teach like him. His Explanations are clear and the way he presents his presentation is easy to understand and not boring to watch.

[@m322_yt]

well, I presume no teacher has a couple of weeks/months time to prepare a single lecture that introduces basic concepts

[@jimboli9400]

Please keep up these sensational videos, incredible amount of work and effort gone into these!

[@zuhail1519]

Absolutely smooth!

[@aureacastillo172]

I think I'm in love, thank you for the video!

[@azatecas]

Why didnt i find this channel sooner? Love this

[@bish-jyag3371]

Very nicely presented, clear and concise. You are the great teacher.

[@kingdel0xe]

There is a small mistake at 4:15 You would need to connect every point on a column with every other point on the same column same for the rows. Otherwise a graph coloring algorithm wouldn't work here, since graph coloring algorithms only test for the constraint that each neightbor has a different color.

[@ahmedtawfiq3625]

I will sit and watch all your videos one by one

[@goober3666]

this video is oddly beautiful, i absolutely despised this whole semester of discrete math but you kinda got me invested

[@ahmedtawfiq3625]

Your videos are so well explained. Wish i had a teacher like you from high school...

[@astroceleste292]

Thank you for putting subtitles

[@GEMINDIGO]

A very interesting video that explains the concepts well. Very inspiring.

[@bikramm5553]

Wow!! Amazing Video. One the best video, I have ever seen.

[@MangoLassiYT]

this video was better than most videos on youtube related to graphs

[@andy-kg5fb]

I love this style of video.

[@guysolo6542]

very good video, thank you so much, keep up the good work, watching 2 days before an exam

[@xxmiamygirlxx]

very nice, thanks for the vizualisation and soothing music

[@nosult3220]

Taking this as a grad level course rn. Its very stimulating for visual learners

[@zaidmermam2524]

absolutely amazing explanation!

[@raunakmitra7868]

The Sudoku example is outstanding and useful.

[@filiprank9870]

Amazing! Thank you!

[@saipan1970]

Fantastic, just needed info for programming.Thank you.

[@jzhuo1731]

Awesome video. Thank you!

[@williammasferrer9067]

Great video !!! It Accomplish his goal of giving an introduction on the topic.

[@chandraprakash934]

Simply awesome ! keep the good work going 👍

[@nothingnoone8752]

Wow, so glad I found this channel. Subbed.

[@Syph_Silver]

thank you very much for this explanation !

[@maxpalm7862]

Thank you very much, that was a great introduction. Much appreciated

[@victorveloso226]

Great Video!! Thank you!

[@technics6215]

Thank you, nice introduction!

[@YiannosG]

Excellent video and narration

[@CipherOne]

Outstanding presentation.

[@divakarbhardwaj7322]

Absolutely amazing content.

[@sherlock_221]

The sudoku Example was the best! Please make more videos on graph theory

[@kuijaye]

Nice introduction. Now I understand why git commits are directed acyclic graphs. Thanks man!

[@lk9895]

Explained very properly!

[@EW-mb1ih]

This is a masterpiece

[@alfcnz]

Thanks! This was great!

[@channagirijagadish1201]

Excellent Channel and very informative with rigor.

[@haleynaga5671]

i cant read my college material for this particualr topic and found your videos, ist really great!!

[@amitadhikaree1801]

Keep on going! Your are doing an amazing work!!

[@judyju7416]

Amazing video !!! Thank you !!!

[@kasyapdharanikota8570]

great channel ,please continue making such great videos .

[@adamtaylor2142]

Excellent video!

[@ryanmckenna2047]

Very nicely introduced, I hope you have some very complex cutting edge applications of graph theory to show off :)

[@shashankkaryakarte8463]

best video for introduction to graphs....

[@MCLooyverse]

I spent a few hours building a Graph data type in Haskell (and I do not remember why), and how I did it was as a (cyclic) list of pairs, where the first entry is the node value, and the second is a list of offsets of the node's neighbors. For example, it would represent the graph at 12:38 as [(0, [1,2,3]), (1, [4, 2]), (2, [3, 1]), (3, [2, 3, 4, 1]), (4, [4])]

[@izzylapidus]

This was super helpful thank you!!!!!

[@basitshabbir1100]

Thank you so much for the video, please make a whole playlist of videos on the graph theory course that they teach in Universities

[@kevg3563]

Very well explained. Subscribed!

[@AJ-et3vf]

Great video. Thank you

[@neeljoymukherjee9087]

nice explanation. Thank you very much.

[@haktwld]

Just found you channel through this video. Great presentation.

[@erv993]

Great video! thanks so much!

[@nachosncheez2492]

nice channel i just found it today, i like the concise summary's of topics

[@shirinnurlyyeva508]

Very neaaaaat explanation man, thank you soooo much!

[@AnasMations]

Thank you so much! This was very helpful.