Graph theory

Question 1

What is the fundamental characteristic of non-linear structures?

Answer 1

Their data doesn’t follow an obvious numerical order.

Question 2

What is a tree defined by?

Answer 2

A root node that may connect to other nodes, stemming from one specific place.

Question 3

What is a binary search tree?

Answer 3

A tree that can only ever have two links to two nodes at any given time.

Question 4

How do trees differ from graphs in terms of node connections?

Answer 4

Trees can only flow in one direction and have one-way connections.

Question 5

What is a key characteristic of graphs compared to trees?

Answer 5

Graphs do not have a concept of a ‘root’ node.

Question 6

What is a singleton graph?

Answer 6

A graph with just one node.

Question 7

What are the two types of graphs commonly recognized?

Answer 7

• Directed graphs
• Undirected graphs

Question 8

What do edges in a graph represent?

Answer 8

Connections between nodes.

Question 9

What are the two types of edges in graphs?

Answer 9

• Directed edges
• Undirected edges

Question 10

What defines a directed edge?

Answer 10

It allows travel in only one specific direction between two nodes.

Question 11

How do undirected edges differ from directed edges?

Answer 11

Undirected edges allow travel in both directions.

Question 12

What is the mathematical representation of a graph?

Answer 12

G = (V, E)

Question 13

What do V and E represent in the context of a graph?

Answer 13

• V: set of vertices
• E: set of edges

Question 14

Why is the set of vertices unordered in a graph?

Answer 14

There is no hierarchy of nodes in a graph.

Question 15

What form do edge objects take in an undirected graph?

Answer 15

They are unordered pairs.

Question 16

True or False: A tree can have loops or cyclical links.

Answer 16

False

Question 17

id ==

Answer 17

the identity function

Question 18

What is the domain of f: A -> B?

Answer 18

D(f) = A

Question 19

What is the image of f: A -> B?

Answer 19

I(f) = B

Question 20

What does f|_A mean?

Answer 20

the function f restricted to set A (subset of domain D(f))

Question 21

Suppose functions f and g where the image of g is in the domain of f. What is the concatenation f o g?

Answer 21

(fog)(x) = f(g(x))

Question 22

When is the union of a function f and g defined?

Answer 22

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).

Question 23

How do we denote the set of all sequences over an alphabet SIGMA?

Answer 23

SIGMA*

Question 24

How do we denote the empty sequence?

Answer 24

epsilon

Question 25

How do we define a simply labeled directed simple graph for a set of node labels K and edge labels [A with missing stripe]?

Answer 25

G = (V_G, E_G, K_G, lambda_G) with V_G the set of vertices, E_G the set of edges, and K_G and lambda_G the node and edge labeling functions.

Question 26

How do we define an edge-labeled directed multigraph for a set of edge labels [A with missing stripe]?

Answer 26

G = (V_G, E_G, vert_G, lambda_G) with v vertices, E edges, vert assigns pair of vertices to edges and lambda assigns labels to edges.

Question 27

How do we define a multi-labeled directed multigraph for a set of node labels K and edge labels [A with missing stripe]?

Answer 27

G = (V_G, E_G, vert_G, K_G, lambda_G) with V the vertices, E the edges, vert assigning two nodes to each edge, lambda labeling the edges.

Question 28

Let G and H be graphs. When is H a subgraph of G?

Answer 28

if V_H is a subset of V_G, E_H is a subset of E_G and vert_H (e) = vert_G (e) and lambda_H (e) = lambda_G (e) for all e in E_H.

Question 29

trivial path

Answer 29

When the two nodes connected by a path are equal.

Question 30

When are two graphs isomorphic?

Answer 30

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.

Question 31

What does the thesis reading mean when it talks about graphs up to isomorphism?

Answer 31

abstract graphs

Question 32

sentence meaning

Answer 32

the meaning inherent to the sentence itself

Question 33

speaker meaning

Answer 33

the meaning the speaker intends to convey

Question 34

Signature (ranked alphabet)

Answer 34

a pair (Σ, ar) where Σ is a finite set and ar is a mapping from Σ to the natural numbers N.

Question 35

How do we denote the arity of a symbol f in Σ?

Answer 35

ar(f)

Question 36

How do we denote the set of symbols of arity n?

Answer 36

Σ_n

Question 37

What does an algebra A consist of?

Answer 37

A signature Σ and a set of object D called the domain.

Question 38

term

Answer 38

trees of symbols

Question 39

When is a term t in T(Σ, X) linear?

Answer 39

If each variable occurs at most once in t.

Question 40

s-graphs

Answer 40

graphs with special, additional node labels called sources.

Question 41

What is the purpose of sources in s-graphs?

Answer 41

they mark the nodes where the HR algebra can 'glue' graphs together.

Question 42

What does G = H || K mean in HR algebra?

Answer 42

G is the result of merging graphs H and K.

Question 43

When is a set of L of ground terms recognizable?

Answer 43

If L = L(A) for some tree automaton A.

Question 44

Define a finite tree automaton over a signature Σ:

Answer 44

a tuple A = (Q, Σ, Q_f, ∆) with Q the set of states, Q_f the set of final states and ∆ the set of transition rules.

Question 45

What do tree automata over Σ run on?

Answer 45

ground terms over Σ.

Question 46

When do we call a state q in Q accessible?

Answer 46

If there is a ground term t in T (Σ) such that