Brainscape's Knowledge GenomeTM

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


See full index

Graph Theory > First Oral Exam > Flashcards

First Oral Exam Flashcards

1
Q

What is a graph?

A

an ordered pair of sets (V,E).

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

What is V?

A

the vertex set

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

What is E?

A

the edge set. E contains two element subsets of V.

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

What is the complement of a graph?

A

the complement of a graph, denoted G_bar, is a graph with the vertex set V(G), and an edge set defined by:
uv » E(G_bar) iff uv ¬« E(G)

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

What is a clique?

A

A SET of pairwise adjacent vertices of a graph

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

What is an independent set?

A

A set of pairwise nonadjacent vertices

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

What is a path?

A

A graph G with a vertex set {x1, x2, x2, …, xk} such that E(G) = {x1x2, x2x3, …, xk-1xk}

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

What is a cycle?

A

A graph G with V(G) = {x1, x2, x2, …, xk} and E(G) = {x1x2, x2x3, …, xk-1xk, xkx1}

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

How do you denote a path with k vertices?

A

P_k

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

How do you denote a cycle with k vertices?

A

C_k

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

What is a complete graph?

A

A graph where all vertices are pairwise adjacent, denoted K_k.

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

What is a trivial, or null, graph?

A

A graph with |V(G)| = 0

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

What is an empty graph?

A

A graph with |V(G)| ≥ 1, and |E(G)| = 0

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

What is the order of a graph?

A

The size of the vertex set

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

What is the size of a graph?

A

The size of the edge set.

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

What is a bipartite graph?

A

A graph G is bipartite if V(G) is the union of two disjoint (possibly empty) independent sets called partite sets ofG.

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

What is the degree of a vertex?

A

The degree of a vertex v in a graph G, written d_G(v) or d(v), is the number of edges incident to v.

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

How do we denote the minimum degree of a vertex in G?

A

∂(G)

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

How do we denote the maximum degree of a vertex in G?

A

∆(G)

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

How do we denote the average degree of G?

A

d(G)

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

What is the distance between vertices u and v?

A

the minimum length of a u-v path, if one exists. If not it is infinity.

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

What is the diameter of a graph?

A

the maximum distance between any two points u and v

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

How is the distance between vertices u and v denoted?

A

d(u,v), or d_G(u,v)

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

How is the diameter of a graph denoted?

A

max_(u,v »V(G)) d(u,v)

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

What is the eccentricity of a vertex u?

A

The maximum distance between u and any other point.

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

How is the eccentricity of a vertex u denoted?

A

epsilon(u)

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

What is the radius of a graph?

A

The minimum eccentricity of any vertex u, or min_(u

«V(G)) epsilon(u)

28
Q

What is the girth of a graph?

A

The length of its shortest cycle.

29
Q

What is the circumference of a graph G?

A

The length of its longest cycle

30
Q

How do we denote the circumference of a graph G?

A

c(G)

31
Q

What is the girth and circumference of a graph G with no cycles?

A

Infinite!

32
Q

What is a forest?

A

A graph with no cycles

33
Q

What is a leaf?

A

A vertex of degree one in a forest

34
Q

What is a subgraph?

A

A subgraph of a graph G is a graph H such that V(H) are a subset of V(G) and E(H) are a subset of E(G).

35
Q

How do we denote that H is a subgraph of G?

A

H is a subset of G, and we say that G contains H.

36
Q

What is an induced subgraph?

A

If H is a subgraph of G such that H contains all edges uv »E(G) with uv »V(H), then H is called an induced subgraph of G. We often say that V’ is a subset of V(G) induces a subgraph H in G.

37
Q

What does it mean for a graph to be connected?

A

A graph is said to be connected if for every pair of vertices u and v there is a path from u to v in G.

38
Q

What is a disconnected graph?

A

A graph that is not connected.

39
Q

What is a component of a graph G?

A

Each maximal set of vertices that induces a connected subgraph of a graph G.

40
Q

What is a separating set of vertex cut of G?

A

A separating set or vertex cut of a graph G is a set S –(G) such that the graph induced by V(G) – S (often this induced subgraph is denoted by G – S) contains more than one component.

41
Q

What is the connectivity of a graph?

A

the minimum size of a vertex set S such that G – S contains more than one component or V(G) – S is a single vertex.

42
Q

How do we denote the connectivity of a graph G?

A

kah(G)

43
Q

What does it mean for a graph to be k-connected?

A

if its connectivity is at least k.

44
Q

What is the walk of a graph G?

A

A list v0,e1,v1, …, ek,vk, of vertices and edges such that for 1 ≤ i ≤ k, the edge e_i has endpoints v_(i-1) and vi.

45
Q

What is a closed walk?

A

A walk where the starting vertex and the ending vertex are the same.

46
Q

What is a trail?

A

A walk with no repeated edges.

47
Q

What is the degree sequence of a graph?

A

the list of vertex degrees, usually written in non-increasing order.

48
Q

What is a graphic sequence?

A

list of nonnegative numbers that is the degree sequence of some simple graph.

49
Q

What does it mean for a graph to realize d?

A

The simple graph has the degree sequence d.

50
Q

What is the Havel Hakimi Theorem?

A

A non-increasing sequence of nonnegative integers S: d1, … dp, (p ≥ 2) is graphical if and only if, the sequence S1: d2-1, d_(d1+1)-1;, d_(d1+2), …, dp is graphical.

51
Q

How can you prove the Havel Hakimi Theorem?

A

Assume S is a graphical sequence, and that the sum of the degree of the vertices adjacent to v_1 is maximum.

1) If the vertices adjacent to v_1 have degrees of d_2, d_3, etc, then the result is obvious.
2) There must exist two vertices then, which one has greater degree than the other, and the one with smaller degree is adjacent to v_1, and the one with higher degree not. These two could switch edges then, maintaining their degree. But v_1 would have more neighbors of higher degree! But that would mean that the sum of the degrees of the vertices in our sequence wasn’t maximum before, a contradiction.
QED.

52
Q

What is isomorphic?

A

Two graphs G and H are said to be isomorphic if there exists a bijection f:V(G) -≥ V(H) such that uv«E(G) if and only if f(u)f(v)«E(H). The bijection is often referred to as an isomorphism.

53
Q

What does it mean for a graph to be H-free?

A

A graph G is H-free if G has no subgraph isomorphic to H

54
Q

What is a matching?

A

A set of edges that share no endpoints

55
Q

What is a saturated vertex?

A

A vertex that is incident to an edge in a given matching.

56
Q

What is a perfect matching?

A

A matching that saturates every vertex in a graph.

57
Q

What is a maximum matching?

A

A matching of the largest size

58
Q

What is a maximal matching?

A

A matching that cannot be larger because of how it is placed.

59
Q

What is a M-alternating path?

A

A path that alternates between edges in the matching and edges not in the matching

60
Q

What is an M-augmenting path?

A

A M-alternating path where both endpoints are unsaturated by M.

61
Q

What is the disjoint union of G and H?

A

A graph in which V(G) U V(H) and E(G) U E(H)

62
Q

What is the symmetric difference of G and H?

A

A subgraph of G U H, whose edges are the edges of E(G) U E(H) appearing in exactly one of G and H.

63
Q

How do you denote the symmetric difference?

A

G∆H

64
Q

Every component of the symmetric difference of two matchings is…

A

a path or a cycle

65
Q

What is Berge’s Theorem?

A

A matching M in a graph G is a maximum matching in G iff G has no M-augmenting path.

66
Q

What is Hall’s Theorem?

A

An bipartite graph G with parts X and Y has a matching that saturates X if and only if |N(S)| ≥ |S| for all S within X.

67
Q

All trees are_____, have _____ edges, and contain _____.

A

connected,
n-1,
no cycles.

Graph Theory (3 decks)

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