⭐️ 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.

Excellent! Thank you for sharing this!

Thank you sir! This has cleared up so many questions I had in class

Thanks man for clearing my doubts .

good job! this was very entertaining and educative! :D keep it up

Nice video 👌👏

Thank you for this video!

Perfect explanation!

Thanks 👍

Go A's because of you. Love you 💓💓💓

yeah please do advanced graph theory courses. Would love to see that.

Well, THAT was surprisingly good.

How did you get from Denver to Dallas? 18:00

Can you make a full course of organic chemistry

Counting and combinatorics pls 🥺

Share the road, Euler...

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.

🎯 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

@newtechai4367

2 жыл бұрын

And the PDF versions of this please through email or any orther means

7! /2 = 2520, not 5040

l like it but please use another microphone.

34:35 first two connection is wrong i think

Links out dated