Graph Theory
59 min 6 Examples
- Introduction to Video: Graphs and Special Graphs
- Determining the type of graph: directed, simple, multigraph, pseudograph (Example #1a-f)
- Identify neighbors, incident edges, degree of vertices (Example #2)
- Overview of the Handshake Theorem
- Use the handshake theorem (Example #3a-b)
- Special Simple Graphs: Walk, Trail, Path, Discrete, Linear, Complete, Cycle, Circuit, Wheel
- Creating subgraphs (Example #4)
- Find the graph union (Example #5)
- What is a bipartite graph? How to determine whether a graph is bipartite?
- Determine whether the graph is bipartite (Example #6a-c)
Isomorphic Graph
1 hr 24 min 15 Examples
- Introduction to Video: Isomorphism and Connectivity
- What is an isomorphism? How do we determine if two graphs are isomorphic?
- Determine if the graphs are isomorphic and verify the one-to-one correspondence (Example #1)
- Determine whether the graphs are isomorphic (Examples #2-7)
- What are cut points and bridges? (Examples #8-9)
- Are the graphs planar? If so, find its planar representation (Examples #10-13)
- What are quotient graphs? Given graph G and relation R find the quotient graph (Example #14)
- Draw the graph and find the equivalence relation then construct the quotient graph (Example #15)
Euler Circuit & Hamiltonian Path
1 hr 7 min 20 Examples
- Introduction to Video: Eulerian and Hamiltonian Graphs
- What are Euler paths and circuits? Understanding the Euler Graph Theorem
- Determine if the graph is an Euler path, circuit, or neither (Examples #1-9)
- Is it possible to walk through each door in a house exactly once? (Example #10)
- Understanding Fleury’s Algorithm
- Understanding Hamilton paths and circuits (Examples #11-16)
- Overview of the shortest path algorithm and weighted graphs
- Find the shortest path (Examples #17-19)
- Solve the TSP by finding all Hamilton circuits and finding minimum total cost (Example #20)
Tree Graph
50 min 12 Examples
- Introduction to Video: Trees
- What is a Tree? Forest? Rooted Tree?
- Which of the graphs are trees? (Examples #1-6)
- Given the rooted tree find the following (Example #7a-i)
- What is an m-ary tree? What is the height of a tree? Properties and Formulas for trees
- Find the number of edges and vertices of a tree (Examples #8-9)
- Determine the number of edges and leaves given internal vertices (Examples #10-11)
- Identify how many people receive a chain letter and how many do not sent it out (Example #12)
Spanning Tree
1 hr 9 Examples
- Introduction to Video: Spanning Trees and Minimum Spanning Trees
- What is a spanning tree? How do we produce spanning trees? (Examples #1-2)
- What is a minimum spanning tree? Understanding Prim’s Algorithm
- Use Prim’s Algorithm to find a MST (Examples #3-6)
- What is Kruskal’s Algorithm? What is a Greedy Algorithm?
- Use Kruskal’s Algorithm to find a MST (Examples #7-9)
Planar Graph
1hr 5min 13 Examples
- Introduction to Video: Planar Graphs
- Overview of planar graphs and plane graphs
- Draw the graph without edge crossings (Examples #1-3)
- Identify the regions and boundaries of the planar graph (Examples #4-6)
- Overview of Euler’s Formula
- Use Euler’s Formula determine the number of regions (Examples #7-8)
- Corollaries to Euler’s Formula and overview of Euler’s Polyhedron formula
- Overview of Kuratowski’s Theorem and Homeomorphism
- Demonstrate Kuratowski’s theorem in the Petersen graph
- Determine whether the graph is planar or nonplanar (Examples #9-10)
- Is planar or nonplanar by finding a homeomorphic subgraph K5 or K3,3 (Examples #11-13)
Graph Coloring
51 min 6 Examples
- Introduction to Video: Graph Coloring
- Overview of Chromatic Numbers and the Four and Five Color Theorems
- Construct a dual graph and find the least number of colors to color (Example #1)
- Create a dual graph and find the chromatic number (Example #2)
- Find the chromatic number given the graph (Examples #3-5)
- Use graph coloring to schedule final exams using the fewest number of time slots (Example #6)
Chapter Test
51 min 8 Practice Problems
- Determine if the graph is an Eulerian path, circuit or neither (Problem #1a-c)
- Determine if the graph is a Hamiltonian path, circuit or neither (Problem #ca-c)
- Determine the degree sequence, all cut points and bridges, and distance (Problem #3a-d)
- Use the Handshake Theorem to find the following (Problem #4a-c)
- Use either Prim’s or Kruskal’s Algorithm to find the MST and total minimum weight (Problem #5a-b)
- Determine which of the following graphs are Bipartite (Problem #6)
- Find, if any, of the three graphs are isomorphic (Problem #7)
- Using the rooted tree find the following (Problem #8a-i)
