patternMinor
What does "local" mean?
Viewed 0 times
localdoesmeanwhat
Problem
I study graph theory on my own using Diestel's Graph Theory book (with Algorithmic graph theory in mind). I don't understand what local property, global property, locality mean given a graph $G$.
For example, on the page 5 it says
The average degree quantifies globally what is measured locally by the
vertex degrees: the number of edges of $G$ per vertex. Sometimes it will
be convenient to express this ratio directly, as $\varepsilon(G) := |E|/|V|$.
In particular, I found the following phrases including the word local...
and many more...
Could someone explain (possibly with examples) what these local and global mean in the context of the graph theory?
For example, on the page 5 it says
The average degree quantifies globally what is measured locally by the
vertex degrees: the number of edges of $G$ per vertex. Sometimes it will
be convenient to express this ratio directly, as $\varepsilon(G) := |E|/|V|$.
In particular, I found the following phrases including the word local...
- local information (pg. 46)
- maximum local density (pg. 61)
- the above local structures (pg. 101)
- locally looks like a tree (pg. 110)
- there is a local reason for it (pg. 110)
- we are looking for local implications of global assumptions (pg. 181).
and many more...
Could someone explain (possibly with examples) what these local and global mean in the context of the graph theory?
Solution
Local property - a property that relates to a specific vertex and its near neighbors. For example, the number of neighbors or 2nd order neighbors a vertex $v$ has. "locally looks like a tree" more formally could be written as the sub-graph of vertices with distance $k$ or less of the vertex $v$ is a tree.
Global property - a property that relates to the graph, like its diameter, average degree, number of connected components or even its size.
Global property - a property that relates to the graph, like its diameter, average degree, number of connected components or even its size.
Context
StackExchange Computer Science Q#86260, answer score: 6
Revisions (0)
No revisions yet.