Brainscape's Knowledge GenomeTM

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


See full index

Graph Theory > Graph Theory > Flashcards

Graph Theory Flashcards

1
Q

What is a graph?

A

Pair of sets (V(G),E(G)), where each element of E consists of a pair of elements of V

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

What is a walk in a graph G?

A

A sequence of vertices v_1 v_2 … v_n such that {v_i, v_i+1} is in E(G) for 1 <= i < n

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

What is a path in a graph G?

A

A walk where all the vertices are distinct

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

What is a cycle?

A

A closed walk of at least 3 vertices with otherwise distinct vertices

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

What does is mean for a graph G to be connected?

A

For any two vertices x,y in V(G), there is an xy-walk in G

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

What does it mean for two vertices x,y to lie in the same component?

A

They are joined by an xy-walk

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

What is a tree?

A

A minimally connected graph

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

Prove that any tree is acyclic

A
  • SFAC there is a cycle in T
  • Remove some edge e in this cycle
  • Then we obtain a path, P
  • Take two vertices x,y in T
  • Since T is connected, there is an xy-walk between them
  • If this walk used the edge we removed, replace it with the path P
  • This is still an xy-walk
  • So T-{e} is connected
  • Contradicts minimality of T
  • So T is acyclic
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Prove that a connected & acyclic graph G is a tree

A
  • SFAC G - {e} is connected for some e = xy in G
  • Let W be a shortest xy-walk in G-{e}
  • Then W must be an xy-path (otherwise it wouldn’t be the shortest)
  • So if we add e back in, we get a cycle, but G was acyclic, contradiction
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Prove that any two vertices in a tree are joined by a unique path

A
  • SFAC this isn’t true
  • i.e. there are two distinct xy-paths in T, P_1 and P_2
  • Suppose P_1 is the shortest over all such choices of x and y
  • Then P_1 and P_2 intersect only at x and y
  • But this is a cycle, contradiction
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Prove that any tree with at least two vertices has at least two leaves

A
  • Let P be a longest path in T
  • If the start / end of P had another neighbour in V(T)/V(P), we could make the path longer
  • If the start / end of P had another neighbour in V(P) other than the next in the sequence P, we would have a cycle
  • So the two ends of P must be leaves.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a leaf?

A

A vertex of degree 1

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

Prove that if T is a tree and v is a leaf, then T-v is a tree

A
  • Suffices to show T-v is connected & acyclic
  • Know T is acyclic, and we can’t create a cycle by removing an edge, so T-v is acyclic
  • Know T is connected
  • For any x,y in T-v, the unique xy-path in T is contained in T-v
  • So T-v is a tree
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Prove that any tree on n vertices has n-1 edges

A
  • By induction
  • A tree with 1 vertex has 0 edges
  • Consider a tree T on n vertices
  • Know T has a leaf v
  • Know T-v is a tree
  • T-v has n-1 vertices and n-2 edges by induction hypothesis
  • So T has n vertices & n-1 edges
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is a spanning tree?

A

Minimally connected subgraph of the same vertex set

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

Prove that a connected graph with n-1 edges and n vertices is a tree

A
  • Let H be a spanning tree of G
  • H has n vertices and n-1 edges
  • so H=G, i.e. G is a tree
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is a minimum cost spanning tree of G?

A

A spanning tree T of G such that for any other spanning tree T’, C(T’) >= C(T)

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

Describe Kruskal’s algorithm

A
  • A_0 = {}
  • Check if there is an edge e in G / A_i such that (V(G), A_i U {e}) is acyclic
  • If not, output A = A_i and stop
  • If there is, set A_i+1 = A_i ∪ {e} for one such e such that c(e) is minimal, then increase i by 1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Prove that Kruskal’s algorithm produces a minimum cost spanning tree of G

A

[CONTINUE]

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

What is an Euler trail?

A

A walk such that every edge in a graph appears exactly once

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

What is an Euler tour?

A

A closed Euler trail

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

What is an Eulerian graph?

A

A graph where every edge is of even degree (in an Euler tour, we use one edge to enter a vertex, and a different edge to leave).

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

What is Eulers theorem?

A

a connected Eulerian graph has an Euler Tour

24
Q

Prove Eulers theorem

A
  • Will prove that Fleury’s algorithm produces an Euler tour.
  • [CONTINUE]
25
Q

Describe Fleury’s Algorithm

A
  • Start at any vertex
  • Follow a walk, deleting each edge after it is used
  • At each step, ensure that after any isolated vertices are removed the graph is still connected, and that we do not run along an edge to a leaf, unless that is the only option.
26
Q

Prove that in any graph there are an even number of vertices of odd degree

A
  • The sum of the degrees of all the vertices in a graph is equal to 2 x no. of edges (since each edge connects to two vertices).
  • So the sum of the degrees of the vertices must be even
  • So there must be an even number of odd degree vertices
27
Q

What is a Hamiltonian cycle?

A

A closed walk that visits every vertex exactly once

28
Q

What is a hamiltonian graph?

A

A graph that contains a Hamiltonian cycle

29
Q

State Ore’s theorem

A
  • G a connected graph with n >= 3 vertices
  • For every pair of non-adjacent vertices x & y, d(x) + d(y) >= n
  • Then G is hamiltonian
30
Q

State Dirac’s theorem

A
  • G connected graph with n>= 3 vertices
  • For ever vertex v, d(v) >= n/2
  • Then G is Hamiltonian
31
Q

Prove that if G is connected an non-hamiltonian, then the length of the longest path is at least as long as the longest cycle

A
  • Let C be a longest cycle with length L
  • Since G is not hamiltonian, there is some vertex not in C.
  • Since G is connected, there is some edge vu with u in C and v not in C
  • Remove an edge of C that contains u and replace it with uv
  • This gives a path of length L
32
Q

Prove ore’s theorem

A
  • SFAC G is not hamiltonian
  • Let P = x1 x2 … xk be a longest path in G
  • P has length k-1
  • So G doesn’t have a cycle of length k (length of longest path >= length of longest cycle)
  • So x1 and xk are not adjacent
  • So d(x1) + d(xk) >= n
  • [CONTINUE]
33
Q

What is an L-shortest xy-path?

A

An xy-path P that minimises L(P)

34
Q

Describe Dijkstra’s algorithm

A
  • Goal: Find an L-shortest xy-path
  • Set U = V(G), D(x) = 0, D(v) = infinity for v != x
  • If U is empty, stop
  • Otherwise:
    • Pick u in U with D(u) minimal
    • Delete u from U
    • For any v in U that is adjacent to u, with D(v) > D(u) + L(uv), replace D(v) by D(u) + L(uv)
  • Repeat
35
Q

What is an L-shortest paths tree rooted at x of a graph G?

A
  • A spanning tree T
  • For any y in V(G), the unique xy path in T is an L-shortest xy-path in G.
36
Q

Wrt Dijkstra’s, what is the parent of a vertex v?

A

The last vertex u such that we replaced D(v) by D(u) + L(uv)

37
Q

How would you use Dijkstra’s to get an L-shortest paths tree rooted at x?

A
  • Run the algorithm
  • Determine the parent of each vertex
  • Draw an edge from each vertex to its parent
38
Q

What is a matching?

A

A subset of the edge set M such that the edges in M are pairwise disjoint.

39
Q

What is a perfect matching?

A

A matching M such that every vertex of the graph belongs to some edge of M

40
Q

What is a bipartite graph G?

A

A graph such that V(G) can be partitioned into two sets A, B so that every edge of G crosses between A and B

41
Q

If M is a matching and P is a path, what does it mean for P to be an M-alternating path?

A

Every other edge of P is in M

42
Q

If M is a matching and P is a path, what does it mean for P to be an M-augmenting path?

A

Every other edge of P is in M and it’s end vertices are not in any edge of M

43
Q

If M is a matching in G, prove that M is not of maximum size if and only if there is an M-augmenting path in G

A
  • If there is an M-augmenting path in P, we can create a larger matching by “flipping” every edge of P (replace M by M \ (M ∩ E(P)) ∪ (E(P) \ M))
  • Suppose M* is a matching with more edges than M
  • Let H = M U M*
  • Every vertex has degree at most 2 in H
  • So each component of H is an edge, path or cycle
  • The edge components consist of M ∩ M*
  • The edges in path and cycle components alternate between M and M*
  • As |M| > |M| we can find a path component with more edges of M
    than M
  • This is an M-augmenting path in G.
44
Q

Describe the Hungarian algorithm for finding a maximum matching in G

A
45
Q

What is a cover of G?

A

A set of vertices C such that every edge contains at least one vertex of C

46
Q

What is the relationship between the size of a matching and the size of a cover?

A

|M| <= |C|

47
Q

What is Konig’s theorem?

A

In any bipartite graph, the size of a maximum matching equals the size of a minimum cover

48
Q

Prove Konig’s theorem

A
49
Q

For a bipartite graph with parts A,B and a set S, a subset of A, what is the neighbourhood of S?

A

N(S) = ∪a∈S{b : ab ∈ E(G)}

i.e. the set of vertices in B that are joined by an edge to a vertex in S

50
Q

What is Hall’s theorem?

A
  • Let G be a bipartite graph with parts A,B
  • Then G has a matching covering A if and only if every S a subset of A has |N(S)| >= |S|
51
Q

Prove Hall’s theorem

A
52
Q

What is a postman walk in G?

A

A walk that uses every edge in G at least once

53
Q

Describe Edmond’s algorithm for the chinese postman problem

A
54
Q

For a graph H in which not all degrees are even, prove there is a path in H such
that both ends have odd degree

A
55
Q

Prove that Edmonds’ Algorithm finds a minimum length postman walk.

A
56
Q

What is the chinese postman problem?

A

The problem of finding the shortest postman walk - a walk that uses every edge of G at least once

Graph Theory (1 decks)

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