What are Graph Decompositions? | Graph Decomposition, Graph Theory

Описание: Support the production of this course by joining Wrath of Math to access all my graph theory videos!
   / @wrathofmath  
🛍 Check out the coolest math clothes in the world: https://mathshion.com/

Graph Theory course:    • Graph Theory  
Graph Theory exercises:    • Graph Theory Exercises  

Get the textbook! https://amzn.to/3HvI535

What is a graph decomposition? Graph decompositions are studied quite extensively by many in graph theory, and we’ll go over what they are, and plenty of examples in today’s video graph theory lesson!

PRACTICE EXERCISE:

There are many ways we could decompose this graph. For a cycle decomposition I decomposed the graph so that the edges fa, ab, bg, and gf make up one subgraph, the edges bf, fe, ed, dc, and cb make up another subgraph, and the edges, eh, hc, and ce make up another subgraph!

For a path decomposition, I decomposed the graph so that the edges fa, ab, bc, cd, de, and eh make up one subgraph, the edges fg and gb make up another subgraph, the edges hc and ce make up another subgraph, the edge fe makes up another subgraph, and the edge bf makes up the last subgraph.

When I say the edges make up a subgraph, I of course mean the edges with their incident vertices.

◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu