1 - Basic Definitions

Question 1

We say that graph is well-founded if it has…

1)

2)

Answer 1

We say that graph is well-founded if it has…

1) No looping paths
2) No infinite descending paths

Question 2

We say that two graphs are isomorphic

if there is a map f: v -> v_o s.t.

1)

2)

Answer 2

We say that two graphs are isomorphic

if there is a map f: v -> v_o s.t.

1) f is a bijection
2) For all v_o,v₁ in V :

there is an edge from v_o to v₁

iff

there is an edge from f(v_o) to f(v₁)

Question 3

f is a ______\_

if for all u in U

there is some v in V s.t.

f(v) = u

Answer 3

f is a surjection

if for all u in U

there is some v in V s.t.

f(v) = u

Question 4

in lay terms, a _______ is a mapping such that all things in the target are hit

Answer 4

in lay terms, a surjection is a mapping such that all ​things in the target are hit

Question 5

f is an _______\_

if for all v_o, v₁ in V

if v_o != v₁

then f(v_o) != f(v₁)

Answer 5

f is an injection

if for all v_o, v₁ in V

if v_o != v₁

then f(v_o) != f(v₁)

Question 6

in lay terms, a(n) _________ is a mapping such that inputs don’t get mapped to the same output

Answer 6

in lay terms, a(n) injection is a mapping such that inputs don’t get mapped to the same output

Question 7

Match the terms together:

Bijection

Injection

Surjection

One-to-One

Onto

One-to-One Correspondence

Answer 7

Match the terms together:

Injection = One-to-One

Surjection = Onto

Bijection = One-to-One Correspondence

Question 8

A ______ is a mapping that is both ______ and _______.

Answer 8

A bijection is a mapping that is both injective and surjective.

Question 9

An ________** is an isomorphism from a graph G to itself. We say that it is **______\_ if it it just the identity.

Answer 9

An automorphism** is an isomorphism from a graph G to itself. We say that it is **trivial​ if it it just the identity.

Question 10

An _______\_ from a graph G1 to a graph G2 is an isomorphism from G1 into a subgraph G2.

Answer 10

An embedding from a graph G1 to a graph G2 is an isomorphism from G1 into a subgraph G2.

Question 11

Models have 3 main ingredients:

1)

2)

3)

Answer 11

• Models* have 3 main ingredients:
  1) a language L
  2) a domain M of objects
  3) an interpretation of the languages constants symbols, relation symbols, etc

Question 12

A graph V is ________\_

if it is the case that for any v_o, v₁ in V

if v_o and v₁ have arrows pointing into them from the same vertices

then v_o must = v₁

(in other words, if for any pair of points that have the same points going to it, then each of these points HAVE to be the same point…not 2 separate distinct points)

Answer 12

A graph V is extensional

if it is the case that for any v_o, v₁ in V

if v_o and v₁ have arrows pointing into them from the same vertices

then v_o must = v₁

(in other words, if for any pair of points that have the same points going to it, then each of these points HAVE to be the same point…not 2 separate distinct points)

Question 13

A graph G is _______\_ in some property P

if every graph F with property P can be embedded in G.

Answer 13

A graph G is universal in some property P

if every graph F with property P can be embedded in G.

Question 14

A graph is ______\_ in some property P if:

1) G has property P
2) if G is a subgraph of F

and F has property P

then F must = G (be the same graph)

(ie - if a graph is ______\_ it is the largest graph that can have this property P)

Answer 14

A graph is maximal in some property P if:

1) G has property P
2) if G is a subgraph of F

and F has property P

then F must = G (be the same graph)

(ie - if a graph is maximal it is the largest graph that can have this property P)

Question 15

The _______** **______\_ of vertex v is the subgraph of G whose vertices are the ancestors of v.

(all those points or vertices that eventually have a path that leads to vertex v

Answer 15

The transitive** **closure of v is the subgraph of G whose vertices are the ancestors of v.

Question 16

Match the term/phrase with the following pictures:

• Bijection (injection + surjection)
• NOT a function
• Surjective (not injective)
• General function
• Injective (not surjective)

Answer 16