Graphics: Deepened Level (weighted, MST, SCC)

Содержание и основные понятия

Back to the table of contents
Alterna chapter 24
Graphics: Deepened Level (weighted, MST, SCC)
Dakestra, A*, MST, SCC for the 11th grade and the Olympics.
Chapter 17 is the basic graphs (degrees, related matrices, topsort).
advanced level
: Weighted graphs, shortest route algorithms, MST, SCC, CPM. Exclusive interactors: MST Game, Bellman-Ford Visualizer, Project Planner, Graphic Painting.
GEF · 11 grade
PLF · Entrance.
EGE No. 1
Olympic level
How does this chapter differ from chapter 17?
Chapter 17
Chapter 24
Undirected graphs, degrees
Weighted oriented graphs
Associated matrix (0/1)
Weight matrix + achievable matrix
DFS/BFS, connectivity
SCC (Taryan), condensation of DAG
Topsort, DP on DAG
CPM, critical path, reserves
Calculation of tracks (formula)
Algorithms of the shortest path
—
MST (Prime/Rascal), A*, Bellman-Ford
—
MST Game, Graphic Painting
🌍
DAG in real life
Minecraft: Craft
Woodboards are so much like instruments. You can't paint walls until the foundation is built. Each item depends on the previous ones, the typical DAG.
Git: Committs
Committs form DAG (directed acyclic grape). Merge comits create parallel branches. Topological order = assembly order/depletion order.
School curriculum
Arifmetics of the algebra function is a derivative. You can't study integrals until you understand the derivatives. The relationship between the themes is DAG.
Program Collection (Mackfile)
obproject.o depends on the source.cpp, final.exe depends on all the object.o. The logical order determines the correct compilation procedure.
Job scheduling
Task A ~ task B means: A has to be done before B. The planner uses Kahn's algorithm to determine the acceptable schedule.
Bureaucracy/document flow
The application for a settlement of payment. You can't be paid without agreement. Each step depends on the previous one, DAG.
24
Chapter Pages
Six pages with theory, unique interactors, and a bank of assignments.
24.1
Graphics and weighting matrix
Weighted graphs, achievable matrix, SCC (Taryana).
Interactive: Graphic painting (Exam timing)
.
24.2
Shorter Paths
Dakestra, A*, Bellman-Ford, MST (Prime/Rascal).
Interactors: Dakestra Visualizer, MST Game, Bellman-Ford Visualizer
.
24.3
Calculation of the routes to the DAG
Topsort (Cana), DP for the number of tracks, CPM.
Interactive: CPM Project Planner (Gant, reserves)
.
24.4
Workshop
Bank 20 assignments: 10 EEG + 10 EGE No. 1 with reviews and mathematical decisions.
24.5
Polygon examination
Quest 800 XP + Test 10 min + Open Task (Daxtra + MST).
🎮
Unique Interactors (not in Chapter 17)
🌲 MST Game
Build an MST on Paint: Choose ribs from lung to heavy. DSU shows components and cycles.
♪ Bellman-Ford visualiser
Step-relaxation of ribs with negative balance support and negative cycle specification.
CPM Planner
Interactive Gant chart: Change the length of the tasks, see how the critical path and reserves change.
♪ Painting the graph
Make a schedule of exams: vertices = exams, ribs = student conflicts. Find a minimum number of slots.
🔗
Links
Chapter 23
Modeling is the previous chapter. The graphs are used to model networks and systems.
Chapter 17
Basic graphs: degrees, DFS/BFS, connectivity, topsort.
Chapter 25
Trees are a private case of graphs (V-1 ribs, connectivity, lack of cycles).
Chapter 19
Trees of games: also graphs (minimax as DP on DAG).