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
🔗
Relationship to Chapter 16 (Logic diagrams)
Logic diagrams consist of the elements and the connections between them. If you forget the electrical signals and leave only "what is connected to" you'll get a graph. The tops are elements (I, or, N, N), ribs are the wires between them, so chapter 16 implicitly prepared you for the idea of the graph: any diagram is a private case of a graph, only oriented and most often without cycles. Graphs are a universal language to describe any connection: roads between cities, friends in social media, the relationship of tasks in the project.
📊
Examples of graphal models
A
B
B
G
D
social media friends.
Friends on social media
Undirected Count
The tops are users, the ribs are friendship, the two-way connection.
Moscow
The door.
Peter.
Choice
170
300
120
Road map
Weighted, unoriented
The upper part is the city, the weight is the distance, find the shortest way.
/
usr
etc
f1
f2
f3
f4
File system
Tree
The folders are tops, the files are leaves, the hierarchy of the input.
Start
A
B
C
Finish
Task dependency scheme
Indicative graph (DAG)
Which should be done before the next task.
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
Drawing a graph from the matrix
🔄
Reverse mode: matrix ~ graph
Enter a related matrix:
1
There's a rib,
*
= weight/length,
0
No rib. The count will be built automatically.
Guidanced
A
B
C
D
A
B
C
D
Рёбра: A→B, A→C, B→D, C→D
06
Mini test
📝
The basis of the graphs is 5 out of 50 questions.
Level:
Newcomer
0
/
50
XP
⬡
0
Question 1 out of 5
♪ Series:
0