Chapter 1

Question 1

what is a binary relation given a set S?

Answer 1

A binary relation R on S is a subset of SxS, or the set of every ordered pair.

Question 2

What quality holds for you to write S.2 = f(S.1) (not a network)

Answer 2

Write that if, for all S.1 in S, there exists S.2 in s s.t. (S.1, S.2) in R. AKA, every S.1 is “connected” somewhere

Question 3

R is irreflexive if:

Answer 3

(s,s) not in R for All s in S. AKA, not reflexive

Question 4

A relation is symmetric if:

Answer 4

(S.1,S.2) in R => (S.2,S.1) in R. Any connection that is inherently 2 way.

Question 5

Formal def of graph.

Answer 5

A finite nonempty set V = {v.1,v.2,…,v.n} together w/ an irreflexive symmetric relationship r = {v.i,v.j}

Question 6

Edge set of G: is a set of symmetric pairs

Answer 6

is a set of symmetric pairs, E = {ab, bc}

Question 7

If e = uv in E (edge set, then: the 3 vocab to describe all this is:

Answer 7

e joins u,v
u,v are incident with e
u,v are adjacent

Question 8

Edge adjacency:

Answer 8

if uv, vw in E, then these edges are adjacent.

Question 9

Order, size:

Answer 9

Number of vertices p is the order,
Number of edges q is the size.

Question 10

Digraph and arcs:

Answer 10

A digraph is a nonempty set v together w/ an irreflexive relation R (not necessarily symmetric). The edges of digraphs are called arcs.

Question 11

A multigraph:

Answer 11

is a triple (V, E, T) where T: E -> Z+ where T is the function to find redundant edges.

Question 12

A network is:

Answer 12

a graph or digraph together with a function f: E(G) -> Real. Each edge has a number on it.

Question 13

Graph with all edges or no edges:

Answer 13

Complete or Null graphs.

Question 14

A graph G is bipartite (and complete) if:

Answer 14

There exists a partition V = X.bar union Y.bar s.t. every edge is between vertices in X.bar and Y.bar. Complete is bipartite with all possible edges.

Question 15

The deg(v) is:

Answer 15

the number of edges incident to a vertex v.