Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

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
What is the eccentricity of a vertex u?
The maximum distance between u and any other point.
26
How is the eccentricity of a vertex u denoted?
epsilon(u)
27
What is the radius of a graph?
The minimum eccentricity of any vertex u, or min_(u | «V(G)) epsilon(u)
28
What is the girth of a graph?
The length of its shortest cycle.
29
What is the circumference of a graph G?
The length of its longest cycle
30
How do we denote the circumference of a graph G?
c(G)
31
What is the girth and circumference of a graph G with no cycles?
Infinite!
32
What is a forest?
A graph with no cycles
33
What is a leaf?
A vertex of degree one in a forest
34
What is a subgraph?
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
How do we denote that H is a subgraph of G?
H is a subset of G, and we say that G contains H.
36
What is an induced subgraph?
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
What does it mean for a graph to be connected?
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
What is a disconnected graph?
A graph that is not connected.
39
What is a component of a graph G?
Each maximal set of vertices that induces a connected subgraph of a graph G.
40
What is a separating set of vertex cut of G?
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
What is the connectivity of a graph?
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
How do we denote the connectivity of a graph G?
kah(G)
43
What does it mean for a graph to be k-connected?
if its connectivity is at least k.
44
What is the walk of a graph G?
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
What is a closed walk?
A walk where the starting vertex and the ending vertex are the same.
46
What is a trail?
A walk with no repeated edges.
47
What is the degree sequence of a graph?
the list of vertex degrees, usually written in non-increasing order.
48
What is a graphic sequence?
list of nonnegative numbers that is the degree sequence of some simple graph.
49
What does it mean for a graph to realize d?
The simple graph has the degree sequence d.
50
What is the Havel Hakimi Theorem?
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
How can you prove the Havel Hakimi Theorem?
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
What is isomorphic?
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
What does it mean for a graph to be H-free?
A graph G is H-free if G has no subgraph isomorphic to H
54
What is a matching?
A set of edges that share no endpoints
55
What is a saturated vertex?
A vertex that is incident to an edge in a given matching.
56
What is a perfect matching?
A matching that saturates every vertex in a graph.
57
What is a maximum matching?
A matching of the largest size
58
What is a maximal matching?
A matching that cannot be larger because of how it is placed.
59
What is a M-alternating path?
A path that alternates between edges in the matching and edges not in the matching
60
What is an M-augmenting path?
A M-alternating path where both endpoints are unsaturated by M.
61
What is the disjoint union of G and H?
A graph in which V(G) U V(H) and E(G) U E(H)
62
What is the symmetric difference of G and H?
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
How do you denote the symmetric difference?
G∆H
64
Every component of the symmetric difference of two matchings is...
a path or a cycle
65
What is Berge's Theorem?
A matching M in a graph G is a maximum matching in G iff G has no M-augmenting path.
66
What is Hall's Theorem?
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
All trees are_____, have _____ edges, and contain _____.
connected, n-1, no cycles.

Graph Theory (3 decks)

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