Counts: bases

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

Back to the table of contents
Alterna chapter 17 page 17.2
Counts: bases
Tops, ribs, degrees.
Count
A pair (V, E), where V is a multitude of vertices, E is a variety of ribs between them. A simple model describing the connections: social media, maps, dependency patterns.
GEF
PIF
OGE No. 4.9
EGE No. 1
01
Definitions
Basic concepts
Top (V)
- Count node, object.
Rebra (E)
- the connection between the two vertices.
Top degree deg(v)
- The number of ribs she's had.
The Wing
- A rib from the top into itself (usually not considered in simple graphs).
Back ribs
- Several ribs between a pair of vertices.
Path
is a sequence of vertices where each adjacent pair is connected by a rib.
Cycle
is the path that begins and ends at the same summit.
Contact box
- from any top to any other top.
Lemma on handshakes.
The sum of the degrees of all the tops of the graph is equal to twice the number of ribs:
Σ deg(v) = 2|E|
That's because each rib adds one to each of its two vertices.
02
Grape types
↔
Undirected
ribs without arrows
It's two-way, social media friendship, roads.
→
Orientation (orthograph)
Ribs arcs
One-way connections, subscriptions, one-way roads.
⚖️
Weighted
Ribs with weight
Each rib is a number (length, value, time).
🌳
Tree
contact without cycles
V tops, V-1 ribs, between any two vertices, one path is exactly the same.
⭐
Full (K_n)
All possible ribs
Each pair of vertices is connected. K_n: n(n-1)/2 ribs.
🔗
Double-deck
2 groups of tops
It's just between groups.
03
Relationship matrix and list of related relationships
Associated matrix A (N×N)
A[i][j] = 1
, if there is a rib i,j, otherwise
0
For non-directed A, symmetrical.
He takes O(N2) memory. Checks quickly the presence of the O(1) rib.
Example: box with 4 vertices and 4 ribs
Ribs: (A,B), (A (C), (B,D), (C,D)
A
B
C
D
A
0
1
1
0
B
1
0
0
1
C
1
0
0
1
D
0
1
1
0
List of related relationships (Adjacencia List)
For each vertebrate, it's a list of its neighbors. The memory of O(V+E) is faster than the graph (O(V + E) versus O(v2) by the matrix.
It's used in real programs.
A
: [B, C]
B
: [A, D]
C
: [A, D]
D
: [B, C]
04
Canvas - Graphic Editor
Squeeze on the canvas, add a top, pull on the top, and pull on to the other one, make a rib.
✏️
Create Your Count
Кликни по холсту, чтобы добавить вершину.
05
Mini test
📝
6 questions per box