Graph theory full course for Beginners
ฝัง
- เผยแพร่เมื่อ 2 ส.ค. 2024
- In mathematics, graph #theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A #graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically; see Graph (discrete mathematics) for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.
⭐️ Table of Content ⭐️
0:00 Graph theory vocabulary
04:53 Drawing a street network graph
07:08 Drawing a graph for bridges
10:19 Dijkstra's algorithm
14:34 Dijkstra's algorithm on a table
19:20 Euler Paths
21:20 Euler Circuits
22:25 Determine if a graph has an Euler circuit
26:13 Bridges graph - looking for an Euler circuit
27:59 Fleury's algorithm
30:29 Eulerization
34:52 Hamiltonian circuits
37:30 TSP by brute force
41:23 Number of circuits in a complete graph
46:12 Nearest Neighbor ex1
48:26 Nearest Neighbor ex2
50:15 Nearest Neighbor from a table
55:06 Repeated Nearest Neighbor
58:59 Sorted Edges ex 1
1:03:15 Sorted Edges ex 2
1:05:24 Sorted Edges from a table
1:09:59 Kruskal's ex 1
1:12:59 Kruskal's from a table
⭐️ Credit ⭐️
Video to accompany the open textbook Math in Society (www.opentextbookstore.com/math.... Part of the Washington Open Course Library Math&107 course.
License: Creative Commons Attribution license (reuse allowed)
⭐️ Join Us ⭐️
Join our FB Group: / cslesson
Like our FB Page: / cslesson
Website:
⭐️ Table of Content ⭐️
0:00 Graph theory vocabulary
04:53 Drawing a street network graph
07:08 Drawing a graph for bridges
10:19 Dijkstra's algorithm
14:34 Dijkstra's algorithm on a table
19:20 Euler Paths
21:20 Euler Circuits
22:25 Determine if a graph has an Euler circuit
26:13 Bridges graph - looking for an Euler circuit
27:59 Fleury's algorithm
30:29 Eulerization
34:52 Hamiltonian circuits
37:30 TSP by brute force
41:23 Number of circuits in a complete graph
46:12 Nearest Neighbor ex1
48:26 Nearest Neighbor ex2
50:15 Nearest Neighbor from a table
55:06 Repeated Nearest Neighbor
58:59 Sorted Edges ex 1
1:03:15 Sorted Edges ex 2
1:05:24 Sorted Edges from a table
1:09:59 Kruskal's ex 1
1:12:59 Kruskal's from a table
It would be great for you guys to do an advanced graph theory course!
When computing shortest paths in a graph, you can remove any vertices of degree 2 or less, connecting their edges together. There's not really a decision to be made at those points. Not without backtracking over an edge you've already crossed, and that would not give you the shortest path. So you can simplify graphs to include only edges where a decision must be made, degree 3 or higher, and just combine the costs of the presumed connection between removed vertices.
Thank you sir! This has cleared up so many questions I had in class
Excellent! Thank you for sharing this!
Nice video 👌👏
good job! this was very entertaining and educative! :D keep it up
Thanks man for clearing my doubts .
Perfect explanation!
Thank you for this video!
Go A's because of you. Love you 💓💓💓
Thanks 👍
yeah please do advanced graph theory courses. Would love to see that.
How did you get from Denver to Dallas? 18:00
Well, THAT was surprisingly good.
Can you make a full course of organic chemistry
Counting and combinatorics pls 🥺
30:17 I completed a different circuit than you. I went from A to D to B to E back to D then to C then back to A.
7! /2 = 2520, not 5040
Share the road, Euler...
🎯 Key Takeaways for quick navigation:
00:00 📐 *Basics of Graph Theory*
- Introduction to vertex, edge, and degree in graph theory.
- Vertex represents locations, edges represent connections.
- Degree of a vertex is the number of edges meeting at that vertex.
03:17 🌐 *Connectivity in Graphs*
- Explanation of connected and not connected graphs.
- A graph is connected if there is a path between any two vertices.
- Emphasis on the importance of considering both connected and not connected graphs.
05:39 📊 *Graph Representation*
- Introducing the concept of graph representation using vertices and edges.
- Simplifying real-world problems into graphs for analysis.
- Emphasizing the importance of connections rather than specific layouts.
08:46 📏 *Weighted Graphs*
- Introduction to the concept of weights on edges in a graph.
- Examples of weights in scenarios like walking paths and flight costs.
- Weighted graphs provide additional information beyond connections.
10:52 🚗 *Dijkstra's Algorithm*
- Explanation of Dijkstra's algorithm for finding the shortest path in a graph.
- Step-by-step walkthrough of applying Dijkstra's algorithm.
- Emphasis on identifying the shortest path based on cumulative weights.
14:36 📦 *Routing Optimization Problem*
- Application of Dijkstra's algorithm in a real-world routing problem.
- Solving the shortest path problem for a package routed through processing centers.
- Demonstrates the practical use of graph theory in logistics.
19:32 🛣️ *Euler Paths and Circuits*
- Definition and difference between Euler paths and circuits.
- Euler path allows not returning to the starting point, while Euler circuit requires it.
- Illustration of finding Euler paths and circuits in sample graphs.
22:37 🔍 *Vertex Degrees and Euler Paths*
- Criteria for determining the possibility of Euler paths based on vertex degrees.
- In an Euler path, all vertices must have even degrees, except for 0 or 2 odd degree vertices.
- Application of degree analysis to identify Euler paths in graphs.
25:21 🚫 *Graphs without Euler Paths*
- Demonstration of how odd degrees in vertices impact the possibility of Euler paths.
- A graph with multiple odd degree vertices may not have an Euler path.
- Explains why certain graphs can't have Euler paths or circuits.
26:19 🌉 *Euler Circuit on Bridges of Königsberg:*
- Euler posed a problem involving the city of Königsberg and its seven bridges.
- The graph representing the landmasses and bridges doesn't have an Euler circuit due to odd degrees at each vertex.
- Demonstrated the process of finding an Euler circuit using Fleury's algorithm, choosing edges carefully to avoid disconnecting the graph.
30:40 🌐 *Eulerization for Graphs with Odd Degrees:*
- Explored the concept of Eulerization to transform a graph for an Euler circuit.
- Duplicated edges strategically to ensure all vertices have even degrees.
- Highlighted the importance of minimizing duplications for an efficient Eulerization.
33:44 🚶 *Hamiltonian Circuit and Path:*
- Defined Hamiltonian circuit as a path that visits every vertex exactly once and returns to the starting point.
- Illustrated a Hamiltonian circuit on a given graph.
- Differentiated between Hamiltonian circuit and path, showcasing a scenario where a circuit is not possible but a path exists.
37:36 💰 *Traveling Salesman Problem - Brute Force Method:*
- Introduced the Traveling Salesman Problem involving finding the minimum cost Hamiltonian circuit.
- Demonstrated the brute-force approach of trying every possible circuit.
- Emphasized the factorial growth in the number of circuits, making it impractical for larger graphs.
46:22 🤖 *Nearest Neighbor Algorithm for TSP:*
- Introduced the Nearest Neighbor algorithm as a heuristic for the Traveling Salesman Problem.
- Showcased the step-by-step application of the algorithm in finding a circuit.
- Discussed the algorithm's greedy nature, which may not always yield the optimal solution.
48:55 🌍 *Applying Nearest Neighbor Algorithm to Real Data:*
- Applied the Nearest Neighbor algorithm to a real-world scenario of a business trip.
- Selected the cheapest travel options iteratively, forming a circuit.
- Emphasized that heuristic methods like Nearest Neighbor provide practical solutions even if not always optimal.
50:46 🗺️ *Nearest Neighbor Algorithm on City Distances:*
- Utilized the Nearest Neighbor algorithm on a table of city distances.
- Started in Portland and navigated through cities to form an efficient circuit.
- Highlighted the flexibility of the algorithm for various applications.
51:00 🌍 *Traveling Salesman Problem Introduction*
- Introduction to the Traveling Salesman Problem (TSP) using the Nearest Neighbor Algorithm,
- Nearest Neighbor Algorithm demonstration for finding the initial circuit.
55:08 🔄 *Repeated Nearest Neighbor Algorithm*
- Introduction to the Repeated Nearest Neighbor Algorithm,
- Application of the Repeated Nearest Neighbor Algorithm starting at different vertices,
- Discussion on finding the circuit with the lowest cost using this algorithm.
59:14 🛣️ *Sorted Edges Algorithm*
- Explanation of the Sorted Edges Algorithm for solving the TSP,
- Demonstration of how to create a circuit by adding edges from the cheapest to most expensive,
- Comparison with the Nearest Neighbor Algorithm.
01:02:52 🌐 *Application of Sorted Edges Algorithm*
- Application of the Sorted Edges Algorithm to solve the TSP for a specific example,
- Discussion of how the Sorted Edges Algorithm can yield a slightly better circuit than Nearest Neighbor Algorithm.
01:10:54 🌳 *Minimum Cost Spanning Tree*
- Introduction to the concept of Minimum Cost Spanning Tree,
- Explanation of Kruskal's Algorithm for finding the Minimum Cost Spanning Tree,
- Application of Kruskal's Algorithm to a graph with weighted edges.
01:13:39 🌐 *Kruskal's Algorithm Example*
- Application of Kruskal's Algorithm to find the Minimum Cost Spanning Tree for a given set of connections between cities,
- Discussion of the significance of Minimum Cost Spanning Trees in practical scenarios, such as power line connections.
Made with HARPA AI
Please could I get practical exercises
And the PDF versions of this please through email or any orther means
l like it but please use another microphone.
34:35 first two connection is wrong i think
Links out dated