Graphics: Deepening (weighted, matrices, SCC)

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

Back to the table of contents
Alterna · Chapter 24 · page 24.1
Graphics: Deepening (weighted, matrices, SCC)
Weight matrix, achievable matrix, Tarian algorithm for highly connected components.
Chapter 17 is an introduction to the box, and here is an extension for the 11th grade: weighted graphs, an achievable matrix, the Taryan algorithm, and preparing for the EEG No.1 and the Olympics.
GEF · 11 ppm
PLF · Entrance.
EGE No. 1
Olympic
01
Weight matrix
For
weighted graph
The weight matrix W is a table where W[i][j] = the weight of the rib i~j. If the rib is not present, write down the ~ (continuous) or 0 depends on the task.
For
Unweighted
The graph is the boulder of the matrix (0/1).
Multigraphs
- number of ribs between the tops.
Example: 4 vertices with weights
A
B
C
D
A
0
5
∞
10
B
∞
0
3
∞
C
∞
∞
0
1
D
∞
∞
∞
0
The rib indicates a lack of rib. Diagonal = 0 (distance to self). Ribs: A
0
1
2
3
4
Figure: Acyclic orientation graph (DAG) with 5 vertices.
Relationship to the EEG
The EGR No. 3 gives a graph in the form of a table of distances or diagrams. You have to find the shortest way between the two vertices. The matrix is one way to set the graph.
02
Interactive: build a weighting matrix
Press the SVG ribs to add/take the weights. The matrix is updated automatically.
0
1
2
3
4
Example DAG: 5 vertices, ribs 0,1, 0, 2, 1, 3, 3 and 4
🔧
Matrix Designer
Click on the rib - ask for weight
03
Feasibility matrix
Feasibility matrix D
: D[i][j] = 1 if from the top of i it is possible to reach j (perhaps through the intermediate peaks) and 0 is different.
How to build:
Let's take the A-related matrix.
Compute transit circuit: D = A ~ A2 A3 ... ~A
n
In practice, the Warschel-Floyd algorithm for
O(V³)
or BFS from each vertice for
O(V·(V+E))
.
Application:
To determine which peaks are connected, to check the connection of the graph, to find the components of the connection.
A
B
C
D
Graph for example: A.B., B.C.,
Example: box of 4 vertices
Ribs: A.B., B.C., C.D., A.D (direct).
A
B
C
D
A
0
1
0
1
B
0
0
1
0
C
0
0
0
1
D
0
0
0
0
Step-building D = A * A2 * A3 * A4 (~= Logical OR):
Step 1 - A1 (direct path):
A.B., A.D., B.C., C.D.1. units in the respective cells
A1 shows: from A to B and D, from B to C, from C to D
Step 2 - A2 (way length 2):
A.B.C., A.D. (no), B.C.2.D., a.D.1...? no D.
A2: A ± C (through B), B ± D (through C)
Step 3 is a combination of: D = A1 ♪ A2 ♪
Build D: D[A][C] = 1 (through B), D[B][D] =1 (through C)
Because A\C\D(long 3: another association gives D[A][D]=1
Outcome: D[A][B]=1, D[ A][C] =1, D [A][D] = 1, D[B][C]= 1, D [B] [D]=1 , D[C][D][] = 1 ♪ D[D] [ D] =1 (diagonal)
A
B
C
D
A
1
1
1
1
B
0
1
1
1
C
0
0
1
1
D
0
0
0
1
Reading: from
A
achievable B, C, D;
B
- C, D; from
C
- D; D is only achievable.
Implementation on Python: Floyd-Worsell
def floyd_warshall(adj):
# adj — матрица смежности, adj[i][j]=1 если есть ребро i→j
n = len(adj)
d = [row[:] for row in adj] # копируем A¹
for k in range(n): # промежуточная вершина
for i in range(n):
for j in range(n):
d[i][j] = d[i][j] or (d[i][k] and d[k][j])
return d # матрица достижимости
# Пример:
adj = [
[0,1,0,1], # A → B, D
[0,0,1,0], # B → C
[0,0,0,1], # C → D
[0,0,0,0] # D → никуда
]
D = floyd_warshall(adj)
# D[0][2]=1: из A можно попасть в C
print("Достижимость из A:", [j for j in range(4) if D[0][j]])
O(V3) is a problem for V ≤ 300–500. For large graphs, use BFS from each vertex: O( V·(V+E)).
🔢
Floyd-Worsell: step by step
04
Strongly connected components (SCC)
Strongly connected component (SCC)
is the maximum set of vertebrates in which from any top there is a path to any other (taking into account the direction of the ribs).
Key fact:
If you squeeze every SCC into one top, you'll get
acyclic box (DAG)
- It's called
Capacitation of graph
.
Taryan's algorithm
Complexity: O(V+E).
The idea is to find "corn" SCCs, which are the ones that you can't get into the previously visited component.
Example: Searching SCC
Graph: A, B, C, A, D, E, D (cycle), C, F. Two SCCs: {A,B,C} and {D,E}.
A
B
C
D
E
F
How Tarian works:
On each top, it is assigned
Number
(entry time) and
lowlink
(minimum attainable number).
The upper part is the root of SCC if
lowlink[v] = num[v]
.
When returned from the DFS, all the tops of the drain to the root form one SCC.
def tarjan_scc(n, adj):
num = [-1]*n; low = [0]*n; stack = []; on_stack = [False]*n
timer = [0]; result = []
def dfs(v):
num[v] = low[v] = timer[0]; timer[0] += 1
stack.append(v); on_stack[v] = True
for u in adj[v]:
if num[u] == -1:
dfs(u); low[v] = min(low[v], low[u])
elif on_stack[u]:
low[v] = min(low[v], num[u])
if low[v] == num[v]: # корень SCC
comp = []
while True:
w = stack.pop(); on_stack[w] = False
comp.append(w)
if w == v: break
result.append(comp)
for v in range(n):
if num[v] == -1: dfs(v)
return result # список SCC
🔗
Tarjana algorithm: SSC search
Example result:
[A,B,C]
,
[D,E]
,
[F]
. Condensation: each SCC is compressed into one top . .
DAG
.
Why would you do that?
Dependency analysis (libraries, packages)
Systems deployment (capacitation)
Searching for cycles in oriented graphs
EGE No. 1: Tasks for Graphic Analysis
05
Topological sorting
Topological order
- a sequence of vertebrates in which all ribs are directed from left to right.
DAG
(directed acyclic graph).
Kahn's algorithm
Count
in-degree
For each vertice.
Put all vertices in line with
in-degree = 0
.
Repeat: remove the top from the top of the line, add to the result, reduce the in-degree of its neighbors. If the roommate's in-legree is 0, add it to the line.
When the line is empty, order is built.
Complexity:
O(V + E)
The result isn't the only one -- any vertice with in-degree 0 could be next.
Why do you have to:
Macefile (Makefile)
Dependency planning
Resolution of formulas in electronic tables
Schedule of courses (prerequisites)
Example:
"B" means "B depends on A." If there is a cycle, the topological order is impossible.
from collections import deque
def topological_sort(n, adj):
in_deg = [0]*n
for v in range(n):
for u in adj[v]:
in_deg[u] += 1
q = deque([v for v in range(n) if in_deg[v]==0])
order = []
while q:
v = q.popleft()
order.append(v)
for u in adj[v]:
in_deg[u] -= 1
if in_deg[u]==0:
q.append(u)
return order # если len(order)!=n — есть цикл!
📋
Kahn: step-by-step topological sorting
06
Formula Directory
Weight matrix
W[i][j] = rib weight i~j
If the ribs are missing , or 0
Feasibility
D = A ∨ A² ∨ … ∨ Aⁿ
O(V3) — Warschel-Floyd
SCC (Taryan)
O(V+E), DFS + Wall
Condensation of DAG
Size of matrix
V x V (for V vertices)
Memory: O(V2)
07
Graphic painting: Schedule
Painting task
- set the (time) top colours so that the adjacent tops are not the same color.
Chromatical number
χ(G).
Practice: schedule of examinations. Every exam is a top, a rib, a student passes both subjects. You can't have conflicting exams at the same time.
📅
Graph Coloring: Examinations
Screaming to the top to choose color (time), conflicts glow red.
Painting application
Schedule
- Examinations, classes, delines
Registering
- Distribution of