Graph theory Flashcards
What is the fundamental characteristic of non-linear structures?
Their data doesn’t follow an obvious numerical order.
What is a tree defined by?
A root node that may connect to other nodes, stemming from one specific place.
What is a binary search tree?
A tree that can only ever have two links to two nodes at any given time.
How do trees differ from graphs in terms of node connections?
Trees can only flow in one direction and have one-way connections.
What is a key characteristic of graphs compared to trees?
Graphs do not have a concept of a ‘root’ node.
What is a singleton graph?
A graph with just one node.
What are the two types of graphs commonly recognized?
- Directed graphs
- Undirected graphs
What do edges in a graph represent?
Connections between nodes.
What are the two types of edges in graphs?
- Directed edges
- Undirected edges
What defines a directed edge?
It allows travel in only one specific direction between two nodes.
How do undirected edges differ from directed edges?
Undirected edges allow travel in both directions.
What is the mathematical representation of a graph?
G = (V, E)
What do V and E represent in the context of a graph?
- V: set of vertices
- E: set of edges
Why is the set of vertices unordered in a graph?
There is no hierarchy of nodes in a graph.
What form do edge objects take in an undirected graph?
They are unordered pairs.
True or False: A tree can have loops or cyclical links.
False
id ==
the identity function
What is the domain of f: A -> B?
D(f) = A
What is the image of f: A -> B?
I(f) = B
What does f|A mean?
the function f restricted to set A (subset of domain D(f))
Suppose functions f and g where the image of g is in the domain of f. What is the concatenation f o g?
(fog)(x) = f(g(x))
When is the union of a function f and g defined?
if f and g agree where their domains overlap, thus mathematically:
if for all x in the intersection of D(f) and D(g), it holds that f(x) = g(x).
How do we denote the set of all sequences over an alphabet SIGMA?
SIGMA*
How do we denote the empty sequence?
epsilon
How do we define a simply labeled directed simple graph for a set of node labels K and edge labels [A with missing stripe]?
G = (VG, EG, KG, lambdaG)
with VG the set of vertices, EG the set of edges, and KG and lambdaG the node and edge labeling functions.
How do we define an edge-labeled directed multigraph for a set of edge labels [A with missing stripe]?
G = (VG, EG, vertG, lambdaG)
with v vertices, E edges, vert assigns pair of vertices to edges and lambda assigns labels to edges.
How do we define a multi-labeled directed multigraph for a set of node labels K and edge labels [A with missing stripe]?
G = (VG, EG, vertG, KG, lambdaG)
with V the vertices, E the edges, vert assigning two nodes to each edge, lambda labeling the edges.
Let G and H be graphs. When is H a subgraph of G?
if VH is a subset of VG, EH is a subset of EG and vertH (e) = vertG (e) and lambdaH (e) = lambdaG (e) for all e in EH.
trivial path
When the two nodes connected by a path are equal.
When are two graphs isomorphic?
When the nodes of one graph can be mapped one-on-one to the nodes of the other graph, same for the edges. Labels dont have to be the same.
What does the thesis reading mean when it talks about graphs up to isomorphism?
abstract graphs
sentence meaning
the meaning inherent to the sentence itself
speaker meaning
the meaning the speaker intends to convey
Signature (ranked alphabet)
a pair (Σ, ar) where Σ is a finite set and ar is a mapping from Σ to the natural numbers N.
How do we denote the arity of a symbol f in Σ?
ar(f)
How do we denote the set of symbols of arity n?
Σn
What does an algebra A consist of?
A signature Σ and a set of object D called the domain.
term
trees of symbols
When is a term t in T(Σ, X) linear?
If each variable occurs at most once in t.
s-graphs
graphs with special, additional node labels called sources.
What is the purpose of sources in s-graphs?
they mark the nodes where the HR algebra can ‘glue’ graphs together.
What does G = H || K mean in HR algebra?
G is the result of merging graphs H and K.
When is a set of L of ground terms recognizable?
If L = L(A) for some tree automaton A.
Define a finite tree automaton over a signature Σ:
a tuple A = (Q, Σ, Qf, ∆)
with Q the set of states, Qf the set of final states and ∆ the set of transition rules.
What do tree automata over Σ run on?
ground terms over Σ.
When do we call a state q in Q accessible?
If there is a ground term t in T (Σ) such that
