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! ruclips.net/channel/UCyEKvaxi8mt9FMc62MHcliwjoin Graph Theory course: ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH Graph Theory exercises: ruclips.net/p/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L
Thank you for watching and for your kind words! I always strive to be as clear as I possibly can be in my lessons and to keep them focused enough to deliver clarity in an easy-to-digest video. Let me know if you ever have any video requests!
Great!! i love this video.Thanks!! can you tell something about how to find all the maximal cliques of the chordal graph? how about the Maximum Cardinality Search?thanks again!!
Let Qn be the graph with vertex set f1; 2; :::; ng. Two vertices are adjacent if and only if their greatest common divisor is 1. Give the clique number of Q7 and draw a maximum clique of it. Can you help these question I always miss sth
Thanks for watching and for the question! I'm not sure if I completely understand, I'm just confused by your notation. I am going to assume that the vertices of Q7 are 1, 2, 3, ..., 7, and let me know if I've gone wrong. If that is the vertex set, and vertices are adjacent if and only if their greater common divisor is 1 (as in, they are relatively prime), then we can find the clique number fairly easily. Let me point out just a couple things and see if it helps! We know 1 is relatively prime to every positive integer by definition, since 1 cannot possibly have a common divisor greater than 1 with any number. So 1 will certainly be part of the largest clique. Additionally, all prime numbers are, by definition, relatively prime to each other. They have no common factors other than 1. Thus, we can include all prime number vertices in a clique with 1. This gives us a clique of size 5 with vertices 1, 2, 3, 5, and 7. We cannot include any other vertex in this clique since the other vertices (4 and 6) are not adjacent (relatively prime) to 2. Additionally, 6 is not relatively prime to 3 either. It only remains to prove that we cannot find a larger clique. To do that, I recommend assuming a clique of size at least 6 exists, and showing a contradiction based on the vertices and edges it must contain (as in, it would force two vertices to be adjacent that have a greatest common divisor other than 1, contradicting the definition of this graph). I hope that is some help!
You're welcome! Thank you for watching, and if you're looking for more graph theory, check out my graph theory playlist! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Thanks for watching and good question! If by empty graph you simply mean a graph with no edges, then yes, it has as many cliques as it has vertices because every isolated vertex is a 1-clique.
@@WrathofMath Thank you for your answer. Suppose we have a graph G which is the union of two isolated vertices and multiple copies of path of length 2, then the clique number is equal two 4, right? One more question regarding planar graph. (a) Is empty graph a planar graph? (b) Suppose we have a graph G which is the union of two isolated vertices and multiple copies of path of length 2. Is G a planar graph?
![[Limbus Company - PV] Chapter.7 - Oblivion](http://i.ytimg.com/vi/VUpkXPkvoxU/mqdefault.jpg)
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!
ruclips.net/channel/UCyEKvaxi8mt9FMc62MHcliwjoin
Graph Theory course: ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Graph Theory exercises: ruclips.net/p/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L
Sir, This video is awesome. You explained everything clearly..
Thank you, I do my best! Glad to see you here again! Thanks for your continued support and as always, let me know if you have any requests!
@@WrathofMath Sure sir.. you are a nice teacher.
I do love your quick and core spot video. Clear, effective and efficient.
Thank you for watching and for your kind words! I always strive to be as clear as I possibly can be in my lessons and to keep them focused enough to deliver clarity in an easy-to-digest video. Let me know if you ever have any video requests!
@@WrathofMath Thank you very much! ^__^
Excellent explanation with a clear voice. Thank you very much.
Glad to help, thanks for watching!
A video about chordal graphs and graph triangulation would be much appreciated.
Maximal clique? More like "Magnificent videos that are slick!" 👍
Thank you so much!
Great explaination.
Thank you!
Great as always, thanks for your explanation. Helps me a lot!!
Thank you for watching and for your support, glad it helped!
Clique vs motif please upload video for these two as I am really confuse between these two.
Awesome!!! An amazingly clear explanation!
Thank you for watching, I am glad it helped! Let me know if you ever have any video requests!
Great!! i love this video.Thanks!! can you tell something about how to find all the maximal cliques of the chordal graph? how about the Maximum Cardinality Search?thanks again!!
What a great video, thanks so much
Thank you, glad it helped!
Let Qn be the graph with vertex set f1; 2; :::; ng. Two vertices are adjacent if and
only if their greatest common divisor is 1. Give the clique number of Q7 and draw
a maximum clique of it.
Can you help these question I always miss sth
Thanks for watching and for the question! I'm not sure if I completely understand, I'm just confused by your notation. I am going to assume that the vertices of Q7 are 1, 2, 3, ..., 7, and let me know if I've gone wrong.
If that is the vertex set, and vertices are adjacent if and only if their greater common divisor is 1 (as in, they are relatively prime), then we can find the clique number fairly easily. Let me point out just a couple things and see if it helps! We know 1 is relatively prime to every positive integer by definition, since 1 cannot possibly have a common divisor greater than 1 with any number. So 1 will certainly be part of the largest clique. Additionally, all prime numbers are, by definition, relatively prime to each other. They have no common factors other than 1. Thus, we can include all prime number vertices in a clique with 1. This gives us a clique of size 5 with vertices 1, 2, 3, 5, and 7. We cannot include any other vertex in this clique since the other vertices (4 and 6) are not adjacent (relatively prime) to 2. Additionally, 6 is not relatively prime to 3 either.
It only remains to prove that we cannot find a larger clique. To do that, I recommend assuming a clique of size at least 6 exists, and showing a contradiction based on the vertices and edges it must contain (as in, it would force two vertices to be adjacent that have a greatest common divisor other than 1, contradicting the definition of this graph). I hope that is some help!
sir can you make the video about "clique cover"
thank you very good video
You're welcome! Thank you for watching, and if you're looking for more graph theory, check out my graph theory playlist! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
What if you remove one and add two more
thanks
What is the Largest clique an undirected graph?
Please explain in details............
How is this a NP problem, if it is. is it? idk
how we can find the evaluation function of this problem?!
Does the empty graph have clique?
Thanks for watching and good question! If by empty graph you simply mean a graph with no edges, then yes, it has as many cliques as it has vertices because every isolated vertex is a 1-clique.
@@WrathofMath Thank you for your answer. Suppose we have a graph G which is the union of two isolated vertices and multiple copies of path of length 2, then the clique number is equal two 4, right?
One more question regarding planar graph. (a) Is empty graph a planar graph?
(b) Suppose we have a graph G which is the union of two isolated vertices and multiple copies of path of length 2. Is G a planar graph?
I was studying Relations & Functions.
Awesome! Relations and functions are very interesting and I look forward to doing more lessons on them, functions especially!
@@WrathofMath Thank you sir. :-)
Great.🙏🏻
Thank you!
Muchas gracias mi chingón . No le entiendo nada a Eunice
#Excelent!