Independent Vertex Sets and Independence Numbers | Graph Theory
49.7 هزار بار بازدید -
5 سال پیش
-
What are independent vertex sets
What are independent vertex sets in graph theory? We'll go over independent sets, their definition and examples, and some related concepts like the vertex independence number of a graph in today's video graph theory lesson!
A subset of the vertex set of a graph is an independent vertex set if and only if it contains no pair of adjacent vertices. It's like a partite set of a bipartite graph!
If an independent set cannot be made bigger by adding another vertex from the graph, while preserving its independence, then it is called a maximal independent set.
If an independent set is of the greatest cardinality possible for any independent set of its graph, then it is a maximum independent set. Maximum independent sets are not unique. The cardinality of a graphs's maximum independent sets is called the graph's independence number, or vertex independence number.
SOLUTION TO PRACTICE PROBLEM:
The independence number of the graph is 3. The set { b, d, f } is a maximum independent set of this graph. So is the set { c, e, g }.
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 support Wrath of Math!
PURCHASE "A First Course in Graph Theory": https://amzn.to/31hgvvJ
I hope you find this video helpful, and be sure to ask any questions down in the comments!
********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.
Vallow Bandcamp: https://vallow.bandcamp.com/
Vallow Spotify: https://open.spotify.com/artist/0fRtu...
Vallow SoundCloud: SoundCloud: benwatts-3
********************************************************************
+WRATH OF MATH+
◆ Support Wrath of Math on Patreon: Patreon: wrathofmathlessons
Follow Wrath of Math on...
● Instagram: Instagram: wrathofmathedu
● Facebook: Facebook: WrathofMath
● Twitter: Twitter: wrathofmathedu
My Music Channel: seanemusic
A subset of the vertex set of a graph is an independent vertex set if and only if it contains no pair of adjacent vertices. It's like a partite set of a bipartite graph!
If an independent set cannot be made bigger by adding another vertex from the graph, while preserving its independence, then it is called a maximal independent set.
If an independent set is of the greatest cardinality possible for any independent set of its graph, then it is a maximum independent set. Maximum independent sets are not unique. The cardinality of a graphs's maximum independent sets is called the graph's independence number, or vertex independence number.
SOLUTION TO PRACTICE PROBLEM:
The independence number of the graph is 3. The set { b, d, f } is a maximum independent set of this graph. So is the set { c, e, g }.
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 support Wrath of Math!
PURCHASE "A First Course in Graph Theory": https://amzn.to/31hgvvJ
I hope you find this video helpful, and be sure to ask any questions down in the comments!
********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.
Vallow Bandcamp: https://vallow.bandcamp.com/
Vallow Spotify: https://open.spotify.com/artist/0fRtu...
Vallow SoundCloud: SoundCloud: benwatts-3
********************************************************************
+WRATH OF MATH+
◆ Support Wrath of Math on Patreon: Patreon: wrathofmathlessons
Follow Wrath of Math on...
● Instagram: Instagram: wrathofmathedu
● Facebook: Facebook: WrathofMath
● Twitter: Twitter: wrathofmathedu
My Music Channel: seanemusic
5 سال پیش
در تاریخ 1398/07/14 منتشر شده
است.
49,760
بـار بازدید شده