Maximum and Maximal Cliques | Graph Theory, Clique Number
Вставка
- Опубліковано 12 вер 2024
- What are maximum cliques and maximal cliques in graph theory? We'll be defining both terms in today's video graph theory lesson, as well as going over an example of finding maximal and maximum cliques in a graph. These two terms can be a little confusing, so let's dig in and clarify our understanding!
A maximal clique in a graph G is a clique that is not a proper subset of another clique in G. Hence, a maximal clique cannot be extended by including another vertex of the graph along with the appropriate edges.
A maximum clique in a graph G is a clique with as many or more vertices than any other clique in G. It is a clique such that no other clique in the graph has more vertices.
Every maximum clique is, by definition maximal, but not every maximal clique is maximum. We will see an example in this video of a maximal clique that is not a maximum clique.
SOLUTION TO PRACTICE PROBLEM ( • What are the Maximum a... ):
This is a bit of a devious problem. Easier part first, there are several maximum cliques. The vertices b, c, d, and e almost look like they make up a 4-clique, but they do not. For example, b and d are not adjacent. The largest cliques in this graph have 3 vertices. An example of one would be a, b, and e. Or b, c, and f.
There are many non-maximal cliques in the graph. By definition, all vertices with degree greater than 0 are non-maximal cliques (if their degree is zero, they are maximal as no other vertex can be included to extend the clique). In this graph every vertex is a non-maximal clique. Additionally, every edge that is part of a K_3 subgraph (a complete subgraph on 3 vertices) is a non-maximal clique. In this graph, every edge is part of a K_3 subgraph, so every edge, with its 2 incident vertices, is another non-maximal clique.
Since we know there is no clique with more than 3 vertices, we know every clique with 3 vertices must be maximal (otherwise they could be extended to a clique with 4 vertices - a contradiction). Hence, we have found all non-maximal cliques, since all cliques yet to be considered have 3 vertices and are maximal.
If you're taking a course in Graph Theory, or preparing to, you may be interested in the textbook that introduced me to Graph Theory: “A First Course in Graph Theory“ by Gary Chartrand and Ping Zhang. It’s a wonderful text! You can purchase this book through my Amazon affiliate link below! Using the affiliate link costs you nothing extra, and helps me continue to work on Wrath of Math!
PURCHASE "A First Course in Graph Theory": amzn.to/31hgvvJ
I hope you find this video helpful, and be sure to ask any questions down in the comments!
+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
Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions!
ua-cam.com/channels/yEKvaxi8mt9FMc62MHcliw.htmljoin
Graph Theory course: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Graph Theory exercises: ua-cam.com/play/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L.html
Thanks for helping all the information to clique! 😎
so lucidly explained. thanks a ton cleared my doubts
So glad it helped, thanks for watching!
I have seen a couple of research paper that are using graph theory to estimate room geometry. Would you be interested in reviewing these papers? It will be a good complement to your graph theory series. Thanks for the lesson!
Thank you very much! Now I understand why I did wrong in my assignment!
Glad to help - thanks for watching!
Out of curiosity, how'd the rest of your class go?
God understanding clear all confusions thanks for this
I am glad it helped, thanks for watching!
so, a complete graph is maximum as well as maximal clique of itself??
Thanks for watching and good observation, you're correct! Not only is an entire complete graph a maximal clique of itself, but it is the only maximal clique of itself!
This helped me 9:26 mins right B4 the exam 😂😂
Awesome! How'd the rest of the exam (and class) go?
What is the Largest Clique of an undirected graph?
Use 9-10 vertices of an undirected graph.
Please explain in details....................
Any Complete Graph With 10 vertices is the largest clique Maximal = Maximum Clique Also
Can you please share link of video on type of coloring, fractional coloring,harmonious coloring....
Great work
Thank you! If you're looking for more graph theory, check out my graph theory playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Could you please make a video on solution for non maximal clique? Because I didn't get the solution you have written in description box.
Thanks for watching, and sure thing! I think it can be a bit tricky to explain in plain text, so I'll whip up a lesson on it! Thanks for the request!
ua-cam.com/video/WTzpaSxHAys/v-deo.html
Which device do you use to make these videos?
Thanks a lot for watching! These videos are screen recordings of an application called Notability running on an iPad Pro, and I am writing with an Apple Pencil.
"A maximal clique in a graph G is a clique that is not a proper subset of another clique in G." For completeness, it would be useful if you clarify what a "proper subset" is. Is a "proper subset" different from a "subset"? Is there such a thing as an "improper subset"?
A proper subset does not have all the members of its superset
@@robertleo3561 Thanks Robert. But this does not answer my two questions:
Is a "proper subset" different from a "subset"? Is there such a thing as an "improper subset"?
@@martinroa Not really, but if a set B is a subset of set A, the only way for it not to be a proper subset of A is when A = B. So in that case, you could call B an improper subset of A. But that terminology is not really used, we simply say "proper subset" when we want to convey that B must be a subset of A, while not equaling A.
@@robertleo3561 I understand now. Thank you very much.
non-maximal Cliquen sind { [e,b,c] , [b,c,d] , [c,d,e ] ,[e,b,d] ,[e,b,c] , [e,b ,a ] , [f,b,c] , [f,d,c] [f,be] , [f,d,e]}
the background is disturbing beacause try to understand for my exam it sound like a holiday sound
It made me get the sense that I was studying math in an elevator, which for me, wasn't necessarily bad...