Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Spring 2018 > math 401 test 3 > Flashcards

math 401 test 3 Flashcards

1
Q

the size of the vertex set |V| is called the ? of G

A

order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

G is a multigraph if

A

there are some repeated edges {xi, xj} (called a multiple edge) for i=/=j in E

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

G is a general graph if

A

we further allow a multigraph to have {xi, xi} (called a loop) in E

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

how to count the degree of a vertex with a loop

A

the loop counts twice for degree (but only once for edge)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Σd(vi) from i to n =

A

2|E|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Handshake problem: prove that the number of people that shake hands an odd number of times is even

A

Σd(vi) of the odd’s + Σd(vi) of the even’s must be = 2|E|. Since Σd(vi) of the evens will be even, the Σd(vi) of the odds must be even as well

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Two general graphs are called isomorphic provided that

A

|V| = |V’| and |E| = |E’|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Let G be a (general) graph. G’ is a (general) subgraph of G if

A

V’⊆V and E’⊆E

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

G’ is a spanning (general) subgraph of G if

A

V’ = V and E’ ⊆ E

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

G’ is a (general) subgraph induced by V’ if

A

any edge of G with both end-vertices in V’ is also an edge of G’

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

A walk is closed if

A

you return to the starting vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

A walk is open if

A

you do not return to the starting vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

A trail is

A

a walk with distinct edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

A closed trail is

A

a closed walk with distinct edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

A path is

A

a walk with distinct vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

A cycle is

A

a closed walk with distinct vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

A general graph is called connected provided that, for each pair of vertices x and y, there is

A

a walk joining x and y

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Let G and G’ be two general graphs. Then the following are necessary conditions for G and G’ to be isomorphic

A
  1. if G is a graph, so is G’
  2. G and G’ have the same number of components
  3. if G has a cycle equal to some length k, so does G’
  4. if G has an (induced) general subgraph that is a complete graph Km, so does G’
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

The adjacency matrix is an n x n array such that

A

the entry aij in row i and column j equals teh number of edges joining xi and xj

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

An open Eulerian trail is

A

an open trail which contains each edge of a graph G exactly once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

a closed Eulerian trail is

A

a closed trail which contains each edge of G exactly once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Let G be a connected general graph. G has a closed Eulerian trail if and only if

A

the degree of each vertex of G is even

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Let G be a connected general graph. G has an open Eulerian trail if and only if

A

G has exactly two vertices of odd degree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Let G be a connected graph and suppose that the number of vertices of G with odd degree is m>0. Then the edges of G can be partitioned into ? trails. It is impossible to partition the edges of G into fewer than ? open trails.

A

m/2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

A Hamiltonian chain is

A

a chain connecting all vertices of G

26
Q

A Hamiltonian cycle is a

A

cycle containing all vertices of G

27
Q

A connected graph with a ? does not have a Hamiltonian cycle

A

bridge

28
Q

Let G be a graph with order n>=3.

a) If the sum of degrees of any two non-adjacent vertices is at least n, then G has a Hamiltonian ?
b) If the sum of degrees of any two non-adjacent vertices is at least n-1, then G has a Hamiltonian ?

A

a) cycle

b) chain

29
Q

Let G = (V,E) be a multigraph. G is called bipartite provided the vertex set V can be

A

partitioned into two subsets X and Y such that each edge of G has one vertex in X and one vertex in Y (X and Y is called a bi-partition of G)

30
Q

A multigraph is bipartite if and only if

A

each of its cycles has even length

31
Q

Let G be a bipartite graph with bi-partition X, Y. If |X| =/= |Y|, then G (has a/has no) Hamiltonian cycle. If |X| = |Y|, then G (has a/has no) Hamiltonian chain connecting two vertices in X or Y. If |X| = |Y|+1, then G (has a/has no) Hamiltonian chain connecting one vertex in X and a vertex in Y

A

has no for all

32
Q

a tree is

A

a connected graph that becomes disconnected upon the removal of any edge (each edge of a tree is a bridge)

33
Q

A connected graph of order n is a tree if and only if

A

it has exactly n-1 edges and no cycle

34
Q

Let G be a connected graph and a be an edge of G. Then a is a bridge if and only if

A

no cycle in G contains a

35
Q

A graph G is a tree if and only if every pair of distinct vertices x and y are joined by

A

a unique chain

36
Q

A spanning tree is

A

a tree containing all vertices of G

37
Q

Every connected graph has a

A

spanning tree

38
Q

Let T be a spanning tree of a connected graph G. Let a be an edge of G which is not an edge of T. Then there is an edge b of T such that

A

the graph T’ obtained from T by inserting a and deleting b is also a spanning tree of G

39
Q

Let G = (V, E) be a graph. A proper coloring of G is

A

an assignment of a color to each vertex of G in such a way that adjacent vertices are assigned different colors

40
Q

If a color is chosen from a set of k-colors, then the vertex-coloring is called

A

a k-coloring, whether or not all k colors are used

41
Q

If G has a k-coloring, it is said to be

A

k-colorable

42
Q

The smallest k, such that G is k-colorable, is called

A

the chromatic number of G X(G)

43
Q

Let G be a graph of order n>=1. Then X(G) <= ?

A

n

44
Q

X(G) = n if and only if

A

G = Kn

45
Q

X(G) = 1 if and only if

A

G is a null graph Nn (a graph with no edges)

46
Q

Let G be a graph and let H be a subgraph of G. Then X(G) ? X(H).

A

> =

47
Q

If G has a subgraph equal to a complete graph Kp of order p, then X(G) ? p

A

> =

48
Q

Let G be a graph of order n and let q be the largest order of an induced subgraph equal to Nq. Then X(G) >=

A

ceil (n/q)

49
Q

A graph is called planar provided that

A

it can be represented by a drawing in the plane such that two edges-curves intersect only at vertex-points

50
Q

Let G’ be a plan representation of G. Then any two edges can only intersect at ?

A

the vertices

51
Q

Let G’ be a planar graph with n vertices, e edges, and r regions. Let the number of edges bordering the regions be, respectively, f1, f2, …, fr. Then Σfi from i to r =

A

= 2e = Σd(v) for each vertex in V

52
Q

Euler’s formula: Let G be a connected planar graph with n vertices, e edges, and r regions. Then

A

r - e + n = 2

53
Q

Let G be a connected planar graph. Then G has a vertex v such that deg(v) <= ?

A

5

54
Q

Let G be a planar graph. Then |E| <= ?

A

3n-6

55
Q

Let G be a bipartite planar graph. Then |E| <= ?

A

2n-4

56
Q

Algorithm for a closed Eulerian trail starting with a1 = {x0, x1} ∈ E

A
  1. put i=1
  2. put W = {x0, x1}
  3. put F = {a1}
  4. while xi =/= x0 do (i) locate an edge a,i+1 = {xi, x,i+1} not in F (ii) put x,i+1 in W (x,i+1 may already be in W) (iii) put a,i+1 in F (iv) i++ and go back to 1
57
Q

algorithm for spanning tree: let G be a connected graph of order n

A

(i) set F = E
(ii) while there is an edge F such that a is not a bridge of G = (V, F), set F = F - {a}

the terminal graph T = (V, F) is a spanning tree of G

58
Q

BF-algorithm to grow a BSF-tree rooted at u (let u be any vertex)

A
  1. put i=1, U={u}, D(u) = 0, bf(u) = 1, F = Ø, and T = (U, F)
  2. if there is no edge in U that joins a vertex x in U to a vertex y in V-U, then stop. Otherwise, determine if there is an edge a = {x,y} with x in U and y in V-U such that x has the smallest breadth-first number bf(x) and do
    (i) put bf(y) = i+1
    (ii) put D(y) = D(x)+1
    (iii) Set U = U ∪ {y} and F = F ∪ {a}
    (iv) put T = (U, F)
    (v) i++ and go back to 2
59
Q

DF-algorithm to grow a DFS-tree rooted at u (let u be any vertex)

A
  1. put i=1, U = {u}, df(u) = 1, F = Ø, and T = (U, F)
  2. if there is no edge in G that joins a vertex x in U to a vertex y in V-U then stop. Otherwise, determine an edge a = {x, y} with x in U and y in V-U such that x has the largest depth-first number df(x) and do
    (i) put df(y) = i+1
    (ii) set U = U ∪ {y} and F = F ∪ {a}
    (iii) Put T = (U, F)
    (iv) i++ and go back to 2
60
Q

Algorithm for a distance-tree for u (Dijkstra’s algorithm): Let G = (V, E) be a graph of order n and let u be any vertex

A
  1. put i=1, U = {u}, D(u)=0, F=Ø, and T=(U,F)
  2. if there is no edge in G that joins a vertex x in U to a vertex y in V-U then stop. Otherwise, determine an edge a = {x, y} with x in U and y in V-U such that D(x) + c{x,y} is as small as possible and do
    (i) set U = U ∪ {y} and F = F ∪ {a}
    (ii) Put D(y) = D(x) + c{x,y} and go back to 2
61
Q

Greedy algorithm for a minimum weight spanning tree (Kruskal’s algorithm): Let G=(V,E) be a weighted connected graph of order n with weight function c

A
  1. put F = Ø
  2. while there exists an edge a not in F such that F ∪ {a} does not contain the edges of a cycle of G, determine such an edge a with minimum weight and set F = F ∪ {a}
  3. put T = (U,F)
62
Q

Prim’s algorithm for a minimum weight spanning tree: Let G=(V,E) be a graph of order n with weight function c and let u be any vertex

A
  1. put i=1, U1 = {u}, F1 = Ø, and T1 = (U1, F1)
  2. for i = 2, 3, …, n-1, do the following
    (i) locate an edge ai = {x, y}of smallest weight such that x is in Ui and y is in V-Ui
    (ii) Put U,i+1 = Ui ∪ {y}, F,i+1 = Fi ∪ {ai}, and T,i+1 = (U,i+1 , F,i+1)
    (iii) increase i to i+1
  3. output T,n-1 = (U,n-1 , F,n-1) where U,n-1 = V

Spring 2018 (23 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions