What is a Clique? | Graph Theory, Cliques

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

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

50% 1

What is a clique? A clique in graph theory is an interesting concept with a lot of depth to explore. We define the term and give some examples in today's math video lesson!
A clique C of a graph G is usually defined as a subset of the vertex set of G such that every pair of distinct vertices in C is adjacent in G. In other words, a subset of the vertex set of G is a clique if and only if its induced subgraph is a complete graph. Watch the full video lesson to learn more and see some examples!
In future lessons we will explore maximal cliques and how to find them!
Other network stuff...
Lesson on k-cliques: • What are k-Cliques? | ...
Lesson on k-cores: • What is the K-Core of ...
Lesson on k-clans and k-clubs: • What are k-Clans and k...
I hope you find this video helpful, and be sure to ask any questions down in the comments!
◉Textbooks I Like◉
Graph Theory: amzn.to/3JHQtZj
Real Analysis: amzn.to/3CMdgjI
Proofs and Set Theory: amzn.to/367VBXP (available for free online)
Statistics: amzn.to/3tsaEER
Abstract Algebra: amzn.to/3IjoZaO
Discrete Math: amzn.to/3qfhoUn
Number Theory: amzn.to/3JqpOQd
The song I play at the end is "Back Then" by B STORY.
◆ Donate on PayPal: www.paypal.me/wrathofmath
◆ Support Wrath of Math on Patreon: / wrathofmathlessons
+WRATH OF MATH+
◆ Support Wrath of Math on Patreon: / wrathofmathlessons
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / seanemusic

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

24 июл 2024

Ссылка:

Скачать:

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

Добавить в:

Мой плейлист

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

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

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

Check out the full Graph Theory playlist with over 130 videos and counting! ru-vid.com/group/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

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

Thank you for making this! Its much easier to understand once its visualized like this

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

So glad it helped! Let me know if you ever have any questions and thanks for watching!

@whitec2482 5 лет назад

Thanks for your explanation. It’s very helpful. Looking forward to the following videos about this topic.

@WrathofMath 5 лет назад

Thanks for watching, I am glad it helped! Sorry it took so long to start getting to this, it has been a gnarly couple of weeks for me, but production will be ramping up!

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

This is so good! Could you explain how to reduce CNFSAT to clique and vise versa? Thank you so much.

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

Wow! Well-explained ❤ thanks so much

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

Super clear, easy to understand. Cheers!

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

Thank you, I'm glad to hear it!

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

Thanks a lot. Quick and straight forward explanation. Got it right away.

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

Glad to hear! You're welcome and thanks for watching!

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

absolutely perfect, keep going !!

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

Thank you! I'm making as many lessons as I possibly can! Let me know if you have any requests!

@muhammedusman7269 6 месяцев назад

Best video on clique. Thanks

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

Great video, super helpful!

@PunmasterSTP Месяц назад

Wow, your videos really help things to...sink in! 👍

@SubhashreeSahoo-mx4wl 4 месяца назад

Thank you so much sir for your clearly clarification!

@user-qb3mn4ur5j Год назад

Thank you for making this clear

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

I will report about this in my masteral class. You just saved my life ❤

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

So glad it helped, thanks a lot for watching!

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

You are my graph guru🙏

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

good, clear explanation.

@anandpk001 5 месяцев назад

loved this class

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

Very good explanatory video

@swaggysack 8 месяцев назад

excellent explanation, i really appreciate you breaking down each piece of logic as the notation can get confusing at times :)

@WrathofMath 8 месяцев назад

Glad it was helpful!

@bytecode5834 6 месяцев назад

Thanks for the gift Sean

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

Good stuff bro, much better explanation here than the sliders the teacher gave us.

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

Thank you for watching and for your kind words! I am glad it helped. Let me know if you ever have any video requests!

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

Thanks for the clear explanations!

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

You're very welcome! Thanks for watching!

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

This is very easy to comprehend. Thanks a lot!

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

You're welcome, I am glad it helped! Check out my Graph Theory playlist if you're looking for more: ru-vid.com/group/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

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

nice explanation 👍

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

explained everything well & thorough !

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

Thank you, I am glad it was clear and thanks for watching!

@justinmorgan7495 5 лет назад

You're a good lessoning teaching guy. Lol, great explanation !

@WrathofMath 5 лет назад

Thank you! Let me know if you ever have any video requests and I'll do my best to make another good lesson on it!

@ItsEvanWilson 5 лет назад

Fantastic Video, keep up the great content. You're helping myself as a college student understand the material! I'm new to the subject

@WrathofMath 5 лет назад

Thanks a lot! Good luck in college, and let me know if you ever have any video requests! I'm happy to help when needed!

@ItsEvanWilson 5 лет назад

Wrath of Math Ayeee thank you so much!! And I will do!! Thx!

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

thank you so much for this! this saved me a lot of time

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

So glad to hear it! Thanks for watching! Be sure to check out my Graph Theory playlist if you're looking for more graph theory lessons, many more to come! ru-vid.com/group/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

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

Very Clear. thanks.

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

Glad to hear it, thanks for watching and check out my graph theory playlist for more! ru-vid.com/group/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

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

You da Graph Theory master in RU-vid

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

Clear and precise. Thanks from 🇮🇳

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

I'm glad you found it clear and thanks for watching! It's great to be able to reach people all over the world, and many from India!

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

Can you please tell me how to find strong metric dimension?

@vector8310 Год назад

Pleasant, perfect exposition.

@WrathofMath Год назад

Thank you!

4 года назад

Your video helped me a lot, thanks !

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

Glad to hear it! Thanks for watching, Pablo!

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

Clear, cogent, limpid all the pretty adjectives you deserve for this video. Thank you.

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

That's very high praise! Thanks a lot for watching and for your kind words, I am glad the lesson was helpful!

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

very helpful, thanks!

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

You're welcome - thanks for watching! If you're looking for more graph theory, check out my playlist! ru-vid.com/group/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

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

The best explanation out there 💕

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

Thank you, that's what I strive for!

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

the guitar part was nice thank you for making me exam night alittle better ❤❤❤❤

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

Thank you! Good luck on the exam/I hope it went well!

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

Any other similar algorithm or efficient algorithm than clique partition algorithm...?

@wishmanoor-fo7rp 8 месяцев назад

Thank you Your way of explaining is mind blowing

@WrathofMath 8 месяцев назад

Thanks and welcome!

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

Amazing , i loved it. Thanks a lot sir

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

My pleasure, thanks for watching!

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

Omg this was so clear thanks much

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

My pleasure, thanks for watching and let me know if you ever have any questions!

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

Good job, way to go. Thanks.

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

You're welcome, and thanks for watching!

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

I need this teacher in my engineering college best teacher I have ever seen 🙏😭❤️❤️❤️❤️❤️❤️❤️. His teachings skills are god level. ❤️❤️❤️❤️ Love from India ❤️🙌.

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

Thanks so much! Glad it helped!

@karinablanchard9511 Год назад

Thank you :)

@user-uy1sl4sk3f 3 месяца назад

Thanks!

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

Thank u so much 4 ur explanation 😍it helps me lot

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

So glad it helped, you're welcome and thanks for watching!

@letsLearnTogether121 28 дней назад

Have you worked on spectral graph theory also?

@cryonim Год назад

Haha a custom guitar played outro is pretty cool!

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

Please explain the difference between clique and pathwidth

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

Thanks a lot Sir 👍 for awesome Explanation 👌

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

My pleasure, thanks for watching! Check out my Graph Theory playlist for more! ru-vid.com/group/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

@sunnygudazi9486 Год назад

please explain what clique separable graphs are

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

Please do a video of inverse domination graph

@taljune142010 Год назад

Thanks a lot!

@WrathofMath Год назад

Glad to help, thanks for watching!

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

I like the idea of song at the end,

@ikechukwumichael1383 День назад

Excellent

@saptarshichattopadhyay8234 Год назад

Thank you so much ❤❤❤❤❤

@WrathofMath Год назад

My pleasure - thanks for watching!

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

perfect!

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

This I got while searching for clique complexes,although it's little bit different but it helps me to understand what a clique is.. Thank you so much. Can you please make a video for clique complexes as well?

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

Thanks for watching, and for the question! I am not familiar with clique complexes so don't expect a lesson soon, but I will study them and may do a lesson on them in the future, thanks for the request!

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

@@WrathofMath also if possible a video on comparability graph too.

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

Im really thankful to u 🙏🤜

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

I'm glad to help! Thanks for watching, and check out my Graph Theory playlist if you're looking for more: ru-vid.com/group/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

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

Really amazing I got a clear picture about clique ❤️

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

Glad to hear it, thanks for watching! If you're looking for more graph theory, check out my graph theory playlist! ru-vid.com/group/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

@Nursin-rg1ey 2 года назад

Thanks sir 🙏🏻

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

You're very welcome - thanks for watching! If you're looking for more graph theory, check out my playlist! ru-vid.com/group/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

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

If I want to count how many cliques are in a graph, do I count subcliques as well? For example the graph in your example had cliques {a, b, c, f} with subcliques such as: {a, b, c}, {a, b, f}, {a, c, f}, {b, c, f}. Does the graph than contain 1 clique (because all the other cliques are sub cliques) or does it contain 5 and we just count all of them, no matter if they are sub-cliques or not?

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

Thanks for watching and good question! If you're asked to count the cliques, I'd say it's a pretty ambiguous question. If I was asked to simply "count the cliques" I'd count all cliques, since the question doesn't specify, and so we'd have 5 nonempty cliques. But it'd make more sense to count maximal cliques, only those that aren't subsets of larger cliques.

@bhavyaanbarasan7919 5 лет назад

Hello sir , I need a video on decomposition of graph. Can you please do it?? And give me some ideas to do Ph.D in this field

@WrathofMath 5 лет назад

Hello and thanks for watching! I will do a video on decomposition of graphs as soon as I can! Got a few other requests to knock out first and I'll try to make a good lesson on it for you! Do you mean ideas for what field of math specifically to get a Ph.D in? Or do you mean ideas for a dissertation during your Ph.D? Either way I don't think I'm the best person to ask because I have not pursued a Ph.D, so I wouldn't be able to give you any advice or suggestions from first hand experience. If you are in the middle of getting a bachelor's degree, or have one, or plan on pursuing one, I'd ask your math professors more about this, as most of them probably went through a similar path to what you're considering. Good luck!

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

TY , really usefull .!

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

Glad to hear it! You're welcome and thanks for watching!

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

Superb! Thanks

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

Glad it helped and thanks for watching!

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

Thanks man

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

No problem, thanks for watching! If you're looking for more graph theory, check out my playlist: ru-vid.com/group/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH Let me know if you ever have any questions!

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

Sir Do you have any video on Vertex transitive graph ?

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

Thanks for watching and I do not at the moment, but I will add it to my list and try to do it soon!

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

@@WrathofMath Thank you sir. I've been searching for it since yesterday, but I can't find anything from Google or RU-vid, I didn't find anything that was easy to understand.

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

Perfect. Can you tell me which software you are using for the board?

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

Thank you! These lessons are recorded on the app Notability on iPad Pro!

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

Fantastic explanation sir

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

I am glad it was clear, thanks for watching!

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

Great Video!

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

Thank you! And thanks a lot for watching, I am glad it helped!

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

Amazing 👌...

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

Thank you for watching!

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

so is a,c,f also a clique in this graph?

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

thank you

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

Thank you! 😊

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

Hello sir, Thanks for your explanation. It’s very helpful. I need a video on Covering and Matching of Independent sets in graph theory. Can you please do it??

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

I'm glad it helped and thanks for watching! Is this what you're looking for? ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-chdr2aj4FUc.html

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

@@WrathofMath thank you so much sir. This is exactly what I was looking for.

@parisshopping-zg3ts 4 месяца назад

You are the best

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

Thank you!

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

Confused. When you say set of vertices, does a clique need to have a minimum number of pairs of vertices? Or any two adgacent vertices make a clique, since they are a subset of vertices, they are adjacent and they are not the same vertice.

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

A clique does not need to have a minimum number of vertices. So indeed, any two adjacent vertices make up a clique, because their induced subgraph is complete. Additionally, every single vertex also is a clique, because its induced subgraph is K1, another complete graph. Thanks for watching and I hope that clears it up!

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

Amazing video, can you explain n-clan and n-club?

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

Thanks for watching and for the request! It's a little late, but here it is! ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-LqPHg9uNp-o.html

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

is {b,c,d,e,f,a} is a clique in this graph?

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

Does {b,d,e} FORM A CLIQUE?

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

What is the Largest Clique of an undirected graph? Please explains in details............................

@lloydlobo3174 5 лет назад

Hi could you do a video explaining K-cores in graph theory

@WrathofMath 5 лет назад

Absolutely, thanks for watching and for the request and sorry for the late reply!

@WrathofMath 5 лет назад

Sorry for the long wait, thanks for the request! :) Here is the lesson! ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-rHVrgbc_3JA.html

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

Can i know the name of the software you are using as a board? Its really good

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

It's a great software, Notability on an iPad Pro. I only use it for lessons, I have other apps I prefer for taking notes, but Notability is a really good option for notes too!

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

How about if we have 2 vertices? example, C={b, c}. Can we consider it a clique?

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

Thanks for watching and just consider the definition of clique. Suppose we have a set C = { a, b } of 2 adjacent vertices. Does C satisfy the definition that each pair of distinct vertices from C is joined by an edge?

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

@@WrathofMath Yes. Thank you. Can you also discuss Clique Graph. Thanks and More subscribers to come!

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

#Excelent!

@yash.dwivedi 3 года назад

thanks

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

No problem - thanks for watching!

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

Good job

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

Thank you for watching!

@3SuriuPica 4 года назад

What is the least number of vertices in a clique?

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

Man what a heck are you talking about? You turned something so simple into quantum physics.

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

Sorry it wasn't clear, do you have any questions I can help clear up?

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

@@WrathofMath Yes in story writing how do I create a good clique?

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

But can we say that {b, c, f}, {a,b,c}, {a,c,f}, are also clicks? of they must be taken as max adjacent set?

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

Thanks for watching and yes, those are cliques, I believe I mention {b, c, f} is a clique. However, under some definitions they may not be. Some definitions require cliques to be maximal, some don't, so you simply need to be aware what definition is being used - or what definition best suits your purpose. If you're writing a paper only concerned with maximal cliques, for example, it would make sense to make maximality part of the definition for convenience.

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

@@WrathofMath Thank you very much.

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

please do a video on independent set of a graph

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

Good idea! Thanks for watching and for the request, I will try to fulfill it as soon as I can! Unfortunately I am sick at the moment, and cannot record lessons. But I expect to be better by next week, and will be right back to uploading new lessons every other day!

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

Here is the lesson on independent sets in graph theory! ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-0stavxEccvE.html Thanks for the request, and let me know of any more specifics on the topic you'd like videos on, I do already have some more lessons planned on this topic!

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

Can you do a video on the basics of Ramsey theory ?plzz

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

@@vijayalekshmi4604 Please post video requests as their own comments rather than replies to other comments, just because RU-vid usually doesn't notify me when people reply to comments so I often miss them! Thanks for watching and for your request, I'd love to fulfill it but I am not well read in Ramsey Theory, so I'd be hesitant to do a lesson on it. I can't say I'll have time to dig into it anytime soon, as I am currently studying financial mathematics primarily, but I regularly study different areas, and will definitely keep your request in mind going forward. I look forward to learning more about Ramsey Theory as well!

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

So a clique is a subset within the graph , and that subset must be a complete graph (K) or in other words , small complete graphs inside the main graph right?..

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

Thanks for watching and that's right! And remember we'll often find it convenient to consider the vertices in the complete subgraph as the clique as well. So the clique may the complete subgraph or the vertices within it.

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

what is pathwidth?

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

I literally thought this was a video about social cliqusz

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

Hi. Would you please make a video on chromatic polynomials! Thank you.😇

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

Thanks for watching and the request! I have wanted to do this topic for a while, it's very fascinating. Not sure when I'll get to it though. I want to make sure my explanations do it justice!

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

@@WrathofMath Thank you!😇

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

Are all subsets of a clique also cliques themselves?

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

Thanks for watching and I will answer with a question. A clique is a set of vertices that are all adjacent to each other. So, if we consider a subset of a clique, must those vertices in the subset all be adjacent to each other?

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

@@WrathofMath Yes, they will have to be adjacent to each other so a subset should also be a clique I think.

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

Precisely!

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

❤️

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

Thanks for watching! Check out my graph theory playlist for more and let me know if you have any questions! ru-vid.com/group/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

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

Please explain Ramsey numbers

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

Thanks for watching, I will definitely get to Ramsey numbers sometime. Hopefully sometime this year, they're really cool!

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

@@WrathofMath I’m searching all over the internet but I didn’t see any convincing details on Ramsey numbers yet!! And I really need to understand 🙄🥺 how do we find the exact solution R(3,3)=6, R(4,4)=18 and even big numbers!! How can I get to know the exact value!! 😶

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

By "exact solution" do you mean how to prove the equalities you listed? As for bigger numbers, we don't know the other Ramsey numbers like R(5,5), R(6,6) and so on.

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

@@WrathofMath I mean how do we know that R(3,3)=6, R(5,5)= 45 etc etc? Is there any way to find out?