How to Tell if Graph is Bipartite (by hand) | Graph Theory
58.3 هزار بار بازدید -
3 سال پیش
-
How can we tell if
How can we tell if a graph is bipartite by hand? We'll discuss the easiest way to identify bipartite graphs in today's graph theory lesson. This method takes advantage of the fact that bipartite graphs are 2-colorable. This means their vertices can be colored using only two colors so adjacent vertices are colored differently (sometimes called a proper coloring). You may easily see that being 2-colorable and bipartite are the exact same things! #GraphTheory
Since a graph being bipartite is the same as being 2-colorable, to determine if a graph is bipartite we simply pick a vertex v to begin coloring - then assign it Color 1. If the graph is bipartite, then the neighbors of v must be colored with Color 2. We continue in this way, coloring neighbors different colors (using only two colors total) until we either finish coloring the graph or we are forced to color two adjacent vertices the same way. If two adjacent vertices are forced to be colored the same way, then the graph cannot possibly be bipartite - since we have been forced to put adjacent vertices in the same set (or color). If we are able to finish coloring the graph - then it is bipartite and we now have a bipartite partitioning of the graph into two colored sets.
Bipartite Graphs: What is a Bipartite Graph? | Graph Th...
Proof Graph with no Odd Cycles is Bipartite: Proof: If a Graph has no Odd Cycles t...
Vertex Colorings and Chromatic Numbers: Vertex Colorings and the Chromatic Nu...
Graph Theory playlist: Graph Theory
★DONATE★
◆ Support Wrath of Math on Patreon for early access to new videos and other exclusive benefits: Patreon: wrathofmathlessons
◆ Donate on PayPal: https://www.paypal.me/wrathofmath
Thanks to Robert Rennie, Barbara Sharrock, and Rolf Waefler for their generous support on Patreon!
Thanks to Crayon Angel, my favorite musician in the world, who upon my request gave me permission to use his music in my math lessons: https://crayonangel.bandcamp.com/
Follow Wrath of Math on...
● Instagram: Instagram: wrathofmathedu
● Facebook: Facebook: WrathofMath
● Twitter: Twitter: wrathofmathedu
My Music Channel: @emery3050
Since a graph being bipartite is the same as being 2-colorable, to determine if a graph is bipartite we simply pick a vertex v to begin coloring - then assign it Color 1. If the graph is bipartite, then the neighbors of v must be colored with Color 2. We continue in this way, coloring neighbors different colors (using only two colors total) until we either finish coloring the graph or we are forced to color two adjacent vertices the same way. If two adjacent vertices are forced to be colored the same way, then the graph cannot possibly be bipartite - since we have been forced to put adjacent vertices in the same set (or color). If we are able to finish coloring the graph - then it is bipartite and we now have a bipartite partitioning of the graph into two colored sets.
Bipartite Graphs: What is a Bipartite Graph? | Graph Th...
Proof Graph with no Odd Cycles is Bipartite: Proof: If a Graph has no Odd Cycles t...
Vertex Colorings and Chromatic Numbers: Vertex Colorings and the Chromatic Nu...
Graph Theory playlist: Graph Theory
★DONATE★
◆ Support Wrath of Math on Patreon for early access to new videos and other exclusive benefits: Patreon: wrathofmathlessons
◆ Donate on PayPal: https://www.paypal.me/wrathofmath
Thanks to Robert Rennie, Barbara Sharrock, and Rolf Waefler for their generous support on Patreon!
Thanks to Crayon Angel, my favorite musician in the world, who upon my request gave me permission to use his music in my math lessons: https://crayonangel.bandcamp.com/
Follow Wrath of Math on...
● Instagram: Instagram: wrathofmathedu
● Facebook: Facebook: WrathofMath
● Twitter: Twitter: wrathofmathedu
My Music Channel: @emery3050
3 سال پیش
در تاریخ 1400/09/17 منتشر شده
است.
58,358
بـار بازدید شده